# zbMATH — the first resource for mathematics

A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm. (English) Zbl 0783.68039
Summary: An interactive proof system is called perfect zero-knowledge if the probability distribution generated by any probabilistic polynomial-time verifier interacting with the prover on input theorem $$\varphi$$, can be generated by another probabilistic polynomial-time machine which only gets $$\varphi$$ as input (and interacts with nobody!).
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 proof systems exist in a nontrivial manner (i.e., for languages not in $$BPP)$$. Our results extend to the logarithm problem in any finite Abelian group.

##### MSC:
 68P25 Data encryption (aspects in computer science)
Full Text: