- 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).
Category / Keywords: foundations / zero knowledge Original Publication (in the same form): IACR-TCC-2020 Date: received 23 Sep 2020, last revised 23 Sep 2020 Contact author: nirbitan at tau ac il,achoud@cs jhu edu Available format(s): PDF | BibTeX Citation Version: 20200925:184612 (All versions of this report) Short URL: ia.cr/2020/1160