article

Free access

Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems

Authors:

Oded Goldreich,

Silvio Micali,

Avi WigdersonAuthors Info & Claims

Journal of the ACM (JACM), Volume 38, Issue 3

Pages 690 - 728

https://doi.org/10.1145/116825.116852

Published: 01 July 1991 Publication History

PDF eReader

References

[1]

AHO, A. V., HOPCRAFT, J E., AND ULLMAN, J, D. The Design and Analysis of Computer A lgorithrn~. Addi~on-WcMcy, Reading, Mass., 1974.

Crossref

Google Scholar

[2]

AIELLO, W., GOLDWASSER, S., AND HASTAD, J. On the power of interaction. In Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1986, pp. 368-379.

Google Scholar

[3]

AIELLO, W, AND HASTAD, J. Perfect zero-knowledge languages can be recognized in two rounds. In Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1987, pp. 439-448.

Google Scholar

[4]

ALEXI, W., CHOR, B., GOLDREICH, 0., AND SCHNORR, C.P. RSA and Rabin functions: Certain parts are as hard as the whole SIAM J. Comput. 17, 2 (1988), 194-209. (Extended abstract in Proceedings of the 25th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1984.)

Crossref

Google Scholar

[5]

ALON, N., GALIL, Z. AND YUNG, M. A fully polynomial simultaneous broadcast in the presence of faults. Unpublished manuscript, 1985.

Google Scholar

[6]

BABAI, L. Trading group theory for randomness. In Proceedings of the 17th Annual A CM Symposium on Theory of Computing (Providence, R.I., May 6-8). ACM, New York, 1985, pp. 421-429.

Crossref

Google Scholar

[7]

BABAI, L., KANTOR, W. M., AND LUKS, E.M. Computational complexity and classification of finite simple groups. In Proceedings of the 24th Annual IEEE Foundations of Computer Science. IEEE, New York, 1983, pp. 162-171.

Google Scholar

[8]

BABAI, L., AND MORAN, S. Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. J. Comput. Syst. Sci. 36, 2 (1988), 254-276.

Crossref

Google Scholar

[9]

BELLARE, M., MICALI, S., AND OSTROVSKY, R. Perfect zero-knowledge in constant rounds. In Proceedings of the 22nd Annual A CM Symposium on Theory of Computing (Baltimore, Md., May 12-14). ACM, New York, 1990, pp. 482-493.

Crossref

Google Scholar

[10]

BENALOH (COHEN), J.D. Cryptographic capsules: A disjunctive primitive for interactive protocols. In A. M. Odlyzko, ed., Proceedings of Advances in Cryptology--Crypto86. Lecture Notes in Computer Science, vol. 263. Springer-Verlag, New York, 1987, pp. 213-222.

Crossref

Google Scholar

[11]

BEN-OR, M., GOLDREICH, O., GOLDWASSER, S., HASTAD, J., KILLIAN, J., MICALI, S., AND ROGAWAY, P. Everything provable is provable in zero-knowledge. In Proceedings of Advances in Cryptology--Crypto88. Lecture Notes in Computer Science, vol. 403. Springer-Verlag, New York, 1990, pp. 37-56.

Crossref

Google Scholar

[12]

BEN-OR, M., GOLDWASS~R, S., AND WIGDERSON, A. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proceedings of the 20th Annual A CM Symposium on Theory of Computing (Chicago, II1., May 2-4). ACM, New York, I988, pp. 1-10.

Crossref

Google Scholar

[13]

BLAK_eLY, G. R. Safeguarding cryptographic keys. In Proceedings of National Computer Conference, vol. 48. AFIPS Press, 1979, pp. 313- 317.

Google Scholar

[14]

BoPr'ANA, R., HASTAD, J., AND ZACHOS, S. Does co-NP have short interactive proofs? Inf. Proc. Lett. 25 (May 1987), 127-132.

Crossref

Google Scholar

[15]

BRASSARD, G., CHAUM, D., AND CR~PZAU, C. Minimum disclosure proofs of knowledge. J. Comput. Syst. Sci. 37, 2 (1988), 156-189.

Crossref

Google Scholar

[16]

BRASSAnD, G., AND CR~PEAU, C. Zero-knowledge simulation of Boolean circuits. In A. M. Odlyzko, ed., Proceedings of Advances in Cryptology--Crypto86. Lecture Notes in Computer Science, vol. 263. Springer-Verlag, New York, 1987, pp. 223-233.

