Question about robust MPC

[lu562]

Hi Marcel,

I need an arithmetic-sharing-based robust MPC framework for the implementation of a recent idea. After searching I realize there are currently no existing ones. I want to start building one by adding robust secret sharing reconstruction to some existing back-ends, do you have some suggestions about which back-end could be a good starting point? Some pointers to the corresponding codes are more appreciated, thanks!

[mkskeller]

I can think of two scenarios:

1. If Rep4 fails due to corruption, it should be easy to identify an honest party who then can finish the computation. This principle underlies works such as the following: https://eprint.iacr.org/2020/592
2. For larger number of parties, I can only think of Shamir secret sharing. https://eprint.iacr.org/2019/646 is the most recent work in this line I can think of.

[lu562]

Thanks for the info! I agree that Shamir secret sharing could be the best way to achieve robustness if we use 2t+1 shares to do reconstruction/Reed-Solomon decoding. If multiplication is done through Beaver triples then robust multiplication is also reduced to robust reconstruction.

btw, May I know what backends in MP-SPDZ use beaver triples to do multiplications? I may want to find a Shamir-based backend to start some prototypes.

[mkskeller]

Beaver triples are used in all dishonest-majority protocols as well as in malicious Shamir and Rep3.

[lu562]

Thank you! Malicious shamir party looks like a good start to me.

Best, Donghang.

---

From: Marcel Keller @.> Sent: Wednesday, May 4, 2022 6:13:14 AM To: data61/MP-SPDZ @.> Cc: Donghang Lu @.>; Author @.> Subject: Re: [data61/MP-SPDZ] Question about robust MPC (Issue #558)

Beaver triples are used in all dishonest-majority protocols as well as in malicious Shamir and Rep3.

— Reply to this email directly, view it on GitHubhttps://github.com/data61/MP-SPDZ/issues/558#issuecomment-1117144069, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AGNE4NYEGBRQ3VHAISBTZJTVIJETVANCNFSM5U4O3JFA. You are receiving this because you authored the thread.Message ID: @.***>

[lu562]

Hi, May I know more info about the following two questions?

(1) What encoding is deployed for Shamir Sharing (especially for malicious-shamir-party.x)? e.g. If the share is (x_i, y_i) for party i, what is x_i?

(2) Is there any way to access the module of the prime field ('p' of Z_p) in the source code level? The reason I ask is that I want to convert shares to vector_ZZ of ntl, so that I can use ntl to help with robust reed-solomon decoding. It looks like the shares do not have a specific data type, so I'm wondering what's the best way to do it.

Thanks in advance : )

[mkskeller]

1. x_i is i + 1.
2. Indeed, the prime isn't fixed during compilation by default. However, you can fix the computation to the prime of your choosing with -P during compilation or executiong.

[lu562]

Thanks for the clarification! I have a follow-up question about the Shamir Sharing:

I'm trying to modify the Shamir reconstruction function (https://github.com/data61/MP-SPDZ/blob/master/Protocols/MaliciousShamirMC.hpp#L46) to be a robust reconstruction. And I met some challenges when I want to extract the value from the "shares" array. It seems that the data type of those values is "open_type" and I don't know how I should access it. What should I do to extract those values to be int or long int? Any documents or articles could also be helpful!

[mkskeller]

open_type is the relevant instantiation of gfp_, documented here: https://mp-spdz.readthedocs.io/en/latest/low-level.html#_CPPv4I_i_iE4gfp_

[lu562]

Thank you, Marcel!

So is it the case that the actual value is stored in mp_limb_t? What should I do if I want to convert those values to int or long int? Since I want the actual share value to be something recognizable by ntl library.

[mkskeller]

The actual value is stored in an array of mp_limb_t in Montgomery representation. You can convert it normal representation by assigning it to bigint, which is a subclass of mpz_class in MPIR. An instance x of that class have an array of 64-limbs at x.get_mpz_t()._mp_d.

[lu562]

Thank you!

I've been modifying the malicious shamir reconstruction codes (https://github.com/data61/MP-SPDZ/blob/master/Protocols/MaliciousShamirMC.hpp#L46). And I found some interesting behaviors:

(1) so the shares array should be an array of gfp_ here as we are using shamir sharing. I also confirm that if I print the type of share[0], it shows "gfp_ILi0ELi2EE", so it looks good. Then I follow your advice and try to convert it to bigint. My first try is to do something as follows:

    bigint test;
    to_bigint(test, shares[0]);

However, when I compile it, the follow error occurs:

