3
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – preethi
    May 15, 2018 at 7:32
  • $\begingroup$ 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. $\endgroup$ May 15, 2018 at 7:56
  • $\begingroup$ Is it known that NIZK (for NP-complete languages) implies one-way functions? I am not aware of such a result. (The closest I know is the Crypto 2005 paper "Unconditional Characterizations of Non-interactive Zero-Knowledge," which shows that NIZK implies non-uniform one-way functions.) $\endgroup$
    – user432944
    Sep 29 at 18:33
  • $\begingroup$ I was not aware of this paper, but you might have misread the definition of "non-uniform one-way function" from their work: it means "OWF secure against non-uniform adversaries", which is the standard definition (and also the strongest one). $\endgroup$ Oct 1 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.