TODO: Add snippets of sample code.
General purpose MPC with active security. These notes are based on two talks by Ivan Damgard at the 5th BIU Winter School. Throughout this document we assume inputs have been shared between n=2 participants, but all results hold for any n > 1.
It might seem weird that these commitments are both statistically binding and hiding, which we know is impossible. However, this hides the fact that the statmenent is only true assuming an ideal dealer (pre-processing phase). Any instantiation of the pre-processing phase makes public key crypto assumptions, so in reality we get information theoretic guarantees only in the online phase of the protocol (not the full protocol).
We refer to shares of x as [x] where each party i \in [n] receives:
Q: Party i has access to shares of [x] and [y] and wants to compute shares of [z] where z=x+y. A: Party i simply computes z_i = x_i + y_i and m(z)_i = m(x)_i + m(y)_i.
To open a share, each party i just broadcasts x_i to all other parties. Now without loss of generality assume that party 1 cheats and instead of x_i it sends x_1 + e thus, the new open value is x' = x + e. The entire point of the online phase of SPDZ is to prevent even an computationally unbounded party from doing this and getting away with it.
So each party i now computes d_i = \alpha_i x' - m(x)_i. It then “commits” to d_i. Once all parties have committed to d_i, each party opens the commitment and reveals d_i. All parties then check if \sum_{i \in [n]} d_i = 0
Completeness: If all parties were honest we would have
\begin{align} d_1 + d_2 &= \alpha(x' - x) &=0 \end{align}
As \alpha \neq 0, we must have x'=x.
Soundness: Now of course the cheating player would not commit to d_1 but some other value d_1 + e' to try and pass the above test. We show that this happens with negligible probability.
\begin{align} d_1 + d_2 + e' &= 0 \\ \alpha(x' - x) + e' &= 0 \\ \alpha(x+ e) - m(x) + e' &= 0 \\ \alpha e - e' &= 0 \end{align}
As \alpha is secret over \Z_q, there q possible combindations of \alpha, e and e' (one for each value of \alpha) such that the above equation holds. Thus the cheating party must guess with probability \frac{1}{q}.
OK! We should be done. The cheating party has been caught but there is one bit we have not clarified. How does each party “commit” to its value d_i ?
To explain commitments, we introduce a new form of sharing of x which we denote as [[x]] where each party i \in [n] receives:
Thus for a single share of x, it stores n MAC values. Note in the [x] scheme, each party just stores a single mac value and a share of a single mac key. During the open phase we each party i \in [n] broadcasts to everyone else x_i and m_{\beta_i}(x)_i. Let x' be the final opened value, each party j also checks if
m_{\beta_j}x' = \sum_{i \in [n]}m_{\beta_j}(x)_i
Completeness: If all parties are honest then x'=x and m_{\beta_j}x' = \sum_{i \in [n]}m_{\beta_j}(x)_i.
Soundness: Without loss of generality say Party one cheated to result in the opening of x' = x_1 + e. We have
\begin{align} m_{\beta_2}(x + e) - m_{\beta_2}(x)_1 - e' - m_{\beta_2}(x)_1 &= 0 \\ \beta_{2} e - e' &= 0 \end{align}
Once again we can see that this happens if party one can guess the value of \beta_2 which happens with probability \frac{1}{q}. Thus this guarantees that with noticeable probability, the opened value has not been tampered with.
Q: Party i has access to shares of [[x]] and wants to compute shares of [[x + \gamma]] for a public constant \gamma.
A: Each party i computes m_{\beta_i}(x)_1 + \gamma\beta_i as their mac of the share under their key. Only a single party (say party 1) computes x_1 + \gamma as their updated share.
To commit to x, the dealer provides the committing party a random value r \xleftarrow{\$}\Z_q and shares [[r]] amongst the other parties. The committer then broadcasts d = x+r to all parties. As r is random and secret, x + r is statistically hiding.
To open the commitment, the partipants open d + [[r]] which is the same as opening x. Note that the commitment is also statistically binding, as by the properties discussed above, the open is guaranteed to open d + r=x.
Every multiplication gate will require each party two open twice to reveal d=x-a and e=y-b for random beaver triples c = ab. To open correctly, each party must commit to a value, which requires the dealer to hand them [[r]]. Openning [[r]] requires n^2 communication and storage and so if we had a lot of multiplication gates this would quite expensive.
Thus the next step is to remove the dependence of number of commitments from the number of multiplication gates in the circuit. Let’s say there are t multiplication gates before the final output gate. Thus we have t'=2t partial opens x_1, \dots, x_{t'}. As these are partial opens we have no idea if there for all i \in [t'] we have x_i = x_i'. Let
z'= \sum_{i=1}^{t'} u^i x_i'
This the batch check we want to do. Assume there exists a shared random value u1. The participants are asked to compute shares of [z] where z=\sum_{i=1}^{t'} u^i x_i. Note as this is a linear combination each party can perform local operations on their shares to compute this. Now we require each party to do a full authenticated open as described above, which guarantees participants open z.
Now all parties checks that accept the partial opens if and only if z - z' = 0. As z - z' is a degree t' polynomial, the probability of sampling a root is at most \frac{t}{p} by Schwarz-Zippel.
Once the partial opens are accepted, the servers can reliably use the shares of the output to do one more full authenticated open to get what they want.
We will discuss how this randomeness is selected later.↩︎