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

- $\Share(x)$ produces an $n$-tuple $(s_1, . . . , s_n)$, and
- $\Recon(s’_{i_1} , . . . , s’_{i_k} )$ is such that if $\set{s’_{i_1} , . . . , s’_{i_k} } \subseteq \set{s_1, . . . , s_n}$ then $\Recon$ outputs $x$.
Security: For any two $x$ and $x’$, and for any subset of at most $k-1$ indicies $S’ \subset [1, n], |S’| < k$, the following two distributions are statistically close:

- $\set{(s_1, . . . , s_n) \gets \Share(x) : (s_i)_{i \in S’}}$ and
- $\set{(s_1, . . . , s_n) \gets \Share(x’) : (s_i)_{i \in S’}}$
Note: we say that two ensembles $\set{X_\lambda}_{\lambda\in\N}$ and $\set{Y_\lambda}_{\lambda\in\N}$ are statistically iff there exists a negligible function $\eps$ such that the statistical difference $\Delta(X_\lambda, Y_\lambda) \le \eps(\lambda)$ for all $\lambda\in\N$.

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

#### **Protocol**: Shamir Secret Sharing

$\Share_{k,n}(x)$:

- Let $p$ be a prime such that $p \gt n$. Choose $k - 1$ random coefficients, $a_1, . . . , a_{k−1}$ where $a_i \in Z_p$.
- Let $s(t) = x + a_1 t + a_2t^2 + · · · + a_{k-1}t^{k-1}$. Output the shares $s_1:=(1,s(1)), . . . , s_n := (n,s(n))$.
$\Recon_{k,n}((x_{i_1} , y_{i_1} ), . . . , (x_{i_k} , y_{i_k} ))$:

- 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’| \le k-1$, we will sample the same $(s_i)_{i\in S’}$ with identical probability (by modifying $\Share$ w.r.t. $S’$).

#### **Lemma:** Lagrange interpolation

Given $n + 1$ points $(x_0, y_0), . . . , (x_n, y_n)$ in which $x_0, . . . , x_n$ are distinct. Let

\[p_i(x) := \prod_{j=0, j\neq i}^n \frac{x-x_j}{x_i-x_j}.\]The unique degree-$n$ polynomial that interpolates these $n+1$ points is

\[P(x) = \sum_{i=0}^n y_i \cdot p_i(x).\]

Notice that $p_i$ depends only on $x_i$’s. Specifically in $\Recon$, $x_i$’s are public information, and thus the output is a linear combination of $y_i$’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, b \in \Z_p$ for prime $p > n$. Let $a(x), b(x)$ be degree $k$ polynomials (abusing notation) such that

- $a(0) = a$, $s^a_{i} = (i,a(i))$ for all $i \in [n]$
- $b(0) = b$, and $s^b_{i} = (i, b(i))$ analogously
Then, two shares $s^a_{i}, s^b_{i}$ can be added by

