The knowledge complexity of interactive proof systems. (English) Zbl 0677.68062

The authors note that usually the proof of a theorem uses more knowledge than the statement of the theorem alone. This is important in cryptography where one wants to avoid giving the other party more information than what is stated explicitly and is looking for a protocol that will not allow the other party to extract more knowledge by cheating on the protocol. The authors define zero-knowledge probabilistic interactive protocols of several kinds, all depending on the length of binary codes, which they compare to prior definitions and show that the definitions are not void by providing a zero-knowledge proof, given two integers \(x, y\), for \(y\) to be or not to be a quadratic residue of \(x\) so that any additional knowledge about \(y\) (as e.g., the knowledge of any factor of \(y\)) is strictly more expensive in computer time than the verification of the given statement.


68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
03F07 Structure of proofs
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
94A60 Cryptography
Full Text: DOI Link


[1] Goldwasser S, Micali S, Rackoff C. The knowledge complexity of interactive proof systems. SIAM J Comput, 1989, 18: 186-208 · Zbl 0677.68062
[2] Bellare M, Goldreich O. On defining proofs of knowledge. Advances in Cryptology-CRYPT’92, LNCS, Vol. 740. Berlin: Springer-Verlag, 1992. 390-420 · Zbl 0823.94016
[3] Halevi S, Micali S. More on proofs of knowledge. http://eprint.iacr.org/1998/015
[4] Goldreich O. Foundations of Cryptography-Basic Tools. Cambridge: Cambridge University Press, 2001 · Zbl 1007.94016
[5] Bellare M, Goldreich O. On probabilistic versus deterministic provers in the definition of proofs of knowledge. Electronic Colloquimon Computational Complexity, 2006, 13(136). Available also from http://eprint.iacr.org/2006/359.ps · Zbl 1343.94042
[6] Barak B, Lindell Y, Vadhan S. Lower bounds for non-black-box zero knowledge. In: 44th Annual IEEE Symposium Foundations of Computer Science. IEEE Computer Society, 2003. 384-393 · Zbl 1094.68024
[7] Barak B, Lindell Y, Vadhan S. Lower bounds for non-black-box zero knowledge. J Comput Sys Sci, 2006, 72: 321-391 · Zbl 1094.68024
[8] Bellare M, Jakobsson M, Yung M. Round-optimal zero-knowledge arguments base on any one-way function. In: EUROCRPT’ 97, LNCS, Vol.1233. Berlin: Spring-Verlag, 1997. 280-305
[9] Feige U, Shamir A. Zero knowledge proofs of knowledge in two rounds. In: Proceedings of CRYPTO’89. Berlin: Springer-Verlag, 1989. 526-545 · Zbl 0722.68045
[10] Goldreich O, Oren Y. Definitions and properties of zero-knowledge proof systems. J Crypt, 1994, 7: 1-32 · Zbl 0791.94010
[11] Goldreich O, Krawczyk H. On the composition of zero-knowledge proof systems. SIAM J Comput, 1996, 25: 169-192 · Zbl 0841.68112
[12] Katz J. Which languages have 4-round zero-knowledge proofs. In: Fifth Theory of Cryptography Conference, LNCS Vol. 4948. Berlin: Spring-Verlag, 2008. 73-88 · Zbl 1162.94372
[13] Goldreich O, Kahan A. How to construct constant-round zero-knowledge proof system for NP. J Crypt, 1996, 9: 167-189 · Zbl 0855.68085
[14] Rosen A. A note on constant-round zero-knowledge proofs for NP. In: First Theory of Cryptography Conference (TCC), LNCS 2951. Berlin: Spring-Verlag, 2004. 191-202 · Zbl 1197.94204
[15] Toshiya I, Kouichi S. On the complexity of constant round ZKIP of possession of knowledge. IEICE Trans Fundam, 1993, E76-A: 31-39 · Zbl 0938.68634
[16] Barak B. How to go beyond the black-box simulation barrier. In: 42th Annual Syposium on Foundation of Computing Science. IEEE Computer Society, 2001. 106-115
[17] Barak B. Non-black-box techniques in cryptography. Thesis for the Ph. D. Degree. Weizmann Institute of Science, 2004, 53-102 (http://www.math.ias.edu/boaz/index.html)
[18] Hada S, Tanaka T. On the existence of 3-round zero-knowledge protocol. http://eprint.iacr.org/1999/009. (Final version of [22]) · Zbl 0931.94009
[19] Bellare M, Palacio A. The knowledge-of-exponent assumptions and 3-round zero-knowledge protocol. http://eprint.iacr.org/2003 · Zbl 1104.94043
[20] Lepinski M. On the existence of 3-round zero-knowledge proofs. Thesis for the Degree of Master, Massachusetts Institute of Technology, 2002. (http://citeseer.ist.psu.edu/lepinski01existence.html)
[21] Barak B, Lindell Y. Strict polynomial-time in simulation and extraction. In: 34th STOC, Montréal, Québec, Canada, 2002. 484-493 · Zbl 1192.68343
[22] Li H D, Li B. The existence of 3-round zero-knowledge proof systems for NP. Sci China Ser F-Inf Sci, 2008, 51: 273-282 · Zbl 1137.94007
[23] Blum M. How to prove a theorem so no one else can claim it. In: Proceedings of the International Congress of Mathematicians, California, USA, 1986. 1444-1451
[24] Naor M. On cryptographic assumptions and challenges. In: Proceedings of Advances in Cryptology-CRYPT’2003, · Zbl 1122.94391
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.