Crossref

Google Scholar

[17]

BRASSARD, G., AND CR~PZAU, C. Non-transitive transfer of confidence: A perfect zeroknowledge interactive protocol for SAT and beyond. In Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1986, pp. 188-195.

Google Scholar

[18]

BRASSAnD, G., CR~PEAU, C., AND YUNG, M. Everything in NP can be argued in perfect zero-knowledge in a constant number of rounds. In Proceedings of the 16th Annual International Colloquium on Automata Languages and Programming. Lecture Notes in Computer Science, vol. 435. Springer-Verlag, New York, 1989, pp. 123-136.

Crossref

Google Scholar

[19]

CHAUM, D. Demonstrating that a public predicate can be satisfied without revealing any information about how. In A. M. Odlyzko, ed., Proceedings of Advances in Cryptology--Crypto86. Lecture Notes in Computer Science, vol. 263. Springer-Verlag, New York, 1987, pp. 195-199.

Crossref

Google Scholar

[20]

CHAUM, D., CRtEPEAU, C., AND DAMGARD, I. Multiparty unconditionally secure protocols. In Proceedings of the 20th Annual A CM Symposium on Theory of Computing (Chicago, Ill., May 2-4). ACM, New York, 1988, pp. 11-19.

Crossref

Google Scholar

[21]

CHOR, B., GOLDWASSER, S., MICALI, S., AND AWERBUCH, B. Verifiable secret sharing and achieving simultaneity in the presence of faults. In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1985, pp. 383-395.

Google Scholar

[22]

CHOR, B., AND KUSHmEWTZ, E. A zero-one law for Boolean privacy. In Proceedings of the 21st Annual ACM Symposium on the Theory of Computing (Seattle, Wash., May 15-17). ACM, New York, 1989, pp. 62-72.

Crossref

Google Scholar

[23]

COHEN, J. D., AND FISCHER, M. J. A robust and verifiable cryptographically secure election scheme. In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science. It~IEE. New York. 10~5. pp. 372-392.

Crossref

Google Scholar

[24]

COOK, S. A. The complexity of theorem-proving procedures. In Proceedings of the 3rd Annual ACM Symposium on the Theory of Computing (Shaker Heights, Ohio, May 3-5). ACM, New York, 1971, pp. 151-158.

Crossref

Google Scholar

[25]

DIFFIE, W., AND HELLMAN, M.E. New directions in cryptography. IEEE Trans. Inf. Theory, IT-22, 6 (Nov. 1976), 644-654.

Google Scholar

[26]

EVEN, S., GOLDREICH, O., AND LEMPEL, A. A randomized protocol for signing contracts. Commun. A CM 28, 6 (June 1985), 637-647.

Crossref

Google Scholar

[27]

FEIGE, U., FIAT, A., AND SHAMIR, A. Zero-knowledge proofs of identity. J. Crypto. 1, 2 (1988), 77-94.

Crossref

Google Scholar

[28]

FEIGE, U., AND SHAMIR, A. Zero-knowledge proofs of knowledge in two rounds. In Proceedings of Advances in Cryptology--Crypto89. Lecture Notes in Computer Science, vol. 435. Springer-Verlag, New York, 1990, pp. 526-544.

Crossref

Google Scholar

[29]

FELDMAN, P. A practical scheme for verifiable secret sharing. In Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1987, pp. 427-438.

Google Scholar

[30]

FISCHER, M., MICALI, S., RACKOFF, C., AND WITTENBERG, D.K. An oblivious transfer protocol equivalent to factoring. Unpublished manuscript, 1986.

Google Scholar

[31]

FORTNOW, L. The complexity of perfect zero-knowledge. In Proceedings of the 19th Annual ACM Symposium on the Theory of Computing (New York, N.Y., May 25-27). ACM. New York, 1987, pp. 204-209.

Crossref

Google Scholar

[32]

GALIL, Z., HABER, S., AND YUNG, M. A private interactive test of a Boolean predicate and minimum-knowledge public-key cryptosystems. In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 360-371.

Crossref

Google Scholar

[33]

