eprint.iacr.org will be offline for approximately an hour for routine maintenance again at 10pm UTC on Wednesday, April 17.

Paper 2020/1160

Characterizing Deterministic-Prover Zero Knowledge

Nir Bitansky and Arka Rai Choudhuri


Randomness is typically thought to be essential for zero knowledge protocols. Following this intuition, Goldreich and Oren (Journal of Cryptology 94) proved that auxiliary-input zero knowledge cannot be achieved with a deterministic prover. On the other hand, positive results are only known in the honest-verifier setting, or when the prover is given at least a restricted source of entropy. We prove that removing (or just bounding) the verifier's auxiliary input, deterministic-prover zero knowledge becomes feasible: - Assuming non-interactive witness-indistinguishable proofs and subexponential indistinguishability obfuscation and one-way functions, we construct deterministic-prover zero-knowledge arguments for $\mathsf{NP}\cap \mathsf{coNP}$ against verifiers with bounded non-uniform auxiliary input. - Assuming also keyless hash functions that are collision-resistant against bounded-auxiliary-input quasipolynomial-time attackers, we construct similar arguments for all of $\mathsf{NP}$. Together with the result of Goldreich and Oren, this characterizes when deterministic-prover zero knowledge is feasible. We also demonstrate the necessity of strong assumptions, by showing that deterministic prover zero knowledge arguments for a given language imply witness encryption for that language. We further prove that such arguments can always be collapsed to two messages and be made laconic. These implications rely on a more general connection with the notion of predictable arguments by Faonio, Nielsen, and Venturi (PKC 17).

Available format(s)
Publication info
Published by the IACR in TCC 2020
zero knowledge
Contact author(s)
nirbitan @ tau ac il
achoud @ cs jhu edu
2020-09-25: received
Short URL
Creative Commons Attribution


      author = {Nir Bitansky and Arka Rai Choudhuri},
      title = {Characterizing Deterministic-Prover Zero Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1160},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1160}},
      url = {https://eprint.iacr.org/2020/1160}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.