Welcome to the resource topic for 2020/141
Title:
Deterministic-Prover Zero-Knowledge Proofs
Authors: Hila Dahari, Yehuda Lindell
Abstract:Zero-knowledge proof systems enable a prover to convince a verifier of the validity of a statement without revealing anything beyond that fact. The role of randomness in interactive proofs in general, and in zero-knowledge in particular, is well known. In particular, zero-knowledge with a deterministic verifier is impossible for non-trivial languages (outside of \mathcal{BPP}). Likewise, it was shown by Goldreich and Oren (Journal of Cryptology, 1994) that zero-knowledge with a deterministic prover is also impossible for non-trivial languages. However, their proof holds only for auxiliary-input zero knowledge and a malicious verifier. In this paper, we initiate the study of the feasibility of zero-knowledge proof systems with a deterministic prover in settings not covered by the result of Goldreich and Oren. We prove the existence of deterministic-prover auxiliary-input honest-verifier zero-knowledge for any \cal NP language, under standard assumptions. In addition, we show that any language with a hash proof system has a deterministic-prover honest-verifier statistical zero-knowledge proof, with an efficient prover. Finally, we show that in some cases, it is even possible to achieve deterministic-prover uniform zero-knowledge for a malicious verifier. Our contribution is primarily conceptual, and sheds light on the necessity of randomness in zero knowledge in settings where either the verifier is honest or there is no auxiliary input.
ePrint: https://eprint.iacr.org/2020/141
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .