A Gentle Introduction to the MPC-in-the-Head Transformation

Written by Giorgio Dell'Immagine on Feb 20, 2025

In this post, we will examine one of the most interesting ways to construct zero-knowledge proofs: the MPC-in-the-Head transformation. This was first introduced in the 2007 paper Zero-knowledge from secure multiparty computation, and it is often referred to as the IKOS transformation, from the initials of the authors of the paper.

The transformation allows us to construct a zero-knowledge proof system from any MPC protocol, which is treated as a black-box. We will explore the intuition behind MPC protocols and the original transformation technique, and discuss how this construction can be applied to develop post-quantum signature schemes.

What is MPC?

Secure Multi-Party computation (MPC) is a cryptographic technique that allows multiple parties to securely compute a function collectively. Each party holds its own private input, and the goal is to compute a designated function over all the private inputs. At the end of the protocol, each party should learn only the output of the function and nothing else.

A simple protocol

A common example used to illustrate MPC protocols is the following: suppose the employees of a company want to know the average salary of the company without revealing their own. In this setting, every employee holds a private input $S_i$, which represents their salary. Let’s assume that all computations are performed over some prime field $\mathbb{F}_p$: we want to build a protocol that computes the sum of the private inputs of all the employees over the field $\mathbb{F}_p$. The average salary can then be computed afterwards in the clear by dividing the sum by the number of employees.

The protocol is divided into three steps: inputs sharing, local accumulation, and reconstruction.

Consider employee number $1$ which holds their private salary $S_1$. They first compute an additive secret sharing of $S_1$, which means that the value is “split” into $n$ shares $$ [ S_1 ]_1, [ S_1 ]_2, \ldots, [ S_1 ]_n $$ which are just field elements chosen so that their sum is equal to the original value $S_1$. $$ S_1 = [ S_1 ]_1 + [ S_1 ]_2 + \ldots + [ S_1 ]_n $$

In practice, this is computed by sampling the first $n-1$ shares uniformly at random from $\mathbb{F}_p$, and then computing the last share as $$ [ S_1 ]_n = S_1 - \sum _{i=1}^{n-1} [ S_1 ]_i $$ It is easy to see that if the first $n-1$ shares are chosen uniformly at random from $\mathbb{F}_p$, then the final share is also uniformly distributed over $\mathbb{F}_p$ (indeed, this would be true also if at least one of the first $n-1$ shares was chosen uniformly at random). This is a simple way to achieve perfect privacy: if an adversary sees up to $n-1$ shares, they learn nothing about the original value $S_1$.

Local accumulation

In this step, every employee sends their $i$-th generated share to the $i$-th party. Focusing on employee number $1$, they will send $[ S_1 ]_2$ to the employee number $2$, $[ S_1 ]_3$ to the employee number $3$, and so on. The employee number $1$ will then receive the following shares from the other employees $$ [ S_2 ]_1, [ S_3 ]_1 \ldots, [ S_n ]_1 $$ plus they have access to the share $[ S_1 ]_1$ which they generated themselves.

They can now accumulate locally every share $$ [ S ]_1 = [ S_1 ]_1 + [ S_2 ]_1 + \ldots + [ S_n ]_1 $$ and then send $[ S ]_1$ to every other employee.

Reconstruction

At the end, every employee has access to the shares accumulated by every other employee $$ [ S ]_1, [ S ]_2, \ldots, [ S ]_n $$ so that each employee can independently reconstruct the final output by summing all the shares $$ S = [ S ]_1 + [ S ]_2 + \ldots + [ S ]_n $$ which corresponds to the sum of all the private inputs. To see why this works, notice that, in this secret sharing scheme, shares are additively homomorphic: if we sum two shares of two secrets, we get a share of the sum of the secrets.

In this specific case, it is possible to employ this very simple protocol because the function we want to collectively compute is linear in the private inputs. In general, MPC protocols can be used to compute any function, but they require more sophisticated techniques. A great starting point to learn about MPC constructions is this review paper by Y. Lindell.

Properties of MPC protocols

There are two main properties that an MPC protocol should satisfy:

Correctness: the output of the protocol should be the correct output of the function, the same as if the parties had computed it in the clear.
Privacy: the parties should not learn anything about the private inputs of the other parties, and should learn only the output of the function.

