A Perfect Zero-Knowledge Proof for a Problem Equivalent to
Discrete Logarithm
Webpage for a paper by Oded Goldreich and Eyal Kushilevitz
Abstract
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.
Note
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.