Secure Multi-Party Computation

Suppose we have a function $f$ with $n$ inputs and $m$ outputs. The goal of MPC is to develop a protocol for $N$ parties where every input is submitted by one party and every output is obtained by some parties. There are some informal descriptions of the security:

• privacy: no party learns anything about any other party's inputs (except for information that is inherently revealed by the outputs);

• soundness: honest parties compute correct outputs (if they compute any output at all);

• input independence: all parties must choose their inputs independently of the other parties' inputs.

And there are assumptions

• cryptographic assumptions

• number of corrupt parties

• communication: synchronous or asynchronous

• type of corruption: malicious or honest-but-curious (of the things to do), static or adapted (of which party to corrupt)

Intro: Beaver’s protocol

The beaver’s protocol securely computes the output of the arithmetic circuits over $\mathbb{F}_q$ among $2$ parties.

Basic Idea

To achieve privacy, it is an intuition to split the key value into several parts, and distribute them to different parties. We use $[x]$ to denote a share of value $x$ , meaning $[x]=(x_1,x_2)$ where $x=x_1+x_2$ . And define

• $[x]+[y]=(x_1+y_1,x_2+y_2)$

• $c[x]=(cx_1,cx_2)$

• $[x]+c=(x_1+c,x_2)$ (I am curious whether it is more secure to split the constant randomly, not just always add it on one side.)

The add gate, scalar multiplication gate and constant add gate is linear; the tow parties can compute independently. The multiplication gate needs the dealer to generate a random Beaver triple sharing : $([a],[b],[c])$ where $c=ab$ .

Suppose the two parties are computing the multiplication of $[x]$ and $[y]$ . The dealer sends $a_i,b_i$ to $P_i$ each, and the two parties compute $[u]=[x]-[a]$ and $[v]=[y]-[b]$ . Then the two parties open the shares $[u],[v]$ to each other so that they both know $u=x-a,v=y-b$ , and uses their own share to compute

For example, the party $i$ computes $z_i=uv\times\mathbf{1}_{i=1}+ub_i+va_i+c_i$ and we can verify that $z_1+z_2=uv+ub+ua+ab=xy$ .

And the dealer would split the input $x=x_1+x_2$ and distributes them to $P_i$ ’s.

Maliciously secure Beaver’s protocol

A malicious participant would send a wrong number when opening their shares. We introduce authenticated sharing $\llbracket x \rrbracket:=([x],[x^{(1)}],[x^{(2)}])$ where $P_i$ has $(x_i,x^{(1)}_i,x^{(2)}_i)$ and summing over $i$ reveals the original content $(x,x^{(1)},x^{(2)})$ . Also there is $[K^{(1)}],[K^{(2)}]$ that the dealer randomly generalize and distribute to the parties during the setup. The authenticated sharing is valid iff $x^{(1)}=K^{(1)}x$ , $x^{(2)}=K^{(2)}x$ .

The intuition is, if any one of the two parties are corrupt, they will never know the other’s secret $K$ , thus cannot make up a fake authenticated sharing. The $K$ here serves as a MAC with homomorphic properties, and is initialized during setup phase, where the dealer sends the sharing to each party using $K^{(i)}$ .

Thus, simply replace $[x]$ by $\llbracket x \rrbracket$ we shift our protocol to a secure version w.r.t. corrupt parties.

Keeping the dealer honest

However, the dealer can be malicious. Although it cannot know the data computed, it can:

• offer an invalid sharing or wrong keys such that $x^{(i)}\not=K^{(i)}x$

• inappropriately split the input $x\not=x_1+x_2$

• provide incorrect Beaver’s triple $([a],[b],[c])$

The first one is easily defenced through checking, and I suppose that the second one is not a problem, because the protocol is in fact computing with a replaced input. We consider the third problem and suppose the dealer sends $a_{ij},b_{ij},c_{ij}$ where $i=1,2$ and $j=1,2,\dots,m$ .