In general, we assume that some parties may be corrupted, meaning that an adversary may see their inputs and messages exchanged. We say that an MPC protocol is $t$-Private if it satisfies privacy even if up to $t$ parties are corrupted; if $t + 1$ parties are corrupted, then there could be some information leakage about the private inputs of the honest parties. In this basic transformation, we require only $2$-Privacy—meaning that privacy is maintained even if up to two parties are corrupted.

Additionally, the MPC protocol is only required to be secure in the semi-honest model, which means that it is assumed that the parties follow the protocol honestly, but may try to learn as much information as possible while doing so. The parties in this model are often called honest but curious. For example, the simple protocol described above indeed assumes that the parties follow the protocol honestly: if a party deviates from the protocol, then the output could be computed incorrectly.

The original IKOS transformation treats the underlying MPC protocol as a black-box, however we should point out that in more efficient schemes, the MPC protocol is specifically designed to yield an efficient zero-knowledge proof scheme when the transformation is applied.

The MPC-in-the-Head transformation

The goal of this transformation is to take any MPC protocol with the properties described above, and use it to build a zero-knowledge proof scheme for a relation $\mathcal{R}$ in $NP$. In this new setting, there are two parties: the prover and the verifier. The prover wants to convince the verifier that they know a witness $w$ such that $(x, w) \in \mathcal{R}$, where $x$ is a public input. As an example, $\mathcal{R}$ could be the pre-image relation of the SHA-256 hash function: $$ \mathcal{R} = \lbrace (x, w) \mid \text{SHA-256}(w) = x \rbrace $$

The prover splits the witness $w$ into an additive sharing $w_1, w_2, \ldots, w_n$ such that the sum of the shares is equal to the original witness: $$ w_1 + w_2 + \ldots + w_n = w $$ Then, the prover simulates “in its head” the MPC protocol: picture it as directing a little play between $n$ sock-puppets, where each character represents one of the parties. These puppets interact by following a scripted dialogue that mirrors the steps of the MPC protocol. The $i$-th party holds $w_i$ as their private input, and all the parties hold the public input $x$. The function computed by the simulated parties just returns $1$ if the relation is satisfied and $0$ otherwise: $$ f(x, w_1, w_2, \ldots, w_n) = \begin{cases} 1 &\text{if } \mathcal{R}(x, w_1 + w_2 + \ldots + w_n) \\ 0 &\text{otherwise} \end{cases} $$ Notice that, since the relation $\mathcal{R}$ is in $NP$, it admits a polynomial-time verification algorithm. Thus, the function $f$ is efficiently computable, since it just sums the local witnesses and then checks the relation. To give a concrete example, the function that the MPC protocol computes for the SHA-256 pre-image relation is the following:

def f(x, w_1, w_2, ..., w_n):
    w = w_1 + w_2 + ... + w_n
    if SHA256(w) == x:
        return 1
    else:
        return 0

In practice, this function is often represented as an arithmetic circuit $\mathcal{C}$ over some finite field.

After simulating the MPC protocol, the prover generates a view for each party, where each view consists of the party’s private input and the messages sent and received by the party during the simulated execution of the protocol. For example, if party $i$ sends a message $m$ to party $j$, then

the view of party $i$ will contain an outward message $\text{out}(j, m)$, and
the view of party $j$ will contain an inward message $\text{in}(i, m)$.

Now, the prover sends commitments for all party views to the verifier. A commitment scheme is a cryptographic primitive that allows a party to commit to a value, without revealing it, and later open the commitment to reveal the value. A commitment $Comm(x)$ should be hiding, meaning that it does not reveal any information about $x$, and binding, meaning that it is infeasible to later reveal another value $y \neq x$ and convince the verifier that it is the valid opening for $Comm(x)$. As a concrete example, a simple commitment scheme could be implemented from a collision-resistant hash function as follows.

def commit(x: bytes) -> bytes:
   nonce = random(16)
   return sha256(x + nonce)

def verify_opening(x: bytes, nonce: bytes, commitment: bytes) -> bool:
   return len(nonce) == 16 and sha256(x + nonce) == commitment

Once the prover has sent commitments to every view, the verifier randomly selects two parties, say $i$ and $j$, and asks for their views to be opened. The prover then sends the chosen views in the clear to the verifier.

The verifier at this point learns the two inputs $w_i$ and $w_j$, and the entire transcript of the messages sent and received by the parties $i$ and $j$. The verifier checks the following:

The views are valid openings with respect to their corresponding commitments.
The parties $i$ and $j$ have followed the protocol honestly.
The two views are consistent, which means that for each message exchanged between the two parties, both transcripts agree on its content.
The opened views agree that the output of the function is $1$.

