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
Secret Sharing scheme consists of a pair of PPT algorithms if it satisfies the following correctness and security.
produces an -tuple , and is such that if then outputs . Security: For any two
and , and for any subset of at most indicies , the following two distributions are statistically close:
and Note: we say that two ensembles
and are statistically iff there exists a negligible function such that the statistical difference for all .
Example: one-time pad is a
Protocol: Shamir Secret Sharing
:
- Let
be a prime such that . Choose random coefficients, where . - Let
. Output the shares .
:
- Interpolate the unique polynomial
that passes through all points given as input. (using the Lagrange formula). Output the value .
The correctness follows by that Lagrange interpolation is unique. The security holds because for both
Lemma: Lagrange interpolation
Given
points in which are distinct. Let The unique degree-
polynomial that interpolates these points is
Notice that
We next show that Shamir secret sharing yields secure addition and multiplication.
Protocol: Addition of Shares
Let
be the number of parties. Let for prime . Let be degree polynomials (abusing notation) such that
, for all , and analogously Then, two shares
can be added by
, and moreover,
for all is a secret sharing of .
We can extend this addition protocol to compute multiplication by a public constant (that is known to all
The multiplication of two secrets is more involved. Let
- Since
and are degree , is degree . That is, to reconstruct , we need shares instead of . is not a random polynomial of degree (such that ) because a random polynomial is unlikely to be decomposible to two polynomials. This could be a security issue: is not a secret share.
To overcome them, the first idea is that, if we want to
The second idea is to re-randomize
Protocol: Multiplication of Shares
Let
be the number of parties. Let for prime . Let be degree polynomials (abusing notation) such that
, for all , and analogously Two shares
can be multiplied by
- For all party
, compute - For all party
, compute share of 0 by , and then send from to , where for random -degree polynomial s.t. All parties locally compute the shares
, where All parties jointly perform
using the addition of secret shares to obtain the new shares of ; that is, do the following:
- For all party
, to all parties - All parties locally compute
using shares; that is, party takes the shares , lets for all , and run the Lagrange interpolation using all pairs, and then let be the resulting polynomial. The value
is the new share of .
The security proof (for multiplication) is omitted due to involved notation. The efficiency is not great: each party sends and receives
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.
AND | ||
---|---|---|
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
The idea of Yao’s garbling is to use two different keys to represent the 0-or-1 wire value.
AND, | ||
---|---|---|
We sample all key
Moreover, when an evaluator is given the above 4 rows and additionally the keys
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,
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
’s and ’s (so that the marks indicate which row to decrypt)
Composing the garbled Boolean gates, we can garble any Boolean circuit. Let
We require that
That is,
We can use garbled circuits to achieve one-sided secure two-party computation.
Alice, input | Public computation, circuit | Bob, private input |
---|---|---|
For each wire | ||
For each gate | ||
Send | ||
Send | ||
For each input wire corresponding to | ||
Gate by gate evaluate |
Notice that one-sided security is actually trivial: Alice gives out
Oblivious Transfer
Alice, sender | Bob, receiver | |
---|---|---|
Input | bits | bit |
Output | nothing | bit |
Security | learns nothing about | learns only |
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
; similarly, even if Bob deviates from the protocol arbitrarily, he still learns only .
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:
- Bob samples
, lets , and samples uniformly at random. Bob sends to Alice. - Alice encrypts
with and gets ciphertexts for . Alice sends to Bob. - Bob decrypts
using and then gets .
This protocol requires that
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