GALIL, Z., HABER, S., AND YUNG, M. Cryptographic computation: Secure fault-tolerant protocols and the public-key model. In C. Pomerance, ed., Proceedings of Advances in Cryptology--Crypto87. Lecture Notes in Computer Science, vol. 293. Springer-Verlag, New York, 1987, pp. 135-155.

Crossref

Google Scholar

[34]

GAREY, M. R., AND JOHNSON, D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979.

Crossref

Google Scholar

[35]

GARZY, M. R., JOHNSON, D. S., AND STOCKMEYER, L. Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1 (1976), 237-267.

Google Scholar

[36]

GOLDREICH, O. A zero-knowledge proof that a two-prime moduli is not a Blum integer. Unpublished manuscript, 1985.

Google Scholar

[37]

GOLDREICH, O. Zero-knowledge and the design of secure protocols (an exposition). Tech. Rep. TR-480. Comput. Sci. Dept., Technion, Haifa, Israel, 1987.

Google Scholar

[38]

GOLDREICH, O. Towards a theory of average case complexity (a survey). Tech. Rep. TR-53I. Comput. Sci. Dept., Techmon, Haifa, Israel, 1988.

Google Scholar

[39]

GOLDREICH, O. A uniform-complexity treatment of encryption and zero-knowledge. Tech. Rep. TR-568. Comput. Sci. Dept., Technion, Haifa, Israel, 1989.

Google Scholar

[40]

GOLDREICH, O., AND KRAWCZYK, H. On the composition of zero-knowledge proof systems. In Proceedings of the 17th Annual International CaUoquium on Automata Languages and Programming. Lecture Notes in Computer Science, vol. 443. Springer-Vertag, New York, 1990, pp. 268-282.

Crossref

Google Scholar

[41]

GOLDREICH, O., MANSOUR, Y., AND SIPSER, M. Interactive proof systems: Provers that never fail and random selection. In Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1987, pp. 449-461.

Google Scholar

[42]

GOLDREICH, O., MICALI, S., AND WIGDERSON, A. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. In Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1986, pp. 174-187.

Google Scholar

[43]

GOLDREICH, O., MICALI, S., AND WIGDERSON, A. How to play ANY mental game or a completeness theorem for protocols with honest majority. In Proceedings of the 19th Annual ACMSymposium on Theory of Cornp~tting (New York, N.Y., May 25-27). ACM, New York, 1987, pp. 218- 229.

Crossref

Google Scholar

[44]

GOLDRE1CH, O, AND OREN, Y. Definitions and properties of zero-knowledge proof systems. Tech. Rep. TR-610. Comput. Sci. Dept., Technion, Haifa, Israel, 1990.

Google Scholar

[45]

GOLDREICH, O., AND VAINISH, R. How to solve any protocol problem--An efficiency improvement. In C. Pomerance, ed., Proceedings of Advances in Cryptology--Crypto87. Lecture Notes in Computer Science, vol. 293. Sprmger-Verlag, New York, 1987, pp. 73-86.

Crossref

Google Scholar

[46]

GOLDWASSER, S., AND MICALI, S. Probabllistic encryptlon. J. Comput. Syst. Sei. 28, 2 (1984), 270-299.

Google Scholar

[47]

GOLDWASSER, S., MICALI, S., AND RACKOFF, C. The knowledge complexity of interactive proof systems. SIAM J. Comput. 18, 1 (1989), 186-208.

Crossref

Google Scholar

[48]

GOLDWASSER, S., MICALI, S., AND RIVEST, R. L. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17, 2 (1988), 281-308.

Crossref

Google Scholar

[49]

GOLDWASSER, S., AND SIPSER, M. Private coins versus public coins in interactive proof systems. In Proceedings of the 18th Annual A CM Symposium on Theory of Computing (Berkeley, Calif., May 28-30). ACM, New York, 1986, pp. 59-68.

Crossref

Google Scholar

[50]

GUREVICH, Y. Average case completeness. Tech. Rep. CRL-TR-03-88, Comput. Res. Lab., Univ. Michigan, Ann Arbor, Mich., 1988.

Google Scholar

[51]

H~STAD, J. Pseudo-random generators under uniform assumptions. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (Baltimore, Md., May 12-14). ACM, New York, 1990, pp. 395-404.

Crossref

Google Scholar

[52]

