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.

68P25 Data encryption (aspects in computer science)
Full Text: DOI
[1] Aiello, W., and J. Hastad, Perfect Zero-Knowledge Languages Can Be Recognized in Two Rounds,Proc. 28th FOCS, 1987, pp. 439-448. · Zbl 0732.68038
[2] Babai, L., Trading Group Theory for Randomness,Proc. 17th STOC, 1985, pp. 421-429.
[3] Babai, L., and L. Kucera, Canonical Labeling of Graphs in Linear Average Time,Proc. 20th FOCS, 1979, pp. 39-46.
[4] Benaloh (Cohen), J. D.; Odlyzko, A. M., Cryptographic Capsules: A Disjunctive Primitive for Interactive Protocols, Advances in Cryptology—Crypto 86 (Proceedings), 213-222 (1987), Berlin: Springer-Verlag, Berlin
[5] Ben-or, M.; Goldreich, O.; Goldwasser, S.; Hastad, J.; Kilian, J.; Micali, S.; Rogaway, P.; Goldwasser, S., Everything Provable Is Provable in Zero-Knowledge, Advances in Cryptology—Crypto 88 (Proceedings), 37-56 (1990), Berlin: Springer-Verlag, Berlin · Zbl 0718.68033
[6] Blum, M.; Micali, S., How To Generate Cryptographically Strong Sequences of Pseudo-Random Bits, SIAM J. Comput., 13, 850-864 (1984) · Zbl 0547.68046
[7] Boppana, R.; Hastad, J.; Zachos, S., Does Co-NP Have Short Interactive Proofs?, Inform. Process. Lett., 25, 127-132 (1987) · Zbl 0653.68037
[8] Brassard, G.; Chaum, D.; Crepeau, C., Minimum Disclosure Proofs of Knowledge, J. Comput. System Sci., 37, 2, 156-189 (1988) · Zbl 0656.68109
[9] Brickell, E. F.; Chaum, D.; Damgard, I.; van de Graaf, J.; Pomerance, C., Gradual and Verifiable Release of a Secret, Advances in Cryptology—Crypto 87 (Proceedings), 156-166 (1987), Berlin: Springer-Verlag, Berlin
[10] Chaum, D.; Odlyzko, A. M., Demonstrating that a Public Predicate Can be Satisfied Without Revealing Any Information About How, Advances in Cryptology—Crypto 86 (Proceedings), 195-199 (1987), Berlin: Springer-Verlag, Berlin · Zbl 0636.94011
[11] Chaum, D.; Evertse, J. H.; van de Graaf, J.; Chaum, D.; Price, W. L., An Improved Protocol for Demonstrating Possession of a Discrete Logarithm Without Revealing It, Advances in Cryptology— Eurocrypt 87 (Proceedings), 127-142 (1988), Berlin: Springer-Verlag, Berlin
[12] Chaum, D.; Evertse, J. H.; van de Graaf, J.; Peralta, R.; Odlyzko, A. M., Demonstrating Possession of a Discrete Logarithm Without Revealing It, Advances in Cryptology—Crypto 86 (Proceedings), 200-212 (1987), Berlin: Springer-Verlag, Berlin · Zbl 0638.94013
[13] Even, S.; Goldreich, O.; Lempel, A., A Randomized Protocol for Signing Contracts, Comm. ACM, 28, 6, 637-647 (1985)
[14] Even, S.; Selman, A. L.; Yacobi, Y., The Complexity of Promise Problems with Applications to Public-Key Cryptography, Inform. Control, 61, 159-173 (1984) · Zbl 0592.94012
[15] Fortnow, L, The Complexity of Perfect Zero-Knowledge,Proc. 19th STOC, pp. 204-209, 1987.
[16] Goldreich, O., and A. Kahn, in preparation.
[17] Goldreich, O.; Micali, S.; Wigderson, A., Proofs that Yield Nothing but Their Validity and a Methodology of Cryptographic Protocol Design, J. Assoc. Comput. Math., 38, 1, 691-729 (1991) · Zbl 0799.68101
[18] Goldreich, O., and Y. Oren, On the Cunning Power of Cheating Verifiers: Some Observations about Zero-Knowledge Proofs, in preparation.
[19] Goldwasser, S.; Micali, S., Probabilistic Encryption, J. Comput. System Sci., 28, 2, 270-299 (1984) · Zbl 0563.94013
[20] Goldwasser, S.; Micali, S.; Rackoff, C., The Knowledge Complexity of Interactive Proof Systems, SIAM J. Comput., 18, 1, 186-208 (1989) · Zbl 0677.68062
[21] Goldwasser, S., and M. Sipser, Private Coins vs. Public Coins in Interactive Proof Systems,Proc. 18th STOC, 1986, pp. 59-68.
[22] Hastad, J., Psuedo-random Generators Under Uniform Assumptions,Proc. 22nd STOC, 1990, pp. 395-404.
[23] Impagliazo, R., L. A. Levin, and M. Luby, Pseudorandom Generation from One-Way Functions,Proc. 21st STOC, 1989, pp. 12-24.
[24] Impagliazo, R.; Yung, M.; Pomerance, C., Direct Minimum-Knowledge Computations, Advances in Cryptology—Crypto 87 (Proceedings), 40-51 (1987), Berlin: Springer-Verlag, Berlin
[25] Kaliski, B. S., Elliptic Curves and Cryptography: A Pseudorandom Bit Generator and Other Tools. Ph.D. Thesis, MIT/LCS/TR-411, Massachusetts Institute of Technology, 1988.
[26] Kucera, L., Canonical Labeling of Regular Graphs in Linear Average Time,Proc. 28th FOCS, 1987, pp. 271-279.
[27] Kushilevitz, E., Perfect Zero-Knowledge Proofs, Master Thesis, Technion, 1989 (in Hebrew). A translation in English of the subsection concerning the parallel execution of the basic protocol is available from the author.
[28] Naor, M.; Brassard, G., Bit Commitment Using Pseudorandomness, Advances in Cryptology—Crypto 89 (Proceedings), 128-136 (1990), Berlin: Springer-Verlag, Berlin
[29] Odlyzko, A., Discrete Logarithm in Finite Fields and Their Cryptographic Significance, Proc. Eurocrypt 84, 224-314 (1985), Berlin: Springer-Verlag, Berlin
[30] Oren, Y., On the Cunning Power of Cheating Verifiers: Some Observations about Zero-Knowledge Proofs,Proc. 28th FOCS, 1987, pp. 462-471.
[31] Rosser, J.; Schoenfield, L., Approximate Formulas for Some Functions of Prime Numbers, Illinois J. Math., 6, 64-94 (1961)
[32] Shamir A., IP=PSPACE,Proc. 31st FOCS, 1990, pp. 11-15.
[33] Tompa, M., and H. Woll, Random Self-Reducibility and Zero-Knowledge Interactive Proofs of Possession of Information,Proc. 28th FOCS, 1987, pp. 472-482.
[34] Yao, A. C., Theory and Applications of Trapdoor Functions,Proc. 23rd FOCS, 1982, pp. 80-91.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.