×

Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. (English) Zbl 0799.68101


MathOverflow Questions:

Zero-knowledge proof of positivity

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68P25 Data encryption (aspects in computer science)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Goldwasser S, Micali S, Rackoff C. The knowledge complexity of interactive proof systems. J Comput, 1989, 18: 186-208 · Zbl 0677.68062
[2] Brassard G, Chaum D, Crepau C. Minimum disclosure proofs of knowledge. JCSS, 1988, 37: 156-189 · Zbl 0656.68109
[3] Babai L. Trading group yheory for randomness. In: Proceedings of the 17th ACM Symposium on Theory of Computing, New York, 1985. 421-429
[4] Ben-Or M, Goldreich O, Goldwasser S, et al. Everything provable is provable in zero-knowledge. In: Proceedings of Crypto88. Berlin: Springer, 1990.. 37-56 · Zbl 0718.68033
[5] Goldreich O. Foundations of Cryptography: Basic Tools. Cambridge: Cambridge University Press, 2001 · Zbl 1007.94016
[6] Goldreich O, Micali S, Wigderson A. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proofs. J ACM, 1991, 38: 691-729 · Zbl 0799.68101
[7] Goldreich O, Oren Y. Definitions and properties of zero-knowledge proof systems. J Crypto, 1994, 7: 1-32 · Zbl 0791.94010
[8] Brassard G, Crepeau C, Yung M. Constant-round perfect zero-knowledge computationally convincing protocols. Theor Comput Sci, 1991, 84: 23-52 · Zbl 0731.68032
[9] Feige U, Shamir A. Zero-knowledge proofs of knowledge in two rounds. In: Advances in Cryptology-CRYPTO’89, LNCS 435. Berlin: Springer, 1989. 526-544 · Zbl 0722.68045
[10] Goldreich O, Kahan A. How to construct constant-round zero-knowledge proof systems for NP. J Crypt, 1996, 9: 167-190 · Zbl 0855.68085
[11] Barak B. How to go beyond the black-box simulation barrier. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, Las Vegas, Nevada, 2001. 106-115
[12] Feige U, Lapidot A, Shamir A. Multiple non-interactive zero-knowledge proofs based on a single random string. J Comput, 1999, 29: 1-28 · Zbl 1018.94015
[13] Goldreich O, Krawczyk H. On the composition of zero-knowledge proof systems, SIAM. J Comput, 1996, 25: 169-192 · Zbl 0841.68112
[14] Barak B, Pass R. On the possibility of one-message weak zero-knowledge. In: Proceedings of the First Theory of Cryptography Conference, TCC 2004, Lecture Notes in Computer Science 2951. Berlin: Springer, 2004. 121-132 · Zbl 1197.94175
[15] Dwork C, Stockmeyer L. 2-round zero-knowledge and proof auditors. In: Proceedings of the 34th ACM Symposium on the Theory of Computing, Montreal, Quebec, Canada, 2002. 332-331 · Zbl 1192.68291
[16] Feige U, Shamir A. Witness indistinguishability and witness hiding protocols. In: Proceedings of the 22nd ACM Symposium on the Theory of Computing, Baltimore, Maryland, USA, 1990. 416-426
[17] Dwork C, Naor M. Zaps and their applications. In: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science-FOCS’00. Redondo Beach, Canada, 2000. 283-293 · Zbl 1125.94019
[18] Naor M. Bit commitment using pseudo-randomness. J Crypt, 1991, 4: 151-158 · Zbl 0731.68033
[19] Blum M. How to prove a theorem so no one else can claim it. In: Proceedings of the International Congress of Mathematicians, · Zbl 0672.94005
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.