{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T15:43:08Z","timestamp":1780069388750,"version":"3.54.0"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540180470","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/3-540-47721-7_11","type":"book-chapter","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T10:32:57Z","timestamp":1175769177000},"page":"171-185","source":"Crossref","is-referenced-by-count":62,"title":["How to Prove All NP Statements in Zero-Knowledge and a Methodology of Cryptographic Protocol Design (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Oded","family":"Goldreich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Silvio","family":"Micali","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"11_CR1","unstructured":"Aho, A.V., J.E. Hopcroft, and J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley Publ. Co., 1974."},{"key":"11_CR2","unstructured":"Alexi, W., B. Chor, O. Goldreich, and C.P. Schnorr, \u201cRSA and Rabin Functions: Certain Parts Are As Hard As The Whole\u201d, to appear in SIAM Jour. on Computing. Extended Abstract in Proc. 25th FOCS, 1984."},{"key":"11_CR3","unstructured":"Alon, N., Z. Galil, and M. Yung, \u201cA Fully Polynomial Simultaneous Broadcast in the Presence of Faults\u201d, preprint, 1985."},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Babai, L., \u201cTrading Group Theory for Randomness\u201d, Proc. 17th STOC, 1985, pp. 421\u2013429.","DOI":"10.1145\/22145.22192"},{"key":"11_CR5","unstructured":"Benaloh, (Cohen) J.D., \u201cSecret Sharing Homomorphisms: Keeping Shares of a Secret Secret\u201d, these proceedings."},{"key":"11_CR6","unstructured":"Blum, M., \u201cCoin Flipping by Phone\u201d, IEEE Spring COMPCOM, pp. 133\u2013137, February 1982."},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"Blum, M., and Micali, S., \u201cHow to Generate Cryptographically Strong Sequences of Pseudo-Random Bits\u201d, SIAM Jour. on Computing, Vol. 13, 1984, pp. 850\u2013864.","journal-title":"SIAM Jour. on Computing"},{"key":"11_CR8","unstructured":"Brassard, G., and C. Crepeau, \u201cZero-Knowledge Simulation of Boolean Circuits\u201d, manuscript 1986."},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"Brassard, G., and C. Crepeau, \u201cNon-Transitive Transfer of Confidence: A Perfect Zero-Knowledge Interactive Protocol for SAT and Beyond\u201d, manuscript, 1986.","DOI":"10.1109\/SFCS.1986.33"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Broder, A.Z., and D. Dolev, \u201cFlipping Coins in Many Pockets (Byzantine Agreement on Uniformly Random Values\u201d, Proc. 25th FOCS, 1984, pp. 157\u2013170.","DOI":"10.1109\/SFCS.1984.715912"},{"key":"11_CR11","unstructured":"Chaum, D., \u201cDemonstrating that a Public Predicate can be Satisfied Without Revealing Any Information About How\u201d, these proceedings."},{"key":"11_CR12","unstructured":"Chaum, D., J.H. Evertse, J. van de Graaf, and R. Peralta, \u201cDemonstrating Possession of a Discrete Logarithm without Revealing It\u201d, these proceedings."},{"key":"11_CR13","unstructured":"Chor, B., O. Goldreich, and S. Goldwasser, \u201cThe Bit Security of Modular Squaring given Partial Factorization of the Modulos\u201d, Proc. of Crypto85, to appear (1986)."},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"Chor, B., S. Goldwasser, S. Micali, and B. Awerbuch, \u201cVerifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults\u201d, Proc. 26th FOCS, 1985, pp. 383\u2013395.","DOI":"10.1109\/SFCS.1985.64"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Cook, S.A., \u201cThe Complexity of Theorem Proving Procedures\u201d, Proc. 3rd STOC, pp. 151\u2013158, 1971.","DOI":"10.1145\/800157.805047"},{"issue":"6","key":"11_CR16","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","volume":"IT-22","author":"W. Diffie","year":"1976","unstructured":"Diffie, W., and M.E. Hellman, \u201cNew Directions in Cryptography\u201d, IEEE Trans. on Inform. Theory, Vol. IT-22, No. 6, November 1976, pp. 644\u2013654.","journal-title":"IEEE Trans. on Inform. Theory"},{"issue":"6","key":"11_CR17","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1145\/3812.3818","volume":"28","author":"S. Even","year":"1985","unstructured":"Even, S., O. Goldreich, and A. Lempel, \u201cA Randomized Protocol for Signing Contracts\u201d, CACM, Vol. 28, No. 6, 1985, pp. 637\u2013647.","journal-title":"CACM"},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"Feldman, P., \u201cA Practical Scheme for Verifiable Secret Sharing\u201d, manuscript, 1986.","DOI":"10.1109\/SFCS.1987.4"},{"key":"11_CR19","unstructured":"Feldman, P., and S., Micali, in preparation, 1985."},{"key":"11_CR20","unstructured":"Fischer, M., S. Micali, C. Rackoff, and D.K. Wittenberg, \u201cAn Oblivious Transfer Protocol Equivalent to Factoring\u201d, in preparation. Preliminary versions were presented in EuroCrypt84 (1984), and in the NSF Workshop on Mathematical Theory of Security, Endicott House (1985)."},{"key":"11_CR21","doi-asserted-by":"crossref","unstructured":"Galil, Z., S. Haber, and M. Yung, \u201cA Private Interactive Test of a Boolean Predicate and Minimum-Knowledge Public-Key Cryptosystems\u201d, Proc. 26th FOCS, 1985, pp. 360\u2013371.","DOI":"10.1109\/SFCS.1985.1"},{"key":"11_CR22","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York, 1979."},{"key":"11_CR23","unstructured":"Goldreich, O., \u201cA Zero-Knowledge Proof that a Two-Prime Moduli Is Not a Blum Integer\u201d, unpublished manuscript, 1985."},{"key":"11_CR24","doi-asserted-by":"crossref","unstructured":"Goldreich, O., S. Goldwasser, and S. Micali, \u201cHow to Construct Random Functions\u201d, Proc. of 25th Symp. on Foundation of Computer Science, 1984, pp. 464\u2013479. To appear in Jour. of ACM.","DOI":"10.1109\/SFCS.1984.715949"},{"key":"11_CR25","unstructured":"Goldreich, O., S. Micali, and A. Wigderson, \u201cProofs that Yield Nothing But their Validity\u201d, in preparation. An extended abstract will appear in the proceedings of 27th FOCS, 1986."},{"key":"11_CR26","unstructured":"Goldreich, O., S. Micali, and A. Wigderson, \u201cHow to Automatically Generate Correct and Private Fault-Tolerant Protocols\u201d, in preparations."},{"issue":"2","key":"11_CR27","first-page":"270","volume":"28","author":"S. Goldwasser","year":"1984","unstructured":"Goldwasser, S., and S. Micali, \u201cProbabilistic Encryption\u201d, JCSS, Vol. 28, No. 2, 1984, pp. 270\u2013299.","journal-title":"JCSS"},{"key":"11_CR28","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., S. Micali, and C. Rackoff, \u201cKnowledge Complexity of Interactive Proofs\u201d, Proc. 17th STOC, 1985, pp. 291\u2013304.","DOI":"10.1145\/22145.22178"},{"key":"11_CR29","unstructured":"Goldwasser, S., S. Micali, and R.L. Rivest, \u201cA Paradoxical Signature Scheme\u201d, Proc. 25th FOCS, 1984."},{"key":"11_CR30","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., and M. Sipser, \u201cArthur Merlin Games versus Interactive Proof Systems\u201d, Proc. 18th STOC, pp. 59\u201368, 1986.","DOI":"10.1145\/12130.12137"},{"key":"11_CR31","doi-asserted-by":"crossref","unstructured":"Karp, R.M., \u201cReducibility among Combinatorial Problems\u201d, Complexity of Computer Computations, R.E. Miller and J.W. Thatcher (eds.), Plenum Press, pp. 85\u2013103, 1972.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"11_CR32","first-page":"115","volume":"9","author":"L.A. Levin","year":"1973","unstructured":"Levin, L.A., \u201cUniversal Search Problems\u201d, Problemy Peredaci Informacii 9, pp. 115\u2013116, 1973. Translated in problems of Information Transmission 9, pp. 265\u2013266.","journal-title":"Problemy Peredaci Informacii"},{"key":"11_CR33","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"R.L. Rivest","year":"1978","unstructured":"Rivest, R.L., Shamir, A., and Adleman, L., \u201cA Method for Obtaining Digital Signatures and Public Key Cryptosystems\u201d, Comm. of the ACM, Vol. 21, February 1978, pp. 120\u2013126.","journal-title":"Comm. of the ACM"},{"key":"11_CR34","unstructured":"Rabin, M.O., \u201cDigitalized Signatures as Intractable as Factorization\u201d, MIT\/LCS\/TR-212, 1979."},{"key":"11_CR35","unstructured":"Rabin, M.O., \u201cHow to Exchange Secrets by Oblivious Transfer\u201d, unpublished manuscript, 1981."},{"key":"11_CR36","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1145\/359168.359176","volume":"22","author":"A. Shamir","year":"1979","unstructured":"Shamir, A., \u201cHow to Share a Secret\u201d, CACM, Vol. 22, 1979, pp. 612\u2013613.","journal-title":"CACM"},{"key":"11_CR37","doi-asserted-by":"crossref","unstructured":"Yao, A.C., \u201cTheory and Applications of Trapdoor Functions\u201d, Proc. of the 23rd IEEE Symp. on Foundation of Computer Science, 1982, pp. 80\u201391.","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2014 CRYPTO\u2019 86"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-47721-7_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T14:27:38Z","timestamp":1736951258000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-47721-7_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540180470"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/3-540-47721-7_11","relation":{},"subject":[]}}