2025-01-07

Simulation-Extractability, Non-Malleability, SoK

These three concepts are related. Going to try to explore the relationship (with respect to non-interactive zero knowledge) in this note.

Simulation-extractability

High-level: Assume we have some NIZK. An adversary, given access to a simulation oracle, produces a proof $\pi$ for a statement $x$. There should be an extractor that whenever $\pi$ is true, extracts a valid witness for $x$.

Realized my intuition doesn’t specify whether the oracle accepts false statements. If it does, then I think this also implies non-malleability? Maybe? What even is the def of non-malleability?

Note that Amit’s simulation-soundness paper allows queries on false statements, i.e., it doesn’t require $w$ as input.

Formal def: (so far)

Game $\mathcal{G}_{\color{green}\mathsf{strong}}(1^\lambda, R, \mathcal{A})$:

1. $(\mathsf{crs}, \tau) \leftarrow \mathsf{NIZK.SimSetup}(1^\lambda, R)$
2. Run $\mathcal{A}^{\mathsf{NIZK.Sim}(\tau, \cdot)}(1^\lambda, R, \mathsf{crs})$, and let $Q$ be the set $\{ (x, \pi) \}$ of query-response pairs for every query made to $\mathsf{NIZK.Sim}$ by $\mathcal{A}$
3. When $\mathcal{A}$ halts and outputs $(x^*, \pi^*)$, run $\mathsf{NIZK.Ext}(\tau, x^*, \pi^*) \rightarrow w^*$.
4. Output $1$ if $(x^*, w^*) \notin R$, and $(x^*, \pi^*) \notin R$. Otherwise, output $0$.

Game $\mathcal{G}_{\color{orange}\mathsf{weak}}(R, 1^\lambda)$:

1. $(\mathsf{crs}, \tau) \leftarrow \mathsf{NIZK.SimSetup}(1^\lambda, R)$
2. Run $\mathcal{A}^{\mathsf{NIZK.Sim}(\tau, \cdot)}(1^\lambda, R, \mathsf{crs})$, and let $Q$ be the set $\{ (x, \pi) \}$ of query-response pairs for every query made to $\mathsf{NIZK.Sim}$ by $\mathcal{A}$
3. When $\mathcal{A}$ halts and outputs $(x^*, \pi^*)$, run $\mathsf{NIZK.Ext}(\tau, x^*, \pi^*) \rightarrow w^*$.
4. Output $1$ if $(x^*, w^*) \notin R$, and x^* is not the first element of any pair in $Q$. Otherwise, output $0$.

We say a NIZK is $\{ {\color{green}\mathsf{strong}}, {\color{orange}\mathsf{weak}} \}$-simulation-extractable if for all PPT $\mathcal{A}$ there is a negligible $\epsilon$ such that

Groth16

Groth16 is ${\color{orange}\mathsf{weak}}$-simulation-extractable. The original security proof for Groth16¹ showed that if an adversarial prover generates a proof, the elements $(A, B, C)$ of this proof must be linear combinations of the elements in the setup. If we are in a model where the coefficients of these linear combinations are revealed by the prover (e.g., the generic group model as used in ¹), then these coefficients can be used to extract a witness for the statement being proven. It turns out² you can extend this argument to the case where this adversarial prover has a simulation oracle. In this case, it turns out that the only way for the prover to generate accepting proofs is either a) to use linear combinations of the setup (as before), or b) to use a rerandomization of the elements given from the simulation oracle. As ² show, the prover cannot mix a) and b). This implies that the if the prover prover generates a new acceptive proof, either this proof is extractable using the original extraction strategy in ¹, or it is a rerandomization of a simulated proof.

Groth16 is not ${\color{green}\mathsf{strong}}$-simulation-extractable. Look at the equality which the verifier checks:

In view of this, given a proof $([A]_1, [B]_2, [C]_1)$, it is possible to set $[A']_1 = r[A]_1$, $(r)^{-1}[B']_2 = [B]_2 + s[\delta]_2$, and $[C']_1 = [C]_1$. This new proof $([A']_1, [B']_2, [C']_1) \neq ([A]_1, [B]_2, [C]_1)$ still satisfies the verification equations, since $[A']_1 \cdot [B']_2 = [A]_1 \cdot [B]_2$. Notice above that if it is possible to rerandomize proofs, it is possible to win against the ${\color{green}\mathsf{weak}}$-simulation-extractability game.

Non-malleability

Todo: write this section. See ³ for relationship between non-malleability and simulation-extractability. See also ⁴

Signature of Knowledge

Todo: write this section.