lu@ubuntu:~/MP-SPDZ$ make -j 8 malicious-shamir-party.x
g++ -o Machines/malicious-shamir-party.o Machines/malicious-shamir-party.cpp -DUSE_NTL -march=native -I./local/include -g -Wextra -Wall -O3 -I. -pthread    -DUSE_GF2N_LONG '-DPREP_DIR="Player-Data/"'  -std=c++11 -Werror -fPIC -MMD -MP -c
In file included from ./Math/Integer.h:14,
                 from ./Processor/Processor.h:8,
                 from ./Protocols/ReplicatedInput.h:10,
                 from ./Protocols/ShamirInput.h:11,
                 from ./Protocols/ShamirShare.h:10,
                 from ./Protocols/MaliciousShamirShare.h:9,
                 from Machines/malicious-shamir-party.cpp:7:
./Math/bigint.h: In instantiation of ‘void to_bigint(bigint&, const T&) [with T = gf2n_long]’:
./Protocols/MaliciousShamirMC.hpp:482:14:   required from ‘typename T::open_type MaliciousShamirMC<T>::reconstruct(const std::vector<typename T::open_type>&) [with T = MaliciousShamirShare<gf2n_long>; typename T::open_type = gf2n_long; typename T::open_type = gf2n_long]’
./Protocols/MaliciousShamirMC.hpp:450:12:   required from ‘typename T::open_type MaliciousShamirMC<T>::finalize_open() [with T = MaliciousShamirShare<gf2n_long>; typename T::open_type = gf2n_long]’
./Processor/Processor.hpp:399:18:   required from ‘void SubProcessor<T>::POpen(const std::vector<int>&, const Player&, int) [with T = MaliciousShamirShare<gf2n_long>]’
./Processor/Instruction.hpp:1008:9:   required from ‘void Instruction::execute(Processor<sint, sgf2n>&) const [with sint = MaliciousShamirShare<gfp_<0, 1> >; sgf2n = MaliciousShamirShare<gf2n_long>]’
./Processor/Instruction.hpp:1304:11:   required from ‘void Program::execute(Processor<sint, sgf2n>&) const [with sint = MaliciousShamirShare<gfp_<0, 1> >; sgf2n = MaliciousShamirShare<gf2n_long>]’
./Processor/Online-Thread.hpp:266:11:   [ skipping 2 instantiation contexts, use -ftemplate-backtrace-limit=0 to disable ]
./Processor/Machine.hpp:144:21:   required from ‘Machine<sint, sgf2n>::Machine(int, Names&, const string&, const string&, int, bool, int, bool, int, bool, bool, OnlineOptions) [with sint = MaliciousShamirShare<gfp_<0, 1> >; sgf2n = MaliciousShamirShare<gf2n_long>; std::string = std::__cxx11::basic_string<char>]’
./Processor/OnlineMachine.hpp:233:9:   required from ‘int OnlineMachine::run() [with T = MaliciousShamirShare<gfp_<0, 1> >; U = MaliciousShamirShare<gf2n_long>]’
./Processor/FieldMachine.hpp:47:5:   required from ‘FieldMachine<U, V, W, X>::FieldMachine(int, const char**, ez::ezOptionParser&, OnlineOptions&, int) [with U = MaliciousShamirShare; V = MaliciousShamirShare; W = HonestMajorityMachine; X = gf2n_long]’
./Processor/FieldMachine.hpp:29:5:   required from ‘HonestMajorityFieldMachine<U, V>::HonestMajorityFieldMachine(int, const char**, ez::ezOptionParser&, int) [with U = MaliciousShamirShare; V = HonestMajorityMachine]’
Machines/ShamirMachine.hpp:101:5:   required from ‘ShamirMachineSpec<T>::ShamirMachineSpec(int, const char**) [with T = MaliciousShamirShare]’
Machines/malicious-shamir-party.cpp:14:55:   required from here
./Math/bigint.h:210:9: error: ‘const class gf2n_long’ has no member named ‘to’; did you mean ‘int gf2n_<int128>::t [4]’? (not accessible from this context)
  210 |   other.to(res);
      |   ~~~~~~^~
In file included from ./Math/gf2nlong.h:19,
                 from ./Math/Integer.h:18,
                 from ./Processor/Processor.h:8,
                 from ./Protocols/ReplicatedInput.h:10,
                 from ./Protocols/ShamirInput.h:11,
                 from ./Protocols/ShamirShare.h:10,
                 from ./Protocols/MaliciousShamirShare.h:9,
                 from Machines/malicious-shamir-party.cpp:7:
./Math/gf2n.h:252:5: note: declared protected here
  252 | int gf2n_<U>::t[4];
      |     ^~~~~~~~
