Multi-Party Computation

Like the “match-making” game, computation often consists of two or more parties, and often each party has its own privacy or security concern. This section discusses generic approaches.

Secret Sharing

Definition: Secret Sharing

A (k,n) Secret Sharing scheme consists of a pair of PPT algorithms (Share,Recon) if it satisfies the following correctness and security.

  1. Share(x) produces an n-tuple (s1,...,sn), and
  2. Recon(si1,...,sik) is such that if {si1,...,sik}{s1,...,sn} then Recon outputs x.

Security: For any two x and x, and for any subset of at most k1 indicies S[1,n],|S|<k, the following two distributions are statistically close:

  • {(s1,...,sn)Share(x):(si)iS} and
  • {(s1,...,sn)Share(x):(si)iS}

Note: we say that two ensembles {Xλ}λN and {Yλ}λN are statistically iff there exists a negligible function ϵ such that the statistical difference Δ(Xλ,Yλ)ϵ(λ) for all λN.

Example: one-time pad is a (2,2) secret sharing.

Protocol: Shamir Secret Sharing

Sharek,n(x):

  1. Let p be a prime such that p>n. Choose k1 random coefficients, a1,...,ak1 where aiZp.
  2. Let s(t)=x+a1t+a2t2+···+ak1tk1. Output the shares s1:=(1,s(1)),...,sn:=(n,s(n)).

Reconk,n((xi1,yi1),...,(xik,yik)):

  1. Interpolate the unique polynomial P that passes through all k points given as input. (using the Lagrange formula). Output the value P(0).

The correctness follows by that Lagrange interpolation is unique. The security holds because for both x,x, for any |S|k1, we will sample the same (si)iS with identical probability (by modifying Share w.r.t. S).

Lemma: Lagrange interpolation

Given n+1 points (x0,y0),...,(xn,yn) in which x0,...,xn are distinct. Let

pi(x):=j=0,jinxxjxixj.

The unique degree-n polynomial that interpolates these n+1 points is

P(x)=i=0nyipi(x).

Notice that pi depends only on xi’s. Specifically in Recon, xi’s are public information, and thus the output is a linear combination of yi’s.

We next show that Shamir secret sharing yields secure addition and multiplication.

Protocol: Addition of Shares

Let n be the number of parties. Let a,bZp for prime p>n. Let a(x),b(x) be degree k polynomials (abusing notation) such that

  • a(0)=a, sia=(i,a(i)) for all i[n]
  • b(0)=b, and sib=(i,b(i)) analogously

Then, two shares sia,sib can be added by

  • sia+b:=(i,a(i)+b(i)),

and moreover, sia+b for all i[n] is a (k,n) secret sharing of a+b.

We can extend this addition protocol to compute multiplication by a public constant (that is known to all n parties).

The multiplication of two secrets is more involved. Let π(x):=a(x)b(x). We have π(0)=a(0)b(0)=ab, but there are two challenges:

  1. Since a(x) and b(x) are degree k, π(x) is degree 2k. That is, to reconstruct ab, we need 2k shares instead of k.
  2. π(x) is not a random polynomial of degree 2k (such that π(0)=ab) because a random polynomial is unlikely to be decomposible to two polynomials. This could be a security issue: (i,π(i)=a(i)b(i)) is not (2k,n) a secret share.

To overcome them, the first idea is that, if we want to Recon immediately after multiplication and we have more than 2k shares, we can still perform interpolation to fully reconstruct (all the coefficients of) π(x) and thus ab. Or equivalently, just dropping the higer degree coefficients of π(x). However, we may not have 2k shares. Moreover, we really want to obtain shares (rather than Recon), so that we can continue with further addition and multiplication.

The second idea is to re-randomize pi(x), so that it becomes a random 2k-degree polynomial pi(x). Then, we can perform Recon on π(x) using secret sharing again, so that the resulting coefficients of π(x) are again (k,n) shares. See the protocol below.

Protocol: Multiplication of Shares

Let n be the number of parties. Let a,bZp for prime p>n. Let a(x),b(x) be degree k<n/2 polynomials (abusing notation) such that

  • a(0)=a, sia=(i,a(i)) for all i[n]
  • b(0)=b, and sib=(i,b(i)) analogously

