# Can we construct a simulation sound NIZK (Non Interactive Zero-Knowledge) proof?

A single theorem adaptive non-interactive zero-knowledge proof (P, V) for a language L is a proof system that satisfies

• Completeness: If a string $x \in L$ (and P has the witness), the verifier V will accept with high probability.
• Soundness: If $x \notin L$, the verifier V rejects with high probability.
• Zero-knowledge: there exists a simulator M on input $x \in L$, outputs the ensemble which is computationally indistinguishable with the output of the protocol.

Since it is adaptive, $x$ is chosen based on the common reference string.

Single theorem implies that a common reference string is used to prove a single theorem $x$. If we use same string to prove more than one theorem, zero-knowledge property may not be preserved.

Simulation soundness is defined as given a list of simulated proof's to the adversary, adversary should not be able to produce a valid proof for any theorem $x \notin L$

If there exists a single-theorem adaptive NIZK, can we construct a simulation sound NIZK?

Yes.

1. If there exists a single-theorem adaptive NIZK proof system for NP, then there exists a multi-theorem adaptive NIZK proof system for NP. This was proven in the seminal paper of Feige, Lapidot, and Shamir.

The idea is the following: if you have a single-theorem NIZK proof system for NP, then you have a single theorem NIWI proof system for NP. NIWI (non-interactive witness indistinguishable proofs) are strictly weaker than NIZKs, so this is immediate: the WI property states that the verifier cannot distinguish which witness is used by the prover, when there is more than one witness, and this is trivially implied by zero-knowledge, which states that a simulator can simulate the proof without knowing any witness. Now, if you have a single-theorem NIWI, you have a multi-theorem NIWI. This is because unlike ZK, WI is an indistinguishability notion, and therefore we can use an hybrid argument: suppose a prover performs $n$ sequential NIWI proofs (with the same CRS), either all with witness $w_0$, or all with witness $w_1$. Suppose also that an adversary can distinguish whether $w_0$ or $w_1$ was used in these $n$ proofs, with non-negligible probability. Then there must be one of the proofs for which the distinguishing advantage of the adversary was non-negligible (otherwise, a sum of $n$ negligible advantages would still be negligible), hence this adversary already breaks single-theorem NIWI. This shows that single-theorem NIWI implies multi-theorem NIWI.

Now, if there exists a multi-theorem NIWI and one-way functions (which are implied by single-theorem NIZKs for NP anyway), then there exists a multi-theorem NIZK. The idea is to artificially add a second witness that can be used to perform the proof honestly; this second witness will only be used by the simulator. Namely, add to the CRS a random bitstring $y$ of length $2k$, for some security parameter $k$, and instead of proving a statement $S$, prove "either $S$ is true, or I know a string $x$ of length $k$ such that $y = \mathsf{PRG}(x)$" (PRG is a pseudorandom generator, whose existence is implied by any one-way function). In any real run of the protocol, no such $x$ exists, so the proof remains the same (it shows that $S$ is true); but to simulate the protocol, the value $y$ added to the CRS is computed as $y = \mathsf{PRG}(x)$ for a short $x$, and $x$ is given to the simulator (by the security of the PRG, this is indistinguishable from the real CRS). The simulator can then use $x$ to simulate the proof, and it cannot be distinguished from the honest prover by the witness-indistinguishable property of the proof system. Hence, the protocol is zero-knowledge.

1. If there exists a multi-theorem adaptive NIZK proof system for NP, then there exists a simulation-sound NIZK proof system for NP. This was shown in the seminal paper on simulation-sound NIZKs.

This is a bit more complex (and in fact, the above paper directly shows that single-theorem NIZK implies simulation sound NIZK). In the simplified scenario of one-time simulation sound NIZKs, however, there is a very simple construction given in Appendix B of this paper: given a word $x$, to prove that there exists $w$ such that $R(x,w) = 1$, prove instead the following: either $\exists w, R(x,w) = 1$, or $\exists r, c = \mathsf{Com}(x;r)$. Here, $c$ is a commitment to $0$ added to the CRS; in honest runs of the protocol, therefore, this proof is equivalent to just showing $\exists w, R(x,w) = 1$. In a simulated proof, however, the simulator will instead generate $c$ as a commitment to $x$. This way, $c$ allows to cheat in the proof for the word $x$, but cannot help with cheating in the proof for any other word, hence it is easy to see that the proof system remains sound even if the adversary can see a simulated proof for the word $x$. From there, techniques exist to boost one-time simulation soundness to unbounded simulation soundness, but that would bring us a bit too far.

• The transformation of single theorem adaptive NIZK to multi-theorem NIZK works only if the language is NP-complete. If the language is only NP, it does not work. Am I correct? May 15 '18 at 7:32
• I see no reason why this would be the case. Furthermore, you can always work with any arbitrary NP-complete language of your choice in this reduction, and later simply convert your specific NP-language into an instance of this NP-complete language using a Karp reduction. May 15 '18 at 7:56