In file included from ./Math/Integer.h:14,
                 from ./Processor/Processor.h:8,
                 from ./Protocols/ReplicatedInput.h:10,
                 from ./Protocols/ShamirInput.h:11,
                 from ./Protocols/ShamirShare.h:10,
                 from ./Protocols/MaliciousShamirShare.h:9,
                 from Machines/malicious-shamir-party.cpp:7:
./Math/bigint.h: In instantiation of ‘void to_bigint(bigint&, const T&) [with T = gf2n_short]’:
./Protocols/MaliciousShamirMC.hpp:482:14:   required from ‘typename T::open_type MaliciousShamirMC<T>::reconstruct(const std::vector<typename T::open_type>&) [with T = GC::MaliciousCcdShare<gf2n_short>; typename T::open_type = gf2n_short; typename T::open_type = gf2n_short]’
./Protocols/MaliciousShamirMC.hpp:450:12:   required from ‘typename T::open_type MaliciousShamirMC<T>::finalize_open() [with T = GC::MaliciousCcdShare<gf2n_short>; typename T::open_type = gf2n_short]’
./Protocols/MaliciousShamirMC.hpp:444:23:   required from here
./Math/bigint.h:210:9: error: ‘const class gf2n_short’ has no member named ‘to’; did you mean ‘int gf2n_<long unsigned int>::t [4]’? (not accessible from this context)
  210 |   other.to(res);
      |   ~~~~~~^~
In file included from ./Math/gf2nlong.h:19,
                 from ./Math/Integer.h:18,
                 from ./Processor/Processor.h:8,
                 from ./Protocols/ReplicatedInput.h:10,
                 from ./Protocols/ShamirInput.h:11,
                 from ./Protocols/ShamirShare.h:10,
                 from ./Protocols/MaliciousShamirShare.h:9,
                 from Machines/malicious-shamir-party.cpp:7:
./Math/gf2n.h:45:14: note: declared protected here
   45 |   static int t[4], l[4];
      |              ^
make: *** [Makefile:70: Machines/malicious-shamir-party.o] Error 1

It looks like T is recognized to be gf2n somehow during the compilation, so I'm not sure if I'm doing it correctly.

(2) my second try is that I see the values of gfp_ is actually in modp, and modP has a to_bigint() function. So I tried this:

shares[0].get().to_bigint(test, shares[0].get_ZpD());

then again the error looks similar:

lu@ubuntu:~/MP-SPDZ$ make -j 8 malicious-shamir-party.x
g++ -o Machines/malicious-shamir-party.o Machines/malicious-shamir-party.cpp -DUSE_NTL -march=native -I./local/include -g -Wextra -Wall -O3 -I. -pthread    -DUSE_GF2N_LONG '-DPREP_DIR="Player-Data/"'  -std=c++11 -Werror -fPIC -MMD -MP -c
In file included from Machines/ShamirMachine.hpp:25,
                 from Machines/malicious-shamir-party.cpp:10:
./Protocols/MaliciousShamirMC.hpp: In instantiation of ‘typename T::open_type MaliciousShamirMC<T>::reconstruct(const std::vector<typename T::open_type>&) [with T = MaliciousShamirShare<gf2n_long>; typename T::open_type = gf2n_long; typename T::open_type = gf2n_long]’:
./Protocols/MaliciousShamirMC.hpp:450:12:   required from ‘typename T::open_type MaliciousShamirMC<T>::finalize_open() [with T = MaliciousShamirShare<gf2n_long>; typename T::open_type = gf2n_long]’
./Processor/Processor.hpp:399:18:   required from ‘void SubProcessor<T>::POpen(const std::vector<int>&, const Player&, int) [with T = MaliciousShamirShare<gf2n_long>]’
./Processor/Instruction.hpp:1008:9:   required from ‘void Instruction::execute(Processor<sint, sgf2n>&) const [with sint = MaliciousShamirShare<gfp_<0, 1> >; sgf2n = MaliciousShamirShare<gf2n_long>]’
./Processor/Instruction.hpp:1304:11:   required from ‘void Program::execute(Processor<sint, sgf2n>&) const [with sint = MaliciousShamirShare<gfp_<0, 1> >; sgf2n = MaliciousShamirShare<gf2n_long>]’
./Processor/Online-Thread.hpp:266:11:   [ skipping 2 instantiation contexts, use -ftemplate-backtrace-limit=0 to disable ]
./Processor/Machine.hpp:144:21:   required from ‘Machine<sint, sgf2n>::Machine(int, Names&, const string&, const string&, int, bool, int, bool, int, bool, bool, OnlineOptions) [with sint = MaliciousShamirShare<gfp_<0, 1> >; sgf2n = MaliciousShamirShare<gf2n_long>; std::string = std::__cxx11::basic_string<char>]’
./Processor/OnlineMachine.hpp:233:9:   required from ‘int OnlineMachine::run() [with T = MaliciousShamirShare<gfp_<0, 1> >; U = MaliciousShamirShare<gf2n_long>]’
./Processor/FieldMachine.hpp:47:5:   required from ‘FieldMachine<U, V, W, X>::FieldMachine(int, const char**, ez::ezOptionParser&, OnlineOptions&, int) [with U = MaliciousShamirShare; V = MaliciousShamirShare; W = HonestMajorityMachine; X = gf2n_long]’
./Processor/FieldMachine.hpp:29:5:   required from ‘HonestMajorityFieldMachine<U, V>::HonestMajorityFieldMachine(int, const char**, ez::ezOptionParser&, int) [with U = MaliciousShamirShare; V = HonestMajorityMachine]’
Machines/ShamirMachine.hpp:101:5:   required from ‘ShamirMachineSpec<T>::ShamirMachineSpec(int, const char**) [with T = MaliciousShamirShare]’
Machines/malicious-shamir-party.cpp:14:55:   required from here
./Protocols/MaliciousShamirMC.hpp:483:21: error: ‘class int128’ has no member named ‘to_bigint’
  483 |     shares[0].get().to_bigint(test, shares[0].get_ZpD());
