{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T05:53:35Z","timestamp":1791352415600,"version":"4.3.1"},"reference-count":46,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1991,12]]},"abstract":"<jats:p>This paper investigates the possibility of disposing of interaction between prover and verifier in a zero-knowledge proof if they share beforehand a short random string.<\/jats:p>\n                  <jats:p>Without any assumption, it is proven that noninteractive zero-knowledge proofs exist for some number-theoretic languages for which no efficient algorithm is known.<\/jats:p>\n                  <jats:p>If deciding quadratic residuosity (modulo composite integers whose factorization is not known) is computationally hard, it is shown that the NP-complete language of satisfiability also possesses noninteractive zero-knowledge proofs.<\/jats:p>","DOI":"10.1137\/0220068","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:34:57Z","timestamp":1109226897000},"page":"1084-1118","source":"Crossref","is-referenced-by-count":297,"title":["Noninteractive Zero-Knowledge"],"prefix":"10.1137","volume":"20","author":[{"given":"Manuel","family":"Blum","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alfredo","family":"De Santis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Silvio","family":"Micali","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giuseppe","family":"Persiano","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"RADHU","doi-asserted-by":"crossref","unstructured":"L. M. Adleman, M. A. Huang,  Recognizing primes in random polynomial time,  Proc. 19th Annual ACM Symposium on Theory of Computing, New York, NY,  1987,  462\u2013470","DOI":"10.1145\/28395.28445"},{"key":"RAN","unstructured":"D. Angluin,  Lecture notes on the complexity of some problems in number theory, Tech. Report, 243, Yale University, Dept. of Computer Science, New Haven, CT,  1982"},{"key":"RANVA","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90045-X"},{"key":"RBA","doi-asserted-by":"crossref","unstructured":"L. Babai,  Trading group theory for randomness,  Proc. 17th Symposium on Theory of Computing, Providence, RI,  1985,  421\u2013429","DOI":"10.1145\/22145.22192"},{"key":"RBAMO","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"RBEGO","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-34805-0_19"},{"key":"RBEGOWI","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, S. Goldwasser, A. Wigderson,  Completeness theorems for non-cryptographic fault-tolerant distributed computations,  Proc. 20th Annual ACM Symposium on Theory of Computing, Chicago, IL,  1988,  1\u201310","DOI":"10.1145\/62212.62213"},{"key":"RBEMI","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-34805-0_48"},{"key":"RBEMIOS","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Micali, R. Ostrowsky,  Perfect zero-knowledge in constant rounds,  Proc. 22nd Annual ACM Symposium on the Theory of Computing, Baltimore, MD,  1990,  482\u2013493","DOI":"10.1145\/100216.100283"},{"key":"RBLBLSH","doi-asserted-by":"publisher","DOI":"10.1137\/0215025"},{"key":"RBLFEMI","doi-asserted-by":"crossref","unstructured":"M. Blum, P. Feldman, S. Micali,  Non-interactive zero-knowledge proof systems and applications,  Proc. 20th Annual ACM Symposium on Theory of Computing, Chicago, IL,  1988,  103\u2013112","DOI":"10.1145\/62212.62222"},{"key":"RBLMI","doi-asserted-by":"publisher","DOI":"10.1137\/0213053"},{"key":"RBL1","first-page":"133","author":"Blum M.","year":"1982","journal-title":"IEEE COMPCON"},{"key":"RBL2","unstructured":"Manuel Blum,  How to prove a theorem so no one else can claim it,  Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Berkeley, Calif., 1986), Amer. Math. Soc., Providence, RI,  1987,  1444\u20131451 91h:681410672.94005"},{"key":"RBOHAZA","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90232-8"},{"key":"RCHCRDA","doi-asserted-by":"crossref","unstructured":"D. Chaum, C. Crepau, I. Damg\u00e4rd,  Multiparty unconditionally secure protocols,  Proc. 20th Annual ACM Symposium on Theory of Computing, Chicago, IL,  1988,  11\u201319","DOI":"10.1145\/62212.62214"},{"key":"RCO","doi-asserted-by":"crossref","unstructured":"S. A. Cook,  The complexity of theorem-proving procedures,  Proc. 3rd Annual ACM Symposium on Theory of Computing, New York, NY,  151\u2013158 0253.68020","DOI":"10.1145\/800157.805047"},{"key":"RDEMIPE1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48184-2_5"},{"key":"RDEMIPE2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48184-2_5"},{"key":"RDEYU","volume-title":"Advances in Cryptology\u2013Crypto 90","author":"De Santis A.","year":"1990"},{"key":"RERSP","unstructured":"P. Erdos, J. Spencer, Probabilistic methods in combinatorics, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1974, 106\u201352:28950308.05001"},{"key":"RFEFISH","doi-asserted-by":"crossref","unstructured":"U. Feige, A. Fiat, A. Shamir,  Zero-knowledge proofs of identity,  Proc. 19th Annual ACM Symposium on Theory of Computing, New York, NY,  1987,  210\u2013217","DOI":"10.1145\/28395.28419"},{"key":"RFELASH","doi-asserted-by":"crossref","unstructured":"U. Feige, A. Lapidot, A. Shamir,  Multiple non-interactive zero-knowledge proofs based on a single random string,  Proc. 31st Annual IEEE Symposium on Foundations of Computer Science, St. Louis, MO,  1990,  308\u2013317","DOI":"10.1109\/FSCS.1990.89549"},{"key":"RFO","doi-asserted-by":"crossref","unstructured":"L. Fortnow,  The complexity of perfect zero-knowledge,  Proc. 19th Annual ACM Symposium on Theory of Computing, New York, NY,  1987,  204\u2013209","DOI":"10.1145\/28395.28418"},{"key":"RFUGOMASIZA","unstructured":"M. Furer, O. Goldreich, Y. Mansour, M. Sipser, S. Zachos,  S.  Micali,  On completeness and soundness in interactive proof systems,  Advances in Computing Research, Vol. 5. Randomness and Computation, JAI Press Inc., Greenwich, CT,  429\u2013442"},{"key":"RGAJO","volume-title":"Computers and intractability","author":"Garey M.","year":"1979"},{"key":"RGOGOMI","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6503"},{"key":"RGOKI","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, J. Kilian,  Almost all primes can be quickly certified,  Proc. 18th Annual ACM Symposium on Theory of Computing, Berkeley, CA,  1986,  316\u2013329","DOI":"10.1145\/12130.12162"},{"key":"RGOMI1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"RGOMI2","unstructured":"S. Goldwasser, S. Micali,  Proofs with untrusted oracles, manuscript"},{"key":"RGOMIRA","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"RGOMIRI","doi-asserted-by":"publisher","DOI":"10.1137\/0217017"},{"key":"RGOMIWI1","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Micali, A. Wigderson,  Proofs that yield nothing but their validity and a methodology of cryptographic design,  Proc. 27th Annual IEEE Symposium on Foundations of Computer Science, Toronto, Ontario, Canada,  1986,  174\u2013187","DOI":"10.1109\/SFCS.1986.47"},{"key":"RGOMIWI2","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Micali, A. Wigderson,  How to play any mental game,  Proc. 19th Annual ACM Symposium on Theory of Computing, New York, NY,  1987,  218\u2013229","DOI":"10.1145\/28395.28420"},{"key":"RGOSI","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, M. Sipser,  Private coins versus public coins in interactive proof\u2013systems,  Proc. 18th Symposium on Theory of Computing, Berkeley, CA,  1986,  59\u201368","DOI":"10.1145\/12130.12137"},{"key":"RKALI","first-page":"191","volume":"28","author":"Karp R.","year":"1982","journal-title":"Enseign. Math. (2)"},{"key":"RKIMIOS","doi-asserted-by":"crossref","unstructured":"J. Kilian, S. Micali, R. Ostrowsky,  Minimum resource zero-knowledge,  Proc. 30th Annual IEEE Symposium on Foundations of Computer Science, Reserach Triangle Park, NC,  1989,  474\u2013479","DOI":"10.1109\/SFCS.1989.63521"},{"key":"RMISH","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-34799-2_18"},{"key":"RNAYU","doi-asserted-by":"crossref","unstructured":"M. Naor, M. Yung,  Public-key cryptosystems provably secure against chosen cypher-text attack,  Proc. 22nd Symposium on Theory of Computing, Baltimore, MD,  1990,  427\u2013437","DOI":"10.1145\/100216.100273"},{"key":"RNIZU","volume-title":"An introduction to the theory of numbers","author":"Niven Ivan","year":"1960"},{"key":"RRA1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-314X(80)90084-0"},{"key":"RRA2","unstructured":"M. Rabin,  Digitalized signatures and public-key functions as intractable as factorization, Tech. Report, MIT\/LCS\/TR-212, MIT Laboratory for Computer Science, Massachussetts Institute of Technology, Cambridge, MA,  1978"},{"key":"RRA3","unstructured":"M. Rabin,  Transaction protection by beacons, Tech. Report, 29-81, Aiken Computation Laboratory, Harvard University, Cambridge, MA,  1981"},{"key":"RSH","volume-title":"Solved and unsolved problems in number theory","author":"Shanks D.","year":"1976"},{"key":"RSOST","doi-asserted-by":"publisher","DOI":"10.1137\/0206006"},{"key":"RYA","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0220068","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:54:21Z","timestamp":1787338461000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0220068"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,12]]},"references-count":46,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1991,12]]}},"alternative-id":["10.1137\/0220068"],"URL":"https:\/\/doi.org\/10.1137\/0220068","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,12]]}}}