Secure multiparty computation is a very new field that has grown very quickly. One of the most interesting things we can currently do with MPC is a paradigm known as MPC in the head. With this, one can construct zero knowledge proofs and signatures from purely symmetric primitives.
Many of the current signatures in the NIST competition use the MPC in the head paradigm or some similar approach, such as VOLE in the head. These methods allow one to convert a multiparty protocol based on communication, into a purely noninteractive zero knowledge proof of some statement.
Background
Zero-knowledge
In a zero knowledge proof, we have two parties, the prover $P$, and the verifier $V$. The prover would like to prove, for some circuit $C$, that $C(w) = 1$, where $w$ is the witness. However, this should be done in zero knowledge, without the verifier learning anything about $w$.
Multiparty Computation
Multiparty computation acts as a different primitive. Here, we have multiple parties $P_1, P_2, \ldots, P_n$. These parties want to together evaluate some function $f(x_1, x_2, \ldots, x_n)$ consisting of inputs from the parties, without any other party learning about the other values $x_1, \ldots, x_n$.
Now, there have been multiple protocols introduced over the years that perform MPC. Garbled Circuits, GMW, BGW, and many others have been introduced to solve this problem.
GMW
The main protocol focused on in here is GMW. In GMW, every input wire value $v$ is split into $n$ secret shares such that $a_1 \oplus a_2 \oplus \ldots \oplus a_n = v$. Now to evaluate gates, we proceed as follows:
- NOT gate: Requires no interaction, just flip your bit $a_i$.
- XOR gate: Requires no interaction, just xor the two shares of those wires $a_i \oplus a_j$.
- AND gate: Requires interaction. One party uses oblivious transfer to send all possible end gate shares to the other parties, who then pick.
MPCitH
The original formulation of MPC in the head given in [IKOS07] involved an arbitrary protocol $\Pi$ which satisfies the MPC functionality of some circuit $f$.
Say we want to prove $C(w) = 1$. Let us split the witness $w$ into shares $x_1, x_2, \ldots, x_n$. Now consider the function $$ f: (x_1, x_2, \ldots, x_n) \mapsto C(x_1 \oplus x_2 \oplus \ldots \oplus x_n)$$
Notice that evaluating $\Pi_f$ in MPC with shares of the witness will evaluate to $1$.
Now the key idea is to have the prover emulate the MPC "in their head". The prove will split this witness into shares, and run the protocol $\Pi_f$ by themselves.
Now, to proving that $C(w) = 1$ amounts to showing that this MPC protocol is well formed and ran properly. However, if the prover sends over all the transcripts from the protocol to the verifier, the verifier can reconstruct $w$, which is no longer zero knowledge!
However, if the prover shows $k < n$ of the transcripts, the verifier can get "some faith" in the prover that this MPC protocol ran correctly. Repeating this over and over, the probability the prover cheated within the protocol will be small enough for the verifier guarantee the prover did not cheat.
So the protocol proceeds as follows:
- The prover creates random shares $x_1, \ldots, x_n$ of $w$. They then emulate $\Pi_f$ on the shares, and create transcripts $t_1, \ldots t_n$ of the $n$ players. The prover then commits to the transcripts.
- The verifier chooses $k$ random players $i_1, \ldots i_k \in \{1, \ldots, n\}$ and sends it to the prover.
- The prover opens the corresponding transcript commitments $t_{i_1}, \ldots, t_{i_k}$.
- Finally, the verifier accepts if all the correct transcripts were opened, the final output of all the transcripts is $1$, and all the transcripts are consistent with each other.
Preprocessing
One of the most useful constructs for MPC is preprocessing, which allows us to improve the efficiency of the previous protocol. In the previous model, the prover has to compute an MPC in their head, which could take a large amount of computation. With preprocessing, [KKW18] have shown that constructing zero knowledge proofs from MPC in the head can be short and practical, and allow a wide scope of different MPC protocols to be used.
The main improvement comes from allowing the MPC protocol to use preprocessing. This allows the protocol to use more parties and still keep costs low, and therefore produce shorter proofs. Here, instead of having oblivious transfer for AND gates, we can instead provide the parties with some additional information.
For each AND gate, we can preprocess a triple $z = x\cdot y$, where $x$ and $y$ are random bits. We then provide shares $z_i$, $x_i$, $y_i$ to the parties.
Then note that a single party can then compute
$$s_i = (a_i\cdot y_i) \oplus (b_i\cdot x_i) \oplus z_i \oplus y_i \oplus x_i $$
Now the parties can publicly broadcast $s_i$ to reconstruct $s$, and then finally compute the value $s \oplus (a_i\cdot b_i)$.
Now with this preprocessing done, we can evaluate the MPC much faster by using this new MPC protocol $\Pi'_f$. However, there is an issue: if the prover is allowed to add preprocessing, what is stopping the prover from cheating at the preprocessing step?
To do this, we can do a small trick:
- As the prover, we can run this preprocessing to create $n$ MPC instances, and commit to the preprocessing state.
- The verifier then challenges the prover to open all but one of these states.
- On the one unopened MPC instance, the prover simulates the MPC $\Pi'_{f}$.
- The verifier then challenges $k$ of the parties in the MPC.
- The prover opens those $K$ parties, showing the verifier there was no tampering in the MPC.
Importantly, to check correctness, the verifier must also check whether the opened states, when simulated in MPC, evaluate to output $1$.
Signatures
Now, with this we have an interactive zero knowledge proof. The prover sends some commitments to the states, the verifier challenges some of them, and so on. To use this interactive zero knowledge proof to create signatures, we can use the Fiat Shamir transform.
Fiat-Shamir
The Fiat Shamir transform allows one to transform an interactive protocol with random challenges into a noninteractive protocol.
Note here that the verifier always responds with a random challenge. Therefore, instead of a verifier responding with a random challenge, we have the "verifier respond with" the hash of the previous messages. So,
- Prover sends $k$.
- Verifier challenges with $H(k)$.
- Prover responds to challenge.
We can also construct signatures by making a small modification:
- Prover sends $k$.
- Verifier challenges with $H(m || k)$.
- Prover responds to challenge.
Now note that this is noninteractive. The prover can compute $H(k)$ themselves, and so the prover just needs to respond to the "challenge" of $H(k)$. This is the principle behind Schnorr signatures.
Conclusion
This is a pretty recent and very interesting development, especially since many signature schemes are now adopting an MPCitH approach. Interestingly, this also allows us to use fully symmetric key primitives within the MPC, such as AES. Therefore, these schemes can be quite easily made post quantum secure. Along with this, MPCitH can be used for fast zero knowledge proof systems. For example, Ligero uses MPCitH for zero knowledge, allowing a number of privacy related features on the blockchain.