{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:47Z","timestamp":1787337587575,"version":"build-2736575974"},"reference-count":55,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>We investigate structural properties of interactive perfect zero-knowledge (PZK) proofs. Specifically, we look into the closure properties of PZK languages under monotone boolean formula composition. This gives rise to new protocol techniques. We show that interactive PZK for random self-reducible (RSR) (and for co-RSR) languages is closed under monotone boolean formula composition. Namely, we present PZK proofs for monotone boolean formulae whose atoms are statements about membership in a PZK language which is RSR (or whose complement is RSR). We also discuss extensions, recent applications, and generalizations of the techniques.<\/jats:p>","DOI":"10.1137\/s0097539798346123","type":"journal-article","created":{"date-parts":[[2008,7,23]],"date-time":"2008-07-23T18:11:18Z","timestamp":1216836678000},"page":"1300-1329","source":"Crossref","is-referenced-by-count":4,"title":["On Monotone Formula Composition of Perfect Zero-Knowledge Languages"],"prefix":"10.1137","volume":"38","author":[{"given":"Alfredo","family":"De Santis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giovanni","family":"Di Crescenzo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giuseppe","family":"Persiano","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moti","family":"Yung","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,7,23]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90018-4"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90006-Q"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"M. Bellare and O. Goldreich,\n                      On defining proofs of knowledge\n                      , in Advances in Cryptology\u2014CRYPTO '92, Lecture Notes in Comput. Sci. 740, E. Brickell, ed., Springer-Verlag, Berlin, 1993, pp. 390\u2013420.","DOI":"10.1007\/3-540-48071-4_28"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"M. Bellare and S. Goldwasser,\n                      A new paradigm for digital signatures and message authentication based on non-interactive zero-knowledge proofs\n                      , in Advances in Cryptology\u2014CRYPTO '89, Lecture Notes in Comput. Sci. 425, G. Brassard, ed., Springer-Verlag, New York, 1989, pp. 194\u2013211.","DOI":"10.1007\/0-387-34805-0_19"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Micali, and R. Ostrovsky,\n                      Perfect zero knowledge in constant rounds,\n                      in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990, pp. 482\u2013493.","DOI":"10.1145\/100216.100283"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Micali, and R. Ostrovsky,\n                      The (true) complexity of statistical zero knowledge\n                      , in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990, pp. 494\u2013502.","DOI":"10.1145\/100216.100285"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"M. Bellare and E. Petrank,\n                      Making zero-knowledge provers efficient,\n                      in Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992, pp. 711\u2013722.","DOI":"10.1145\/129712.129781"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, O. Goldreich, S. Goldwasser, J. H\u00e5stad, S. Micali, and P. Rogaway,\n                      Everything provable is provable in zero-knowledge\n                      , in Advances in Cryptology\u2014CRYPTO '88, Lecture Notes in Comput. Sci. 403, Springer-Verlag, Berlin, 1988, pp. 37\u201356.","DOI":"10.1007\/0-387-34799-2_4"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"G. R. Blackley,\n                      Safeguarding cryptographic keys\n                      , in Proceedings of the 1979 National Computer Conference, American Federation of Information Processing Societies, 1979, pp. 313\u2013317.","DOI":"10.1109\/MARK.1979.8817296"},{"key":"R10","unstructured":"M. Blum,\n                      How to prove a theorem so no one else can claim it\n                      , in Proceedings of the International Congress of Mathematicians, Berkeley, CA, 1986, pp. 1444\u20131451."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"M. Blum,\n                      Program result checking: A new approach to making programs more reliable\n                      , in Proceedings of the 20th Annual International Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci. 700, Springer-Verlag, London, UK, 1993, pp. 1\u201314.","DOI":"10.1007\/3-540-56939-1_57"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/0220068"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"M. Blum, P. Feldman, and S. Micali,\n                      Non-interactive zero-knowledge and applications\n                      , in Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988, pp. 103\u2013112.","DOI":"10.1145\/62212.62222"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200880"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90232-8"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/BF00196727"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90005-0"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90259-5"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293350"},{"key":"R20","first-page":"111","volume":"8","author":"Cramer R.","year":"1995","journal-title":"CWI Quarterly","ISSN":"https:\/\/id.crossref.org\/issn\/0922-5366","issn-type":"print"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"I. Damgard,\n                      Interactive hashing can simplify zero-knowledge protocol design without computational assumptions\n                      , in Advances in Cryptology\u2014CRYPTO '93, Lecture Notes in Comput. Sci. 773, D. Stinson, ed., Springer-Verlag, Berlin, 1994, pp. 100\u2013109.","DOI":"10.1007\/3-540-48329-2_9"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90237-2"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"A. De Santis, G. Di Crescenzo, and G. Persiano,\n                      On NC$^1$ Boolean circuit composition of non-interactive perfect zero-knowledge\n                      , in Proceedings of the 29th Annual International Symposium on Mathematical Foundations of Computer Science 2004 (MFCS 2004), Lecture Notes in Comput. Sci. 3153, Springer-Verlag, Berlin, 2004, pp. 356\u2013367.","DOI":"10.1007\/978-3-540-28629-5_26"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"A. De Santis, G. Di Crescenzo, and G. Persiano,\n                      Communication-efficient anonymous group identification\n                      , in Proceedings of the Fifth Annual ACM Conference on Computer and Communication Security (CCS 98), 1998, pp. 73\u201382.","DOI":"10.1145\/288090.288110"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00010-1"},{"key":"R26","unstructured":"A. De Santis, G. Di Crescenzo, G. Persiano, and M. Yung,\n                      On monotone formula closure of SZK\n                      , in Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS 94), Santa Fe, NM, 1994, pp. 453\u2013464."},{"key":"R27","doi-asserted-by":"crossref","unstructured":"A. De Santis, S. Micali, and G. Persiano,\n                      Non-interactive zero-knowledge proof systems\n                      , in Advances in Cryptology\u2014CRYPTO '87, Lecture Notes in Comput. Sci. 293, C. Pomerance, ed., Springer-Verlag, Berlin, 1998, pp. 52\u201372.","DOI":"10.1007\/3-540-48184-2_5"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"A. De Santis and G. Persiano,\n                      Zero-knowledge proofs of knowledge without interaction,\n                      in Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, 1992, pp. 427\u2013437.","DOI":"10.1109\/SFCS.1992.267809"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"A. De Santis and M. Yung,\n                      Cryptographic applications of the non-interactive metaproof and many-prover systems,\n                      in Advances in Cryptology\u2014CRYPTO '90, Lecture Notes in Comput. Sci. 537, A. Menezes and S. Vanstone, eds., Springer-Verlag, Berlin, 1991, pp. 366\u2013377.","DOI":"10.1007\/3-540-38424-3_27"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"G. Di Crescenzo, K. Sakurai, and M. Yung,\n                      On zero-knowledge proofs: From membership to decision\n                      , in Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC 2000), Portland, OR, 1999, pp. 255\u2013264.","DOI":"10.1145\/335305.335336"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1007\/BF02351717"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1007\/BF00208002"},{"key":"R33","unstructured":"L. Fortnow,\n                      The complexity of perfect zero-knowledge\n                      , in Randomness and Computation, Advances in Computing Research 5, JAI Press, Greenwich, CT, 1989, pp. 327\u2013343."},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1137\/0218049"},{"key":"R35","unstructured":"M. Garey and D. Johnson,\n                      Computers and Intractability, a Guide to the Theory of NP-Completeness\n                      , W. H. Freeman, New York, 1983."},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791220688"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1007\/BF02620137"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1007\/BF00195207"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280524"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050019"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"R43","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and M. Yung,\n                      Direct minimum knowledge computations\n                      , in Advances in Cryptology\u2014CRYPTO '87, Lecture Notes in Comput. Sci. 293, C. Pomerance, ed., Springer-Verlag, London, 1987, pp. 40\u201351.","DOI":"10.1007\/3-540-48184-2_4"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1007\/BF02620229"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1007\/s001459900018"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1007\/s001459900037"},{"key":"R48","doi-asserted-by":"crossref","unstructured":"M. Naor and M. Yung,\n                      Public-key cryptosystems provably secure against chosen ciphertext attacks\n                      , in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990, pp. 427\u2013437.","DOI":"10.1145\/100216.100273"},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1664"},{"key":"R50","doi-asserted-by":"crossref","unstructured":"E. Petrank and G. Tardos,\n                      On the knowledge complexity of NP\n                      , in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 494\u2013503.","DOI":"10.1109\/SFCS.1996.548508"},{"key":"R51","doi-asserted-by":"crossref","unstructured":"A. Sahai and S. Vadhan,\n                      A complete promise problem for statistical zero-knowledge\n                      , in Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, 1997, p. 448.","DOI":"10.1109\/SFCS.1997.646133"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"},{"key":"R53","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"R54","doi-asserted-by":"crossref","unstructured":"M. Tompa and H. Woll,\n                      Random self-reducibility and zero-knowledge interactive proofs of possession of information\n                      , in Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, 1987, pp. 472\u2013482.","DOI":"10.1109\/SFCS.1987.49"},{"key":"R55","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90016-6"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539798346123","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:18:57Z","timestamp":1787336337000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539798346123"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":55,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/S0097539798346123"],"URL":"https:\/\/doi.org\/10.1137\/s0097539798346123","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}