A Perfect Zero-Knowledge Proof for a Problem Equivalent to Discrete Logarithm

Webpage for a paper by Oded Goldreich and Eyal Kushilevitz


An interactive proof is called perfect zero-knowledge if the probability distribution generated by any probabilistic polynomial-time verifier interacting with the prover on input a theorem, can be generated by another probabilistic polynomial time machine which only gets as input (and interacts with nobody!). In this paper we present a perfect zero-knowledge proof system for a decision problem which is computationally equivalent to the Discrete Logarithm Problem. Doing so we provide additional evidence to the belief that perfect zero-knowledge proofs-exist in a non-trivial manner (i.e. for languages not in BPP). Our results extend to the logarithm problem in any finite Abelian group.


This work has appeared in the proceedings of Crypto88 as well as in the Journal of Cryptology (1993). You may try to retreive the conference version from here...

Back to either Oded Goldreich's homepage. or general list of papers.