IMPAGLIAZZO, R., LEVIN, L. A., AND LUBY, M. Pseudorandom generation from one-way functions. In Proceedings of the 21st Annual A CM Symposium on Theory of Computing (Seattle, Wash., May 15-17). ACM, New York, 1989, pp. 12-24.

Crossref

Google Scholar

[53]

IMPAGLIAZZO, R., AND YUNG, M. Direct minimum-knowledge computations. In C. Pomerance, ed., Proceedings of Advances in Cryptology--Crypto87. Lecture Notes in Computer Science, vol. 293. Springer-Verlag, New York, 1987, pp. 40-51.

Crossref

Google Scholar

[54]

KARP, R.M. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, eds. Complexity of Computer Computations. Plenum Press, New York, 1972, pp. 85-103.

Google Scholar

[55]

KILIAN, J., MICALI, S., AND OSTROVSKY, R. Minimum resource zero-knowledge proofs. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1989, pp. 474-479.

Google Scholar

[56]

LEVlN, L.A. Universal search problems. Prob. Pere. Inf. 9 (1973), 115-116. Translated m Prob. Inf. Trans. 9 (1973), 265-266.

Google Scholar

[57]

LEVIN, L.A. Average case complete problems. SIAM J. Comput. 15 (1986), 285-286.

Crossref

Google Scholar

[58]

NAOR, M. Bit commitment using pseudorandomness. In Proceedings of Advances in Cryptology--Crypto89. Lecture Notes in Computer Science, vol. 435. Springer-Verlag, New York, 1990, pp. 128-137.

Crossref

Google Scholar

[59]

NISSAN, N., AND WIGDERSON, A. Hardness vs. randomness. In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1988, pp. 2-11.

Google Scholar

[60]

OREN, Y. On the cunning power of cheating verifiers: Some observations about zero-knowledge proofs. In Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1987, pp. 462-471.

Google Scholar

[61]

RABIN, M. O. Digitalized signatures and public-key functions as intractable as factorization. Tech. Rep. MIT/LCS/TR-212. MIT, Cambridge, Mass., 1979.

Crossref

Google Scholar

[62]

RABtN, T., AND BEN-OR, M. Verifiable secret sharing and multiparty protocols with honest majority. In Proceedings of the 21st Annual A CM Symposium on Theory of Computing (Seattle, Wash., May 15-17). ACM, New York, 1989, pp. 73-85.

Crossref

Google Scholar

[63]

RIVEST, R. L., SHAMIR, A., AND ADLEMAN, L. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21, 2 (Feb. 1978), 120-126.

Crossref

Google Scholar

[64]

SCHOENING, U. Graph isomorphism is in the low hierarchy. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STA CS 87). Lecture Notes in Computer Science, vol. 247. Springer-Verlag, New York, 1987, pp. 114-124.

Crossref

Google Scholar

[65]

SHAMIR, A. How to share a secret. Commun. ACM 22, 11 (Nov. 1979), 612-613.

Crossref

Google Scholar

[66]

STOCKMEYER, L.J. The polynomial-time hierarchy. Theoret. Comput. Sci. 3 (1977), 1-22.

Google Scholar

[67]

TOMPA, M., AND WOLL, H. Random self-reducibility and zero-knowledge interactive proofs of possession of information. In Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1987, pp. 472-482.

Google Scholar

[68]

YAO, A.C. Theory and applications of trapdoor functions. In Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1982, pp. 80-91.

Google Scholar

[69]

YAO, A.C. How to generate and exchange secrets. In Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1986, pp. 162-167.

Google Scholar

Cited By

View all

Cho HFroelicher DDokmai NNandi ASadhuka SHong MBerger B(2024)Privacy-Enhancing Technologies in Biomedical Data ScienceAnnual Review of Biomedical Data Science10.1146/annurev-biodatasci-120423-1201077:1(317-343)Online publication date: 23-Aug-2024
https://doi.org/10.1146/annurev-biodatasci-120423-120107
Chen JYan HLiu ZZhang MXiong HYu S(2024)When Federated Learning Meets Privacy-Preserving ComputationACM Computing Surveys10.1145/367901356:12(1-36)Online publication date: 22-Jul-2024
https://dl.acm.org/doi/10.1145/3679013
Simsek I(2024)Authentication, Authorization, Access Control, and Key Exchange in Internet of ThingsACM Transactions on Internet of Things10.1145/3643867Online publication date: 3-Feb-2024
https://doi.org/10.1145/3643867
Show More Cited By