Soundness of the scheme is directly based on the correctness of the underlying MPC protocol. Assuming that the MPC protocol satisfies perfect correctness, if the prover honestly simulates the proocol, then the output will be correct. However, if the prover tries to cheat, then it has to do so in at least one party, so there will be at least one pair of views that are not consistent with respect to an honest execution. The probability that the verifier selects the inconsistent pair is $1 / {{n}\choose{2}}$, meaning that the probability that the prover can successfully cheat is $$ \varepsilon = 1 - 1 / {n\choose{2}} $$ As usual when dealing with zero-knowledge proofs, after doing enough repetitions, the soundness error can be made exponentially small.

Zero-knowledge is instead directly based on the Privacy of the underlying MPC protocol. It suffices to see that the verifier knows at most the views of two parties, and since the underlying MPC protocol is assumed to be $2$-Private, the verifier learns nothing about the private inputs of the other parties. Also notice that learning $w_i$ and $w_j$ does not give the verifier any information about $w$.

Removing interaction

This protocol has the very nice property of being public-coin, which means that the verifier does not have any active role, and just samples random challenges and sends them to the prover. This means that the protocol can be rendered non-interactive using the standard Fiat-Shamir transformation.

Improvements

Although the protocol described above is quite inefficient in practice, later concrete instantiations have greatly improved upon this basic idea. One of the sources for inefficiency is that in practice the prover has to perform many rounds to achieve a reasonably low soundness error. This is due to the fact that the soundness error for one round is quite high, because the verifier only opens two views at the time. As a concrete example, if $n = 8$, then the prover cheats successfully over one round with probability $$ 1 - 1 / {8\choose{2}} \approx 96.4 \text{%} $$

An immediate improvement can be made by building upon an $(n-1)$-Private MPC protocol, such that the prover can safely open to all parties except one, without losing zero-knowledge. In this case, the verifier just chooses one party to keep private, and the prover sends openings to the views of all the other parties. This improves quite a lot the soundness error, which becomes $$ \varepsilon = \frac{1}{n} $$ as the prover can cheat only in the party that is chosen by the verifier, which occurs with probability $1/n$. As before, with $n = 8$ the probability of cheating successfully is $$ \frac{1}{8} \approx 12.5 \text{%} $$

Applications to post-quantum signatures

The resulting zero-knowledge proof scheme has some interesting characteristics:

If we use an MPC protocol that is post-quantum secure, then the resulting zero-knowledge proof scheme will also be post-quantum secure, since the transformation relies only on simple cryptographic commitments, which can be instantiated using collision-resistant hash functions, e.g., SHA3.
The proof size is linear in the size of the circuit with very small constants, making it efficient in practice for circuits with a small amount of gates.
Both the prover and verifier time complexities are linear in the size of the circuit, and essentially they do the same amount of work.

This makes the scheme particularly interesting for building post-quantum signatures. In general, to construct a signature scheme from a zero-knowledge proof, we choose a one-way function $H$, which is a function for which it is easy to compute $H(x)$, but given an output $y$ it is hard to find an input $x$ such that $H(x) = y$. The standard example is to take $H$ to be a cryptographic hash function, and then take the relation $\mathcal{R}$ to be the pre-image relation of $H$.

To generate a key pair, the private key $x$ is sampled randomly, and the public is computed as the hash value $y = H(x)$.
To sign a message $m$, the signer proves that they know a private $x$ such that $H(x) = y$, where $y$ is the public key, using the zero-knowledge proof scheme. We can include the message $m$ efficiently in the proof by exploiting the Fiat-Shamir transformation. We let the first message sent by the prover to the verifier to be the message $m$, and then the normal protocol proceeds as before. In this way we obtain a sort of “message-dependent proof of knowledge”, where the signer proves that they know a pre-image of the public key, but the proof is only valid for a specific message $m$. Notice that every challenge sampled by the verifier is dependent on the first message $m$, so the signature is not reusable for other messages.
Finally, to verify a signature for a message $m$, the verifier first checks that the message included in the proof matches $m$, and then verifies the associated zero-knowledge proof.

Several concrete signature schemes have been proposed, such as ZKBoo, Picnic, KKW18 and FAEST. Notably, also the Ligero zero-knowledge proof scheme can also be viewed as an instantiation of an optimized MPC-in-the-Head transformation, and manages to achieve sub-linear proof-size using an MPC protocol which is secure against active adversaries.