3
$\begingroup$

To the best of my knowledge, most of the MPC protocol's are built on a ring $\mathbb{Z}_{2^\ell}$(usually $\mathbb{Z}_{2^{64}}$) or field $\mathbb{Z}_p$ ($p$ is a big prime), why? What is the difference between them?

Examples:

Update:

This paper says that SS-MPC over the ring cannot easily construct the constant-round protocol due to a lack of the multiplicative inverse.

$\endgroup$
2
  • $\begingroup$ The better question, what are the advantages/disadvantages when a field is used instead of a ring... And given some references that you have seen will make the question have more quality. $\endgroup$
    – kelalaka
    Dec 7 '20 at 12:36
  • $\begingroup$ Ring may or may not have the multiplicative inverse, when it has it is called ring with unity. while field should have multiplicative inverse. MPC protocol may not need this. as Kelalaka mentioned please provide some reference. $\endgroup$
    – SSA
    Dec 7 '20 at 13:27
5
$\begingroup$

[...][Most] of the MPC protocol is built on a ring $\mathbb{Z}_{2^\ell}$(usually $\mathbb{Z}_{2^{64}}$) or field $\mathbb{Z}_p$($p$ is a big prime), why?

The relevant protocols for $\mathbb{Z}_{2^\ell}$ most likely use boolean sharing / boolean garbled circuits (representing each individual bit as a shared value) whereas the ones for $\mathbb{Z}_p$ use arithmetic sharing and in some rare cases arithmetic garbled circuits.

The core difference between these two is the set of operations that can be performed cheaply on each:

  • Bit-wise XOR tends to be extremely cheap with boolean sharing but is usually prohibitively expensive with arithmetic ones
  • Normal addition is not too-expensive for boolean sharings but tends to be free for arithmetic ones
  • Bitwise / -oriented gates and reductions in general tend to be much cheaper for boolean sharings than for arithmetic ones - e.g. equality comparisons or bitwise operations commonly seen in symmetric ciphers
  • Arithmetic operations tend to be much cheaper in the arithmetic case, especially multiplication which is a primitive operation there but requires $O(\ell^2)$ ish non-free operations for boolean sharings
$\endgroup$
3
  • $\begingroup$ $Z_2$ is already a field, wheater the designer uses or not. Does any use of DLOG? since the binary extension fields are dead. $\endgroup$
    – kelalaka
    Dec 7 '20 at 13:52
  • 2
    $\begingroup$ @kelalaka dlog is usually not used (directly) for MPC, you either use garbled circuits and then rely on some assumptions about your block cipher or you use the sharing variants which then use custom interactive protocols to compute ANDs / MULs. Though these commonly make some use of oblivious transfers which in turn may rely on "normal" dlog - though they can use strong instances for that because they only do ~128 such pk-intensive OTs and then use symmetric crypto get all they need. $\endgroup$
    – SEJPM
    Dec 7 '20 at 14:32
  • $\begingroup$ The relevant protocols for Z2ℓ most likely use boolean sharing I slightly disagree. There are protocols which work natively on rings. Think of 3 parties replicated secret sharing for semi-honest. We can get ring arithmetic for many malicious protocols as well. $\endgroup$
    – Dragos
    Jan 7 at 13:06
2
$\begingroup$

As discussed in @SEJPM's answer, traditionally, MPC over $\mathbb{Z}_{2^l}$ usually adopt boolean sharing while MPC over $\mathbb{Z}_p$ adopt arithmetic sharing and they mainly differ in the "primitve" set of operations they provide.

However, a few recent works (refer CDE+18,GRW18,KPPS20 and the works they cite) focus on efficient MPC for small parties over rings. These MPC protocols usually involve a secret shared evaluation of an arithmetic circuit consisting of addition and multiplication gates and should be compared to MPC protocols over fields. They differ from boolean sharing/boolean garbled circuits which tend to offer XOR and AND as the primitive operations.

Most MPC protocols over fields require the presence of an inverse for reconstruction of shares, linear MAC schemes etc., However, operating over fields introduces a relatively large overhead in terms of the concrete efficiency of implementations. Computation over rings like $\mathbb{Z}_{64}$ on the other hand are a better model for real-world CPU architectures. Additionally, it is arguably easier to work with real numbers over rings through fixed-point and floating point arithmetic.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.