Index Terms

Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems

Recommendations

On the Composition of Zero-Knowledge Proof Systems

The wide applicability of zero-knowledge interactive proofs comes from the possibility of using these proofs as subroutines in cryptographic protocols. A basic question concerning this use is whether the (sequential and/or parallel) composition of zero-...
Definitions and properties of zero-knowledge proof systems

In this paper we investigate some properties of zero-knowledge proofs, a notion introduced by Goldwasser, Micali, and Rackoff. We introduce and classify two definitions of zero-knowledge: auxiliary-input zero-knowledge and blackbox-simulation zero-...
On the communication complexity of zero-knowledge proofs

The fact that there are zero-knowledge proofs for all languages in NP (see [15], [6], and [5]) has, potentially, enormous implications to cryptography. For cryptographers, the issue is no longer "which languages in NP have zeroknowledge proofs" but ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 38, Issue 3

July 1991

259 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/116825

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1991

Published in JACM Volume 38, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

874
Total Citations
View Citations
6,640
Total Downloads

Downloads (Last 12 months)1,038
Downloads (Last 6 weeks)255

Reflects downloads up to 24 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Cho HFroelicher DDokmai NNandi ASadhuka SHong MBerger B(2024)Privacy-Enhancing Technologies in Biomedical Data ScienceAnnual Review of Biomedical Data Science10.1146/annurev-biodatasci-120423-1201077:1(317-343)Online publication date: 23-Aug-2024
https://doi.org/10.1146/annurev-biodatasci-120423-120107
Chen JYan HLiu ZZhang MXiong HYu S(2024)When Federated Learning Meets Privacy-Preserving ComputationACM Computing Surveys10.1145/367901356:12(1-36)Online publication date: 22-Jul-2024
https://dl.acm.org/doi/10.1145/3679013
Simsek I(2024)Authentication, Authorization, Access Control, and Key Exchange in Internet of ThingsACM Transactions on Internet of Things10.1145/3643867Online publication date: 3-Feb-2024
https://doi.org/10.1145/3643867
Hirahara SNanashima MMohar BShinkar IO'Donnell R(2024)One-Way Functions and Zero KnowledgeProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649701(1731-1738)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649701
Gur TO'Connor JSpooner NMohar BShinkar IO'Donnell R(2024)Perfect Zero-Knowledge PCPs for #PProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649698(1724-1730)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649698
Drusinsky D(2024)From P Versus NP to Probabilistic and Zero Knowledge Proof SystemsComputer10.1109/MC.2024.335892857:4(119-130)Online publication date: 3-Apr-2024
https://dl.acm.org/doi/10.1109/MC.2024.3358928
Mehandiratta SAgarwal R(2024)Increasing Trust and Privacy by Using Blockchain Technology in the Onion Router Network2024 11th International Conference on Reliability, Infocom Technologies and Optimization (Trends and Future Directions) (ICRITO)10.1109/ICRITO61523.2024.10522123(1-5)Online publication date: 14-Mar-2024
https://doi.org/10.1109/ICRITO61523.2024.10522123
Lewis LZhu DGheorghiu ANoel CKatz OHarraz BWang QRisinger AFeng LBiswas DEgan LVidick TCetina MMonroe C(2024)Experimental implementation of an efficient test of quantumnessPhysical Review A10.1103/PhysRevA.109.012610109:1Online publication date: 9-Jan-2024
https://doi.org/10.1103/PhysRevA.109.012610
Wang CWu WChen FShu HZhang JZhang YWang TXie DZhao C(2024)A Blockchain-Based Trustworthy Access Control Scheme for Medical Data SharingIET Information Security10.1049/2024/55595222024Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1049/2024/5559522
Ismayilov GÖzturan C(2024)PTTS: Zero-knowledge proof-based private token transfer system on Ethereum blockchain and its network flow based balance range privacy attack analysisJournal of Network and Computer Applications10.1016/j.jnca.2024.104045(104045)Online publication date: Oct-2024
https://doi.org/10.1016/j.jnca.2024.104045
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

On the Composition of Zero-Knowledge Proof Systems

Definitions and properties of zero-knowledge proof systems

On the communication complexity of zero-knowledge proofs

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations