Consider that we want to deal with
\[(y_1, \cdots, y_m) = f(x_1, \cdots, x_n)\]
Similar to ideas in ZKP, we first write \(f\) as an arithmetic circuit, composed of addition, multiplication, constant addition, scalar multiplication. Here, we work over \(\mathbb{F}_q\).
So we wish to deal with the four operations, but in an MPC setting.
We first consider a two-party setting. In this case, for each variable \(x\), the two parties \(P_1, P_2\) have a share \(x_1, x_2\) such that \(x = x_1 + x_2\). Then, addition, constant addition, scalar multiplication can be handled as follows due to linearity.
This implies that the hardest part to deal with is the multiplication.
To deal with this, a third party, a dealer \(D\), provides a Beaver triple sharing, i.e.
such that
\[(a_1 + a_2)(b_1 + b_2) = (c_1 + c_2)\]
such Beaver triples are assigned for each and every multiplication gate.
To deal with a multiplication \(z = x \cdot y\) - consider \(P_1, P_2\) have
\[x = x_1 + x_2, \quad y = y_1 + y_2\]
we can compute
\[z = (x - a + a)(y - b + b) = (x - a)(y - b) + (x - a) b + a (y-b) + ab\]
so we can have \(P_1, P_2\) each compute
\[u_i = x_i - a_i, \quad v_i = y_i - b_i\]
then share it with each other, then have \(u = u_1 + u_2\), \(v = v_1 + v_2\), then
\[z_1 = uv + ub_1 + va_1 + c_1, \quad z_2 = ub_2 + va_2 + c_2\]
leading to \(z_1 + z_2 = z\) as desired.
Here, we see that the communication complexity depends on the number of multiplication gates. For easier writing, we can abstract away this protocol as follows.
For any \(x \in \mathbb{F}_q\), we denote \([x]\) by \((x_1, x_2)\) such that \(x_1 + x_2 = x\). We note that \(P_i\) holds \(x_i\).
The protocol can be written as a combination for various subprotocols.
We also write dealer's protocol - a random sharing \([x] = (x_1, x_2)\) can be created by choosing \(x_1\) at random and setting \(x_2 = x - x_1\). The dealer has the following subprotocols.
The Beaver "2.5"-party Protocol works as follows: of course, addition, constant addition, scalar multiplication works in the most natural way as we defined above. The other subprotocols are
To make this protocol secure when at most one of \(P_1, P_2, D\) are corrupt, we use authenticated sharings. Authenticated sharing \([[x]]\) consists of three ordinary sharings, \(([x], [x^{(1)}], [x^{(2)}])\), which is valid if \(x^{(1)} = K^{(1)}x\) and \(x^{(2)} = K^{(2)}x\) holds. All subprotocols remain the same, although \([[z]] \leftarrow [[x]] + c\) requires \([z^{(1)}] \leftarrow [x^{(1)}] + c[K^{(1)}]\) and \([z^{(2)}] \leftarrow [x^{(2)}] + c[K^{(2)}]\).
The idea behind is that if one player is malicious, the other could end up with values \(x + \delta\) and \(x^{(i)} + \delta^{(i)}\) when it was supposed to end up with \(x\) and \(x^{(i)}\). The verification will check
\[K^{(i)}(x + \delta) = x^{(i)} + \delta^{(i)}\]
which would hold with at most \(1/q\) probability since no one knows \(K^{(i)}\) until the end.
The dealer would need to provide additional singleton sharings \([K^{(1)}]\) and \([K^{(2)}]\), and change all sharings provided to an authenticated version of them. (Beaver triples as well) The dealer reliably opens \(K^{(i)}\) with \(P_i\) and \(P_i\) only - as \(P_{3-i}\) does not know \(P_i\), they must participate in the protocol correctly by our previous analysis. The remaining case to deal with is malicious \(D\).
So the dealer gives \(P_1\)
\[a_{11}, \cdots, a_{m1}, b_{11}, \cdots, b_{m1}, c_{11}, \cdots, c_{m1}\]
and gives \(P_2\)
\[a_{12}, \cdots, a_{m2}, b_{12}, \cdots, b_{m2}, c_{12}, \cdots, c_{m2}\]
and they have to check that
\[(a_{k1} + a_{k2}) (b_{k1} + b_{k2}) = (c_{k1} + c_{k2})\]
hold for all \(k\). We wish to guarantee that if \(D\) is corrupt and \(P_1, P_2\) are honest, then if \(P_1, P_2\) finish the protocol without aborting then with overwhelming property \(D\) had to send correct values that pass the check. Also, if one of \(P_1, P_2\) is corrupt and \(D\) is honest, then the verification protocol does not lead to the corrupt party learning about the hoenst party.
This is, actually, exactly same as the usual PLONK-like algorithm with the additional rows added for hiding. Therefore, we only present the algorithm here, as analysis is very similar. Recall that the number of additional rows corresponds to the number of evaluations.
\(D\) chooses \(a_{01}, a_{02}, b_{01}, b_{02}\) such that
\[(a_{01} + a_{02}) (b_{01} + b_{02}) = (c_{01} + c_{02})\]
then \(D\) runs interpolation to find \(A_1, A_2, B_1, B_2\) of degree \(\le m\) such that
\[A_i(k) = a_{ki}, \quad B_i(k) = b_{ki}\]
and computes \(C(X) = (A_1(X) + A_2(X))(B_1(X) + B_2(X))\). \(D\) then chooses \(c_{k1}, c_{k2}\) such that \(C(k) = c_{k1} + c_{k2}\) for \(0 \le k \le 2m\). Then \(D\) sends all \(a_{ki}, b_{ki}, c_{ki}\) values to \(P_i\) accordingly.
Now \(P_i\) can run interpolation once again to recover \(A_i, B_i, C_i\) of degree \(\le m, \le m, \le 2m\). The goal for the \(P_1, P_2\) is to verify the fact that
\[(A_1(X) + A_2(X))(B_1(X) + B_2(X)) = (C_1(X) + C_2(X))\]
to do so, \(P_1\) chooses \(r \in \mathbb{F}_q \setminus \{0, \cdots m\}\) and sends to \(P_2\). Each party computes
\[\alpha_i \leftarrow A_i(r), \quad \beta_i \leftarrow B_i(r), \quad \gamma_i \leftarrow C_i(r)\]
and sends it to the other party - then both verify
\[(\alpha_1 + \alpha_2)(\beta_1 + \beta_2) = (\gamma_1 + \gamma_2)\]
while precise security proofs is much difficult (due to MPC's security definitions and so on) one sees that the \(a_{01}, a_{02}, b_{01}, b_{02}\) is exactly the additional row for zero-knowledge. The dealer's corruption case is also exactly like the soundness proof in ZKP - the usual Schwartz-Zippel arguments work. Indeed, the success probability is at most \(2m/(q-m-1)\).
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe