Score:3

Crypto

Reference for basic secret sharing and MPC arithmetic algorithms

Kolja

5/30/24, 1:58 PM

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?

120

1 + 6

multiparty-computation

secret-sharing

arithmetic

Command Master

5/31/24, 4:44 AM

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$.

Kolja

6/5/24, 6:37 AM

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.

Geoffroy Couteau

6/5/24, 8:23 AM

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.

Kolja

6/5/24, 12:12 PM

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.

Geoffroy Couteau

6/5/24, 5:27 PM

Sorry, you're right, in one round you only get shares of the result; getting the result in the clear requires two rounds.

Kolja

6/5/24, 7:55 PM

I guess something like a Shamir secret sharing multiplication would work if we have a pre-shared secret share of zero (of degree $2t$) which we can use to mask the output.

Score:3

Crypto

Mikero

6/6/24, 3:27 AM

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).

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Reference for basic secret sharing and MPC arithmetic algorithms

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.