- $s^{a+b}_{i} := (i, a(i) + b(i))$,
and moreover, $s^{a+b}_{i}$ for all $i \in [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 $\pi(x) := a(x) \cdot b(x)$. We have $\pi(0) = a(0) \cdot b(0) = a \cdot b$, but there are two challenges:

- Since $a(x)$ and $b(x)$ are degree $k$, $\pi(x)$ is degree $2k$. That is, to reconstruct $a \cdot b$, we need $2k$ shares instead of $k$.
- $\pi(x)$ is not a random polynomial of degree $2k$ (such that $\pi(0) = a\cdot b$) because a random polynomial is unlikely to be decomposible to two polynomials. This could be a security issue: $(i,\pi(i)=a(i)\cdot 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) $\pi(x)$ and thus $a \cdot b$. Or equivalently, just dropping the higer degree coefficients of $\pi(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 $\pi’(x)$ *using secret sharing again*, so that the resulting coefficients of $\pi’(x)$ are again $(k,n)$ shares. See the protocol below.

#### **Protocol**: Multiplication of Shares

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

- $a(0) = a$, $s^a_{i} = (i,a(i))$ for all $i \in [n]$
- $b(0) = b$, and $s^b_{i} = (i, b(i))$ analogously
Two shares $s^a_{i}, s^b_{i}$ can be multiplied by

- For all party $i \in [n]$, compute $(i, \pi(i) = a(i) \cdot b(i))$
- For all party $i \in [n]$, compute $(2k,n)$ share of 0 by $(r_{i,1},…, r_{i,n} \gets \Share_{2k,n}(0)$, and then send $r_{i,j}$ from $i$ to $j$, where $r_{i,j} := (j, r_i(j))$ for random $2k$-degree polynomial s.t. $r_i(0) = 0$
All parties locally compute the shares $(i,\pi’(i))$, where

\[\pi'(x) := \pi(x) + \sum_{i} r_i(x)\]All parties jointly perform $\Recon$ using the addition of secret shares to obtain the new shares of $\pi’(0) = a\cdot b$; that is, do the following:

- For all party $i$, $((1,s_{i,1}),…,(n,s_{i,n})) \gets \Share(\pi’(i))$ to all $n$ parties
- All parties locally compute $\Recon_{k,n}$ using shares; that is, party $j$ takes the shares $(s_{1,j}, s_{2,j} …, s_{n,j})$, lets $(x_t, y_t) := (t, s_{t,j})$ for all $t$, and run the Lagrange interpolation using all $(x_t,y_t)$ pairs, and then let $S_j(x)$ be the resulting polynomial.
The value $(j,S_j(0))$ is the new $(k,n)$ share of $a \cdot b$.

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

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

$a$ | $b$ | AND, $c$ |
---|---|---|

$k^a_0$ | $k^b_0$ | $\Enc_{k^a_0}(\Enc_{k^b_0}(k^c_0))$ |

$k^a_0$ | $k^b_1$ | $\Enc_{k^a_0}(\Enc_{k^b_1}(k^c_0))$ |

$k^a_1$ | $k^b_0$ | $\Enc_{k^a_1}(\Enc_{k^b_0}(k^c_0))$ |

$k^a_1$ | $k^b_1$ | $\Enc_{k^a_1}(\Enc_{k^b_1}(k^c_1))$ |

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:

$a$ | $b$ | $c$ |
---|---|---|

$\Enc_{k^a_0}(\Enc_{k^b_0}(k^c_0))$ | ||

$\Enc_{k^a_1}(\Enc_{k^b_1}(k^c_1))$ | ||

$\Enc_{k^a_1}(\Enc_{k^b_0}(k^c_0))$ | ||

$\Enc_{k^a_0}(\Enc_{k^b_1}(k^c_0))$ |

Moreover, when an evaluator is given the above 4 rows and additionally the keys $(k^a_0, k^b_0)$, the evaluator can decrypt exactly 1 row and then obtain $k^c_0$. Since $k^a_0, k^b_0, k^c_0$ 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 $\bot$ 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 $k^a$’s and $k^b$’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$:

- $(\tilde C, \label) \gets \Garble(1^n, C)$
- $\tilde x \gets \label(x)$
- $y \gets \Eval(\tilde C, \tilde x)$

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

\[\set{(\tilde C, \tilde x)} \approx \set{S(1^n, |C|, |x|, C(x))}.\]That is, $S$ simulates the garbling $(\tilde C, \tilde x)$ given only the output $C(x)$.

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

Alice, input $x_1$ | Public computation, circuit $C$ | Bob, private input $x_2$ |
---|---|---|

For each wire $w \in C$, sample wire keys $k^w_b \gets \Gen$ for $b = 0,1$ | ||

For each gate $g \in C$, compute 4 encrypted rows using the corresponding wire keys, and let $\set{\tilde g}_{g\in C}$ be the result | ||

Send $\set{\tilde g}_{g \in C}$ to Alice. For each input wire corresponding to $x_2$, send the garbled input, $\tilde x_2$, to Alice. | ||

Send $x_1$ to Bob | ||

For each input wire corresponding to $x_1$, send the garbled input, $\tilde x_1$, to Alice. | ||

Gate by gate evaluate $\tilde g$’s, and obtain $C(x_1, x_2)$ |

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

## Oblivious Transfer

Alice, sender | Bob, receiver | |
---|---|---|

Input | bits $(a_0, a_1)$ | bit $i \in \bit$ |

Output | nothing | bit $a_i$ |

Security | learns nothing about $i$ | learns only $a_i$ but nothing about $a_{i’}$ for $i’ \neq i$ |

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

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 $(\pk,\sk) \gets \Gen$, lets $\pk_i := \pk$, and samples $\pk_{\bar i}$ uniformly at random. Bob sends $(\pk_0, \pk_1)$ to Alice.
- Alice encrypts $a_j$ with $\pk_j$ and gets ciphertexts $c_j \gets \Enc_{\pk_j}(a_j)$ for $j=0,1$. Alice sends $(c_0, c_1)$ to Bob.
- Bob decrypts $c_i$ using $\sk$ and then gets $a_i$.

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