edabits with SPDZ2k

[mfaisal97]

Hi Marcel,

First, thanks a lot for creating this nice opensource library.

I have question regarding the implementation of SPDZ2k with edabits. How do you instantiate the binary protocol [x]_2 needed for the edabits? The documentation mentions using an adapted version of SPDZ2k using work from Furukawa.

Is there a pseduocode for the resulting protocol? Can you point to the location of the resulting AND/XOR implementation for this protocol? Thanks a lot.

[mkskeller]

Where in the documentation are you referring to? The following table is meant to say a combination between Frederiksen et al. and Furukawa et al.: https://mp-spdz.readthedocs.io/en/latest/non-linear.html#protocol-pairs

Frederiksen et al. contains pseudocode for the offline phase, the only difference is that the bucket sacrifice is replaced with the more efficient one by Furukawa et al. For AND/XOR, the standard approach for Beaver triple protocols are used, see for example Chapter 3.4 in the following textbook: https://securecomputation.org/docs/ch3-fundamentalprotocols.pdf

[mfaisal97]

Thank your helpful reply!

What I was referring to is "Tiny denotes the adaption of SPDZ2k to the binary setting. In particular, the SPDZ2k sacrifice does not work for bits, so we replace it by cut-and-choose according to Furukawa et al." from https://mp-spdz.readthedocs.io/en/latest/readme.html#protocols .

Does the online phase of this protocol give malicious dishonest-majority security? If yes, is that achieved without using a MAC or we use MAC as indicated by the SPDZ2k protocol instantiated with k=1?

What I understand so far is that by "adaption of SPDZ2k" you mean (a) instantiating the SPDZ2k protocol with k=1 for online phase but (b) the preprocessing phase is using techniques from Frederiksen et al. and Furukawa et al.

Also, please note that I am interested in how the secret sharing [x]_2 needed for the edabits is implemented in the case of malicious dishonest majority so if there is a more efficient binary protocol than the tiny/tinier, please let me know.

Thanks a lot. Have a good day.

[mkskeller]

What I was referring to is "Tiny denotes the adaption of SPDZ2k to the binary setting. In particular, the SPDZ2k sacrifice does not work for bits, so we replace it by cut-and-choose according to Furukawa et al." from https://mp-spdz.readthedocs.io/en/latest/readme.html#protocols .

Tiny is a different protocol than Tinier used for binary secret sharing in MP-SPDZ and the Crypto paper.

Does the online phase of this protocol give malicious dishonest-majority security? If yes, is that achieved without using a MAC or we use MAC as indicated by the SPDZ2k protocol instantiated with k=1?

Yes, Tinier uses a MAC as described by Frederiksen et al.

What I understand so far is that by "adaption of SPDZ2k" you mean (a) instantiating the SPDZ2k protocol with k=1 for online phase but (b) the preprocessing phase is using techniques from Frederiksen et al. and Furukawa et al.

No, SPDZ2k with k=1 is not used for the online phase, it's Frederiksen et al. Their MAC works differently, in particular the addition of MACs is done via XOR and not integer addition as in SPDZ2k.

Also, please note that I am interested in how the secret sharing [x]_2 needed for the edabits is implemented in the case of malicious dishonest majority so if there is a more efficient binary protocol than the tiny/tinier, please let me know.

I'm not aware of a more efficient protocol.