3
$\begingroup$

I am looking for references for the most basic secret sharing and MPC arithmetic algorithms for generic rings or prime fields.

Problem:

Suppose there are $m$ parties $P_1, \ldots, P_m$ which wish to do arithmetic over a ring.

They hold some secret shared values $[x], [y]$ and they wish to compute $[x+y]$ and $[xy]$.

What are the basic algorithms for solving these problems?
What are the basic secret sharing methods that can be used?

I know of the following two basic secret sharing methods

  • Shamir secret sharing (essentially Lagrange interpolation, $t$ out of $n$ secure)
  • Additive secret sharing ($n-1$ out of $n$ secure)

Both of these secret sharing methods are linear (they allow for computation of $[x+y]$ by only doing local computations (additions)) and they provide information-theoretic security.

As for multiplication, it doesn't follow automatically, and I know of the following method

  • Beaver triples

which requires a precomputed triple $([a],[b],[ab])$ and one round of communication per multiplication, and is information theoretically secure.

Are there other algorithms for $+,\times$ in the MPC setting?
Which are the simplest ones?
Which require the least amount of communication?
Which require the least amount of precomputation?
Are there other related algorithms that one should be aware of?

Is it possible to compute a multiplication and open it in a single communication round?

I would appreciate any references or answers to the above questions.

EDIT: Additional question - what how do these algorithms generalise in a malicious adversary $(t<n/2 \text{ or } t<n/3)$ setting, either in an information theoretic or computational security model?

$\endgroup$
6
  • 1
    $\begingroup$ If you use Shamir's secret sharing with $t < n/2$ then you can perform the multiplication locally and then do a single (or maybe two, I don't remember) round of communication to reduce the degree of the polynomial back to the original $t$. $\endgroup$ May 31, 2023 at 4:44
  • $\begingroup$ Yes indeed, but that again requires a round of communication. I thought it might be possible to multiply locally and open, within a single comm round, however that would increase the degree of the polynomial, which would allow to recover the factors of the multiplication through polyomial factorisation. I'm still looking for a method that does mult+open in 1 round without precomputation. $\endgroup$
    – Kolja
    Jun 5, 2023 at 6:37
  • 1
    $\begingroup$ To be sure I understand: you want to reveal the product $xy$ in the clear, to everyone, using a single round of communication? If yes, then this can be done using a Beaver triple. $\endgroup$ Jun 5, 2023 at 8:23
  • $\begingroup$ How? The beaver triple method $([x],[y];[a],[b],[ab]\mapsto[xy])$ requires first an opening of $[x-a],[y-b]$, and then the opening of $[xy]$ after it is computed as $[xy]=[ab]+[x](y-a)+[y](x-b)+[1](x-a)(y-b)$. One can't just share $[ab]$ before computing $[xy]$, without compromising the security. One could compute it with optimal secret sharing where $x,y$ are shared as $(x+r, [r]), (y+r',[r'])$, but that would require that the Beaver triple $([r],[r'],[rr'])$ is dependent on the sharing of $x,y$, which I am hoping to avoid. All $[\cdot]$ above denote additive secret sharing. $\endgroup$
    – Kolja
    Jun 5, 2023 at 12:12
  • 1
    $\begingroup$ Sorry, you're right, in one round you only get shares of the result; getting the result in the clear requires two rounds. $\endgroup$ Jun 5, 2023 at 17:27

1 Answer 1

3
+50
$\begingroup$

I might suggest A Pragmatic Introduction to Secure Multi-Party Computation by Evans, Kolesnikov, Rosulek. It describes main protocols at a fairly high level. To answer your broad questions about what protocols are possible, I would suggest reading:

  • 3.3 BGW protocol
  • 3.4 preprocessed triples
  • 6.5 BDOZ & SPDZ, if you're interested in security against malicious parties

The answers to your more specific feasibility questions depend heavily on the threat model (honest/dishonest majority, semi-honest/malicious).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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