The dealer will do additional computations to prove that for every $j$ , $(a_{1j}+a_{2j})(b_{1j}+b_{2j})=c_{1j}+c_{2j}$ using interpolation. The dealer randomly picks $a_{j0},b_{j0},c_{j0},j=1,2$ such that $(a_{10}+a_{20})(b_{10}+b_{20})=c_{10}+c_{20}$ and interpolates a degree- $m$ polynomial $A_1(X),A_2(X)$ such that $A_i(j)=a_{ij},i=1,2,j=0,\dots,m$ . Similar for $B$ , and $C(X)=(A_1(X)+A_2(X))(B_1(X)+B_2(X))$ . Then for $k=m+1,\dots,2m$ , randomize $c_{1k}+c_{2k}=C(k)$ .

Each of the participant $P_i$ receives $a_{ik},b_{ik},k=0,\dots,m$ and $c_{ik},k=0,\dots,2m$ , and interpolates the polynomials $A_i,B_i,C_i$ . The next step, the participants run an argument of proving the polynomial equals $0$ , all done by sending a random number and reveal the evaluations to each other. To be precise,

• Party $P_1$ randomly chooses $r \in \mathbb{Z}_q \setminus \{0, \ldots, m\}$ and sends it to $P_2$ .

• Party $P_2$ verifies that $r \in \mathbb{Z}_q \setminus \{0, \ldots, m\}$ ; if not, $P_2$ aborts the protocol.

• Each party $P_i$ (for $i = 1, 2$) sends to the other party

  $$\alpha_i \leftarrow A_i(r), \quad \beta_i \leftarrow B_i(r), \quad \gamma_i \leftarrow C_i(r).$$

• Each party locally checks whether

  $$(\alpha_1 + \alpha_2)(\beta_1 + \beta_2) = (\gamma_1 + \gamma_2)$$

  holds. If not, the party aborts the protocol.

So the soundness probability of the dealer to be corrupt is about $\frac{2m}{q}$ .

Further, we should use simulator as in ZKP to prove that with a corrupted $P_i$ , the $P_i$ cannot learn anything from $P_{3-i}$ .

Garbled Circuits

A garbling scheme consists of four algorithms; the first is non-deterministic while others are deterministic:

• $\mathsf{Garble}$ : $(\mathcal{F}, e, d) \leftarrow \mathsf{Garble}(f)$

• $\mathsf{Encode}$ : $\mathcal{X} \leftarrow \mathsf{Encode}(e, {x})$

• $\mathsf{Eval}$ : $\mathcal{Y} \leftarrow \mathsf{Eval}(\mathcal{F}, \mathcal{X})$

• $\mathsf{Decode}$ : $\{{y},\bot\} \leftarrow \mathsf{Decode}(d, \mathcal{Y})$

Correctness: For all $f, (\mathcal{F}, e, d) \leftarrow \mathsf{Garble}(f), {x}$ ,

Intuitive security goals:

• Obliviousness : $\mathcal{F}, \mathcal{X}$ reveals nothing about $x$ . This is about preventing the evaluator from gaining the input.

• Authenticity : Given $\mathcal{F}, \mathcal{X}$ it is of negligible probability for all PPT adversaries to find $\mathcal{Y}'\not=\mathsf{Eval}(\mathcal{F},\mathcal{X})$ that decodes to a value (not a $\bot$ ). This is about preventing the evaluator from forging the result.

• Output simulatability : $\mathcal{Y}$ can be efficiently computed by $f(x)$ and $d$ .

Here is a scheme of outsourcing computation: suppose Alice uses Bob’s computation resources to compute $f(x)$ . First Alice generates $(\mathcal{F}, e, d) \leftarrow \mathsf{Garble}(f)$ ; then sends $\mathcal{F}$ to Bob, and keeps $e,d$ herself. When she wants to compute, she has $\mathcal{X} \leftarrow \mathsf{Encode}(e, {x})$ and sends $\mathcal{X}$ to Bob, where Bob computes $\mathcal{Y} \leftarrow \mathsf{Eval}(\mathcal{F}, \mathcal{X})$ and returns to Alice. Then Alice can decode.

Note that Alice should generate a garbled circuit on different inputs and the same boolean circuit. If we use the same GC for different computation tasks, then a honest-but-curious party would know some relations of the two inputs through comparing the encoded $\mathcal{X}$ ; or some information about $e$ . We should always keep in mind that the encoding algorithm is deterministic.