./Protocols/MaliciousShamirMC.hpp:483:47: error: ‘const value_type’ {aka ‘const class gf2n_long’} has no member named ‘get_ZpD’; did you mean ‘get_t’?
  483 |     shares[0].get().to_bigint(test, shares[0].get_ZpD());
      |                                     ~~~~~~~~~~^~~~~~~
      |                                     get_t
./Protocols/MaliciousShamirMC.hpp: In instantiation of ‘typename T::open_type MaliciousShamirMC<T>::reconstruct(const std::vector<typename T::open_type>&) [with T = GC::MaliciousCcdShare<gf2n_short>; typename T::open_type = gf2n_short; typename T::open_type = gf2n_short]’:
./Protocols/MaliciousShamirMC.hpp:450:12:   required from ‘typename T::open_type MaliciousShamirMC<T>::finalize_open() [with T = GC::MaliciousCcdShare<gf2n_short>; typename T::open_type = gf2n_short]’
./Protocols/MaliciousShamirMC.hpp:444:23:   required from here
./Protocols/MaliciousShamirMC.hpp:483:21: error: request for member ‘to_bigint’ in ‘(&(& shares)->std::vector<gf2n_short>::operator[](0))->gf2n_short::<anonymous>.gf2n_<long unsigned int>::get()’, which is of non-class type ‘long unsigned int’
  483 |     shares[0].get().to_bigint(test, shares[0].get_ZpD());
./Protocols/MaliciousShamirMC.hpp:483:47: error: ‘const value_type’ {aka ‘const class gf2n_short’} has no member named ‘get_ZpD’; did you mean ‘get_t’?
  483 |     shares[0].get().to_bigint(test, shares[0].get_ZpD());
      |                                     ~~~~~~~~~~^~~~~~~
      |                                     get_t
make: *** [Makefile:70: Machines/malicious-shamir-party.o] Error 1

So somehow the shares array is treated as gf2n instead of gfp_ during the compilation, could you enlighten me how to fix this mismatch? Appreciate it!

[lu562]

Or are there ways that I can force Shamir sharing to be in GF(p) instead of GF(2^n) when I compile malicious-sharmir-party.x?

[mkskeller]

This is because the virtual machines provide computation in both domains. You can avoid by this by working without the virtual machine infrastructure (e.g., with paper-example.x) or by providing a dummy to function in gf2n_: void to(bigint&) {}

[lu562]

Thank you! It works after I add the dummy to() to gf2n. brilliant idea : )

I have some questions about the input shares array of the reconstruction function:

(1) for now I assume shares[i] store the value from party i, is it the case?

(2) Besides, what happens if let's say the shares of party j never arrive in this round? what does the shares array look like in this case? are there relevant documents?

(3) could I control the size of the shares array when the reconstruction function is called. (e.g. parties run reconstruct() only when the party receives 2t+1 or more shares.)

[mkskeller]

1. shares[i] stores the share of party (j+i)%n where j is the current party. This is to evenly the communication load.
2. The framework expects all parties to be online, so if there is something missing, the program will freeze or crash.
3. I think this requires deeper changes in the communication component as the current operating mode is to simply abort when some expected information doesn't arrive.