{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T21:18:20Z","timestamp":1675286300010},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1991,7]]},"DOI":"10.1145\/116825.116852","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"690-728","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":663,"title":["Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems"],"prefix":"10.1145","volume":"38","author":[{"given":"Oded","family":"Goldreich","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}]},{"given":"Silvio","family":"Micali","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge"}]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[{"name":"Hebrew Univ., Jerusalem, Israel"}]}],"member":"320","published-online":{"date-parts":[[1991,7]]},"reference":[{"key":"e_1_2_1_1_2","volume-title":"Mass.","author":"AHO A. V.","year":"1974","unstructured":"AHO , A. V. , HOPCRAFT , J E ., AND ULLMAN , J, D . The Design and Analysis of Computer A lgorithrn~. Addi~on-WcMcy, Reading , Mass. , 1974 . AHO, A. V., HOPCRAFT, J E., AND ULLMAN, J, D. The Design and Analysis of Computer A lgorithrn~. Addi~on-WcMcy, Reading, Mass., 1974."},{"key":"e_1_2_1_2_2","first-page":"368","volume-title":"Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science. IEEE","author":"AIELLO W.","year":"1986","unstructured":"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 . 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."},{"key":"e_1_2_1_3_2","first-page":"439","volume-title":"Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science. IEEE","author":"AIELLO W","year":"1987","unstructured":"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 . 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."},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/0217013"},{"key":"e_1_2_1_5_2","volume-title":"A fully polynomial simultaneous broadcast in the presence of faults. Unpublished manuscript","author":"ALON N.","year":"1985","unstructured":"ALON , N. , GALIL , Z. AND YUNG , M. A fully polynomial simultaneous broadcast in the presence of faults. Unpublished manuscript , 1985 . ALON, N., GALIL, Z. AND YUNG, M. A fully polynomial simultaneous broadcast in the presence of faults. Unpublished manuscript, 1985."},{"key":"e_1_2_1_6_2","first-page":"421","volume-title":"Proceedings of the 17th Annual A CM Symposium on Theory of Computing (Providence, R.I., May 6-8). ACM","author":"BABAI L.","year":"1985","unstructured":"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 . 10.1145\/22145.22192 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. 10.1145\/22145.22192"},{"key":"e_1_2_1_7_2","first-page":"162","volume-title":"Proceedings of the 24th Annual IEEE Foundations of Computer Science. IEEE","author":"BABAI L.","year":"1983","unstructured":"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 . 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."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"e_1_2_1_9_2","first-page":"482","volume-title":"Proceedings of the 22nd Annual A CM Symposium on Theory of Computing","author":"BELLARE M.","year":"1990","unstructured":"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 . 10.1145\/100216.100283 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. 10.1145\/100216.100283"},{"key":"e_1_2_1_10_2","series-title":"Lecture Notes in Computer Science","first-page":"213","volume-title":"Proceedings of Advances in Cryptology--Crypto86","author":"BENALOH N), J","year":"1987","unstructured":"BENALOH (COHE N), 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 . 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."},{"key":"e_1_2_1_11_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/0-387-34799-2_4","volume-title":"Proceedings of Advances in Cryptology--Crypto88","author":"BEN-OR M.","year":"1990","unstructured":"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 . 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."},{"key":"e_1_2_1_12_2","first-page":"1","volume-title":"Proceedings of the 20th Annual A CM Symposium on Theory of Computing","author":"BEN-OR M.","unstructured":"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 . 10.1145\/62212.62213 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. 10.1145\/62212.62213"},{"key":"e_1_2_1_13_2","first-page":"313","volume-title":"Proceedings of National Computer Conference","volume":"48","author":"BLAK LY, G","year":"1979","unstructured":"BLAK _e LY, G . R. Safeguarding cryptographic keys . In Proceedings of National Computer Conference , vol. 48 . AFIPS Press , 1979 , pp. 313 - 317 . BLAK_eLY, G. R. Safeguarding cryptographic keys. In Proceedings of National Computer Conference, vol. 48. AFIPS Press, 1979, pp. 313- 317."},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90232-8"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90005-0"},{"key":"e_1_2_1_16_2","series-title":"Lecture Notes in Computer Science","first-page":"223","volume-title":"Proceedings of Advances in Cryptology--Crypto86","author":"BRASSA D, G","year":"1987","unstructured":"BRASSA n D, 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 . 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."},{"key":"e_1_2_1_17_2","first-page":"188","volume-title":"Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science. IEEE","author":"BRASSARD G.","year":"1986","unstructured":"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 . 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."},{"key":"e_1_2_1_18_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/BFb0035756","volume-title":"Proceedings of the 16th Annual International Colloquium on Automata Languages and Programming","author":"BRASSA D, G","year":"1989","unstructured":"BRASSA n D, 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 . 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."},{"key":"e_1_2_1_19_2","series-title":"Lecture Notes in Computer Science","first-page":"195","volume-title":"Proceedings of Advances in Cryptology--Crypto86","author":"CHAUM D.","year":"1987","unstructured":"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 . 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."},{"key":"e_1_2_1_20_2","first-page":"11","volume-title":"Proceedings of the 20th Annual A CM Symposium on Theory of Computing","author":"CHAUM D.","year":"1988","unstructured":"CHAUM , D. , CR tE PEAU , 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 . 10.1145\/62212.62214 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. 10.1145\/62212.62214"},{"key":"e_1_2_1_21_2","first-page":"383","volume-title":"Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science. IEEE","author":"CHOR B.","year":"1985","unstructured":"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 . 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."},{"key":"e_1_2_1_22_2","first-page":"62","volume-title":"Proceedings of the 21st Annual ACM Symposium on the Theory of Computing","author":"CHOR B.","year":"1989","unstructured":"CHOR , B. , AND KUSH m EWTZ , 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 . 10.1145\/73007.73013 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. 10.1145\/73007.73013"},{"key":"e_1_2_1_23_2","first-page":"372","volume-title":"Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science. It~IEE","author":"COHEN J. D.","year":"1985","unstructured":"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 . 10.1109\/SFCS. 1985 .2 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. 10.1109\/SFCS.1985.2"},{"key":"e_1_2_1_24_2","first-page":"151","volume-title":"Proceedings of the 3rd Annual ACM Symposium on the Theory of Computing","author":"COOK S. A.","year":"1971","unstructured":"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 . 10.1145\/800157.805047 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. 10.1145\/800157.805047"},{"key":"e_1_2_1_25_2","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","volume":"6","author":"DIFFIE W.","year":"1976","unstructured":"DIFFIE , W. , AND HELLMAN , M.E. New directions in cryptography. IEEE Trans. Inf. Theory, IT-22 , 6 ( Nov. 1976 ), 644 - 654 . DIFFIE, W., AND HELLMAN, M.E. New directions in cryptography. IEEE Trans. Inf. Theory, IT-22, 6 (Nov. 1976), 644-654.","journal-title":"IEEE Trans. Inf. Theory, IT-22"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3812.3818"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02351717"},{"key":"e_1_2_1_28_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1007\/0-387-34805-0_46","volume-title":"Proceedings of Advances in Cryptology--Crypto89","author":"FEIGE U.","year":"1990","unstructured":"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 . 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."},{"key":"e_1_2_1_29_2","first-page":"427","volume-title":"Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science. IEEE","author":"FELDMAN P.","year":"1987","unstructured":"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 . 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."},{"key":"e_1_2_1_30_2","volume-title":"An oblivious transfer protocol equivalent to factoring. Unpublished manuscript","author":"FISCHER M.","year":"1986","unstructured":"FISCHER , M. , MICALI , S. , RACKOFF , C. , AND WITTENBERG , D.K. An oblivious transfer protocol equivalent to factoring. Unpublished manuscript , 1986 . FISCHER, M., MICALI, S., RACKOFF, C., AND WITTENBERG, D.K. An oblivious transfer protocol equivalent to factoring. Unpublished manuscript, 1986."},{"key":"e_1_2_1_31_2","first-page":"204","volume-title":"Proceedings of the 19th Annual ACM Symposium on the Theory of Computing","author":"FORTNOW L.","year":"1987","unstructured":"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 . 10.1145\/28395.28418 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. 10.1145\/28395.28418"},{"key":"e_1_2_1_32_2","first-page":"360","volume-title":"Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science. IEEE","author":"GALIL Z.","year":"1985","unstructured":"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 . 10.1109\/SFCS. 1985 .1 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. 10.1109\/SFCS.1985.1"},{"key":"e_1_2_1_33_2","series-title":"Lecture Notes in Computer Science","first-page":"135","volume-title":"Proceedings of Advances in Cryptology--Crypto87","author":"GALIL Z.","year":"1987","unstructured":"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 . 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."},{"key":"e_1_2_1_34_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"GAREY M. R.","year":"1979","unstructured":"GAREY , M. R. , AND JOHNSON , D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness . Freeman , New York , 1979 . GAREY, M. R., AND JOHNSON, D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979."},{"key":"e_1_2_1_35_2","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"GARZY M. R.","year":"1976","unstructured":"GARZY , M. R. , JOHNSON , D. S. , AND STOCKMEYER , L. Some simplified NP -complete graph problems. Theoret. Comput. Sci. 1 ( 1976 ), 237 - 267 . GARZY, M. R., JOHNSON, D. S., AND STOCKMEYER, L. Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1 (1976), 237-267.","journal-title":"Theoret. Comput. Sci."},{"key":"e_1_2_1_36_2","volume-title":"A zero-knowledge proof that a two-prime moduli is not a Blum integer. Unpublished manuscript","author":"GOLDREICH O.","year":"1985","unstructured":"GOLDREICH , O. A zero-knowledge proof that a two-prime moduli is not a Blum integer. Unpublished manuscript , 1985 . GOLDREICH, O. A zero-knowledge proof that a two-prime moduli is not a Blum integer. Unpublished manuscript, 1985."},{"key":"e_1_2_1_40_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1007\/BFb0032038","volume-title":"Proceedings of the 17th Annual International CaUoquium on Automata Languages and Programming","author":"GOLDREICH O.","year":"1990","unstructured":"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 . 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."},{"key":"e_1_2_1_41_2","first-page":"449","volume-title":"Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science. IEEE","author":"GOLDREICH O.","year":"1987","unstructured":"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 . 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."},{"key":"e_1_2_1_42_2","first-page":"174","volume-title":"Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science. IEEE","author":"GOLDREICH O.","year":"1986","unstructured":"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 . 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."},{"key":"e_1_2_1_43_2","first-page":"218","volume-title":"Proceedings of the 19th Annual ACMSymposium on Theory of Cornp~tting","author":"GOLDREICH O.","year":"1987","unstructured":"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 . 10.1145\/28395.28420 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. 10.1145\/28395.28420"},{"key":"e_1_2_1_45_2","series-title":"Lecture Notes in Computer Science","first-page":"73","volume-title":"Proceedings of Advances in Cryptology--Crypto87","author":"GOLDREICH O.","year":"1987","unstructured":"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 . 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."},{"key":"e_1_2_1_46_2","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/0022-0000(84)90073-4","volume":"28","author":"GOLDWASSER S.","year":"1984","unstructured":"GOLDWASSER , S. , AND MICALI , S. Probabllistic encryptlon. J. Comput. Syst. Sei. 28 , 2 ( 1984 ), 270-299. GOLDWASSER, S., AND MICALI, S. Probabllistic encryptlon. J. Comput. Syst. Sei. 28, 2 (1984), 270-299.","journal-title":"J. Comput. Syst. Sei."},{"key":"e_1_2_1_47_2","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"e_1_2_1_48_2","doi-asserted-by":"publisher","DOI":"10.1137\/0217017"},{"key":"e_1_2_1_49_2","first-page":"59","volume-title":"Proceedings of the 18th Annual A CM Symposium on Theory of Computing","author":"GOLDWASSER S.","year":"1986","unstructured":"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 . 10.1145\/12130.12137 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. 10.1145\/12130.12137"},{"key":"e_1_2_1_51_2","first-page":"395","volume-title":"Proceedings of the 22nd Annual ACM Symposium on Theory of Computing","author":"H~STAD J.","year":"1990","unstructured":"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 . 10.1145\/100216.100270 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. 10.1145\/100216.100270"},{"key":"e_1_2_1_52_2","first-page":"12","volume-title":"Proceedings of the 21st Annual A CM Symposium on Theory of Computing","author":"IMPAGLIAZZO R.","year":"1989","unstructured":"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 . 10.1145\/73007.73009 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. 10.1145\/73007.73009"},{"key":"e_1_2_1_53_2","series-title":"Lecture Notes in Computer Science","first-page":"40","volume-title":"Proceedings of Advances in Cryptology--Crypto87","author":"IMPAGLIAZZO R.","year":"1987","unstructured":"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 . 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."},{"key":"e_1_2_1_54_2","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"KARP R.M.","year":"1972","unstructured":"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 . 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."},{"key":"e_1_2_1_55_2","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1109\/SFCS.1989.63521","volume-title":"Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science. IEEE","author":"KILIAN J.","year":"1989","unstructured":"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 . 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."},{"key":"e_1_2_1_56_2","first-page":"115","volume":"9","author":"LEV N, L","year":"1973","unstructured":"LEV l N, L .A. Universal search problems. Prob. Pere. Inf. 9 ( 1973 ), 115 - 116 . Translated m Prob. Inf. Trans. 9 (1973), 265-266. LEVlN, L.A. Universal search problems. Prob. Pere. Inf. 9 (1973), 115-116. Translated m Prob. Inf. Trans. 9 (1973), 265-266.","journal-title":"Prob. Pere. Inf."},{"key":"e_1_2_1_57_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215020"},{"key":"e_1_2_1_58_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1007\/0-387-34805-0_13","volume-title":"Proceedings of Advances in Cryptology--Crypto89","author":"NAOR M.","year":"1990","unstructured":"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 . 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."},{"key":"e_1_2_1_59_2","first-page":"2","volume-title":"Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science. IEEE","author":"NISSAN N.","year":"1988","unstructured":"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 . 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."},{"key":"e_1_2_1_60_2","first-page":"462","volume-title":"Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science. IEEE","author":"OREN Y.","year":"1987","unstructured":"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 . 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."},{"key":"e_1_2_1_62_2","first-page":"73","volume-title":"Proceedings of the 21st Annual A CM Symposium on Theory of Computing","author":"RAB N, T","year":"1989","unstructured":"RAB t N, 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 . 10.1145\/73007.73014 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. 10.1145\/73007.73014"},{"key":"e_1_2_1_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359342"},{"key":"e_1_2_1_64_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1007\/BFb0039599","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STA CS 87)","author":"SCHOENING U.","year":"1987","unstructured":"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 . 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."},{"key":"e_1_2_1_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"},{"key":"e_1_2_1_66_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"STOCKMEYER L.J.","year":"1977","unstructured":"STOCKMEYER , L.J. The polynomial-time hierarchy. Theoret. Comput. Sci. 3 ( 1977 ), 1 - 22 . STOCKMEYER, L.J. The polynomial-time hierarchy. Theoret. Comput. Sci. 3 (1977), 1-22.","journal-title":"Theoret. Comput. Sci."},{"key":"e_1_2_1_67_2","first-page":"472","volume-title":"Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science. IEEE","author":"TOMPA M.","year":"1987","unstructured":"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 . 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."},{"key":"e_1_2_1_68_2","first-page":"80","volume-title":"Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science. IEEE","author":"YAO A.C.","year":"1982","unstructured":"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 . 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."},{"key":"e_1_2_1_69_2","first-page":"162","volume-title":"Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science. IEEE","author":"YAO A.C.","year":"1986","unstructured":"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 . 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."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/116825.116852","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:36:37Z","timestamp":1672263397000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/116825.116852"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,7]]},"references-count":63,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1991,7]]}},"alternative-id":["10.1145\/116825.116852"],"URL":"http:\/\/dx.doi.org\/10.1145\/116825.116852","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1991,7]]},"assertion":[{"value":"1991-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}