Formal definition of the security goals

Obliviousness. For $b = 0, 1$ , we have experiment $\mathsf{Exp}_b$ :

• Adversary submits $(f, \mathbf{x}^{(0)}, \mathbf{x}^{(1)})$

• Challenger computes:

  $$(\mathcal{F}, e, d) \leftarrow \mathsf{Garble}(f), \quad \mathcal{X} \leftarrow \mathsf{Encode}(e, \mathbf{x}^{(b)})$$

  and sends $(\mathcal{F}, \mathcal{X})$ to adversary.

• Adversary outputs $\hat{b} \in \{0,1\}$ , let $W_b$ be the event that the adversary outputs $1$ .

A garbling scheme is oblivious iff for every PPT adversary, the game has a negligible advantage defined by $|\Pr[W_0] - \Pr[W_1]|$ .

Output Simulatability. A garbling scheme is output simulatable if there exists an efficient deterministic algorithm $\mathsf{Reverse}$ such that for every $f$ , every $(\mathcal{F}, e, d) \leftarrow \mathsf{Garble}(f)$ , and every ${x}$ :

$\texttt{Garble0}$ : an implementation of garbling scheme

Suppose the boolean circuit has $n$ variables and $m$ outputs.

where $x$ is the input and $\mathcal{Y}$ is the garbled output. The decoding algorithm is to compare each $Y_j$ to the pair $(Y_j^0,Y_j^1)$ .

Our goal is to establish the algorithm $\mathsf{Eval}$ that with input $\mathcal{F}$ and $\mathcal{X}$ carries out the garbled output.

The garbled circuit $\mathcal{F}$ consists of a function for each gate $g$ , which we will denote by $\mathsf{GateEval}_g$ satisfying

where $I_i^x$ ‘s are the garbled values of input wires and $O^y$ are that of the output wire. For example an AND gate, we have $\mathsf{GateEval}(I_1^u,I_2^v)=O^{\mathbf{1}[u=1\land v=1]}$ . The encoding $\mathcal{G}$ for this gate is called a garbled encoding, which should be used together with a garbled evaluation algorithm $\mathsf{GateEval}$ .

Implementation of garbled encoding

This implementation entails a public key encryption scheme. We index each wire by $I$ and each wire $i$ corresponds to two public keys $(k_i^0,k_i^1)$ as the private encoding. Then consider one gate with inputs wires $i,j$ and output wire $t$ .

where the length of the trailing zeros is the security parameter $\lambda$ . And the garbled circuit is the tuple

with the evaluation algorithm

This algorithm is obviously correct, but requires computations for all $4$ possibilities. Below we propose the point-and-permute method to make it more efficient.

(In fact this method has a constant complexity for all gates; if we construct a big look-up table for the whole circuit, the total time will be exponential!)

More efficient

We have $T=\{0,1\}^\ell$ be our set of tokens and $I$ is the finite set of identifiers that each gate has a unique identifier $i\in I$ . And $H:T\times T\times I\mapsto T$ a hash function. For each wire, the garbling process generates $(A^0,A^1,r)$ as the private encoding such that $A^i$ begins with $i$ . Then consider the gate $i$ with its input private encodings $(A^0,A^1,r),(B^0,B^1,s)$ and the output private encodings $(C^0,C^1,t)$ . We set for $a,b\in\{0,1\}$ ,

Note that And we define the garbled encoding

with the garbled evaluation algorithm

where $a$ is the first bit of $X$ and $b$ is the first bit of $Y$ .

The correctness of the algorithm is one line of formula. When computing, if the first input wire has value $u$ , then the corresponding encoding is $X^u:=A^{u\oplus r}$ , and the same for the second input and the output, say, $Y^v:=B^{v\oplus s}$ and $Z^w:=C^{w\oplus t}$ . Then we have

The random bit here is used to mask the true value. Imagine you send $A^u,B^v$ directly, the evaluator immediately knows the hidden value because $A^u$ has the first bit $u$ , and the same as $B^v$ .

The full protocol