Two shares sia,sib can be multiplied by

  1. For all party i[n], compute (i,π(i)=a(i)b(i))
  2. For all party i[n], compute (2k,n) share of 0 by (ri,1,,ri,nShare2k,n(0), and then send ri,j from i to j, where ri,j:=(j,ri(j)) for random 2k-degree polynomial s.t. ri(0)=0
  3. All parties locally compute the shares (i,π(i)), where

    π(x):=π(x)+iri(x)
  4. All parties jointly perform Recon using the addition of secret shares to obtain the new shares of π(0)=ab; that is, do the following:

    1. For all party i, ((1,si,1),,(n,si,n))Share(π(i)) to all n parties
    2. All parties locally compute Reconk,n using shares; that is, party j takes the shares (s1,j,s2,j,sn,j), lets (xt,yt):=(t,st,j) for all t, and run the Lagrange interpolation using all (xt,yt) pairs, and then let Sj(x) be the resulting polynomial.

    The value (j,Sj(0)) is the new (k,n) share of ab.

The security proof (for multiplication) is omitted due to involved notation. The efficiency is not great: each party sends and receives O(n) messages. It requires n>2k to work, and it assumes that all parties are honest but curious, meaning that they always follow the prescribed protocol. The strength is that it achieves perfect security, that is, any (unbounded) adversary that corrupts <k parties learns nothing more than the output.

Discuss:

  • How about FHE?

[Ref: Ps, Sec 6.1] Arora@Princeton

Yao’s Garbling

For computationally bounded adversaries, we use garbled circuits to achieve MPC. Consider the truth table of any Boolean gate.

abAND
000
010
100
111

The idea of Yao’s garbling is to use two different keys to represent the 0-or-1 wire value.

abAND, c
k0ak0bEnck0a(Enck0b(k0c))
k0ak1bEnck0a(Enck1b(k0c))
k1ak0bEnck1a(Enck0b(k0c))
k1ak1bEnck1a(Enck1b(k1c))

We sample all key k’s (for all super- and sub-scripts) independently using Gen, and we perform all Enc using a secure (symmetric-key) encryption scheme. Any NUPPT adversary that is given only the ciphertexts can not know the table is an AND gate, as long as we permute the rows uniformly at random:

abc
  Enck0a(Enck0b(k0c))
  Enck1a(Enck1b(k1c))
  Enck1a(Enck0b(k0c))
  Enck0a(Enck1b(k0c))

Moreover, when an evaluator is given the above 4 rows and additionally the keys (k0a,k0b), the evaluator can decrypt exactly 1 row and then obtain k0c. Since k0a,k0b,k0c are representing the values of the wires a,b,c, the evaluator can perform any computation without knowing the values and logic gates.

A minor issue is that the evaluator needs to know which row decrypts correctly. This can be solved by either one of the two below:

  • Use an encryption scheme such that if the key is incorrect, Dec outputs with overwhelming probability (so that the evaluator knows which row is correct)
  • Mark the 4 rows uniformly at random, and then attach the mark to the corresponding ka’s and kb’s (so that the marks indicate which row to decrypt)

Composing the garbled Boolean gates, we can garble any Boolean circuit. Let n be the security parameter (such as the length of the secret key). For any circuit C and input x that are of polynomial size in n:

  • (C~,label)Garble(1n,C)
  • x~label(x)
  • yEval(C~,x~)

We require that y=C(x) for correctness. For security, we require that there exists a PPT simulator S such that

{(C~,x~)}{S(1n,|C|,|x|,C(x))}.

That is, S simulates the garbling (C~,x~) given only the output C(x).

We can use garbled circuits to achieve one-sided secure two-party computation.

Alice, input x1Public computation, circuit CBob, private input x2
  For each wire wC, sample wire keys kbwGen for b=0,1
  For each gate gC, compute 4 encrypted rows using the corresponding wire keys, and let {g~}gC be the result
  Send {g~}gC to Alice. For each input wire corresponding to x2, send the garbled input, x~2, to Alice.
Send x1 to Bob  
  For each input wire corresponding to x1, send the garbled input, x~1, to Alice.
Gate by gate evaluate g~’s, and obtain C(x1,x2)  

Notice that one-sided security is actually trivial: Alice gives out x1, and thus Bob can simply compute C(x1,x2). Thus, oblivious transfer is typically used.

Oblivious Transfer

 Alice, senderBob, receiver
Inputbits (a0,a1)bit i{0,1}
Outputnothingbit ai
Securitylearns nothing about ilearns only ai but nothing about ai for ii

We often consider two variants of security definitions:

  • Semi-honest: both Alice and Bob follow the porescribed protocol
  • Malicious: even if Alice deviates from the protocol arbitrarily, she still learns nothing about i; similarly, even if Bob deviates from the protocol arbitrarily, he still learns only ai.

The malicious setting is involved an skipped in this lecture. The semi-honest setting can be formalized by indistinguishability (similar to encryption).

Toy protocol based on public-key encryption:

  1. Bob samples (pk,sk)Gen, lets pki:=pk, and samples pki¯ uniformly at random. Bob sends (pk0,pk1) to Alice.
  2. Alice encrypts aj with pkj and gets ciphertexts cjEncpkj(aj) for j=0,1. Alice sends (c0,c1) to Bob.
  3. Bob decrypts ci using sk and then gets ai.

This protocol requires that pk is indistinguishable from uniform random string.

Using “trapdoor permutation” we can formalize this toy protocol. We can also instantiate the idea using concrete assumptions such as LWE (or DDH or RSA).

[Ps Sec 6.2.4] Barak@Princeton