{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T23:46:38Z","timestamp":1769730398453,"version":"3.49.0"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2004,11,1]],"date-time":"2004-11-01T00:00:00Z","timestamp":1099267200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2004,11]]},"abstract":"<jats:p>\n            Concurrent executions of a zero-knowledge protocol by a single prover (with one or more verifiers) may leak information and may not be zero-knowledge\n            <jats:italic>in toto<\/jats:italic>\n            . In this article, we study the problem of maintaining zero-knowledge.We introduce the notion of an (\u03b1, \u03b2)\n            <jats:italic>timing constraint<\/jats:italic>\n            : for any two processors\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            and\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            , if\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            measures \u03b1 elapsed time on its local clock and\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            measures \u03b2 elapsed time on its local clock, and\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            starts\n            <jats:italic>after<\/jats:italic>\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            does, then\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            will finish after\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            does. We show that if the adversary is constrained by an (\u03b1, \u03b2) assumption then there exist four-round almost concurrent zero-knowledge interactive proofs and perfect concurrent zero-knowledge arguments for every language in\n            <jats:italic>NP<\/jats:italic>\n            . We also address the more specific problem of\n            <jats:italic>Deniable Authentication<\/jats:italic>\n            , for which we propose several particularly efficient solutions. Deniable Authentication is of independent interest, even in the sequential case; our concurrent solutions yield sequential solutions\n            <jats:italic>without recourse to timing<\/jats:italic>\n            , that is, in the standard model.\n          <\/jats:p>","DOI":"10.1145\/1039488.1039489","type":"journal-article","created":{"date-parts":[[2005,1,26]],"date-time":"2005-01-26T16:35:53Z","timestamp":1106757353000},"page":"851-898","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":102,"title":["Concurrent zero-knowledge"],"prefix":"10.1145","volume":"51","author":[{"given":"Cynthia","family":"Dwork","sequence":"first","affiliation":[{"name":"Microsoft Research SVC, Mountain View, California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moni","family":"Naor","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amit","family":"Sahai","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles, California"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2004,11]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Agrawal M. Kayal N. and Saxena N. 2002. Primes is in P. Manuscript.]]  Agrawal M. Kayal N. and Saxena N. 2002. Primes is in P. Manuscript.]]"},{"key":"e_1_2_1_2_1","unstructured":"Bach E. and Shallit J. 1996. Algorithmic Number Theory: Efficient Algorithms. MIT Press Cambridge Mass.]]   Bach E. and Shallit J. 1996. Algorithmic Number Theory: Efficient Algorithms. MIT Press Cambridge Mass.]]"},{"key":"e_1_2_1_3_1","first-page":"106","volume-title":"Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif.","author":"Barak B.","year":"2001","unstructured":"Barak , B. 2001 . How to Go Beyond the Black-Box Simulation Barrier . In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. , pp. 106 -- 115 .]] Barak, B. 2001. How to Go Beyond the Black-Box Simulation Barrier. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 106--115.]]"},{"key":"e_1_2_1_4_1","unstructured":"Bellare M. and Goldwasser S. 1996. Encapsulated key escrow. Manuscript Nov. (Earlier version was MIT Laboratory for Computer Science Technical Report 688 April 1996.)]]   Bellare M. and Goldwasser S. 1996. Encapsulated key escrow. Manuscript Nov. (Earlier version was MIT Laboratory for Computer Science Technical Report 688 April 1996.)]]"},{"key":"e_1_2_1_5_1","first-page":"280","volume-title":"Advances in Cryptology---EUROCRYPT '97 Proceedings. Lecture Notes in Computer Science","volume":"1233","author":"Bellare M.","unstructured":"Bellare , M. , Jakobsson , M. , and Yung , M . 1997. Round-optimal zero-knowledge arguments based on any one-way function . In Advances in Cryptology---EUROCRYPT '97 Proceedings. Lecture Notes in Computer Science , vol. 1233 . Springer-Verlag, New York , pp. 280 -- 305 .]] Bellare, M., Jakobsson, M., and Yung, M. 1997. Round-optimal zero-knowledge arguments based on any one-way function. In Advances in Cryptology---EUROCRYPT '97 Proceedings. Lecture Notes in Computer Science, vol. 1233. Springer-Verlag, New York, pp. 280--305.]]"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/BF00208000","article-title":"Certifying permutations: Noninteractive zero-knowledge based on any trapdoor permutation","volume":"9","author":"Bellare M.","year":"1996","unstructured":"Bellare , M. , and Yung , M. 1996 . Certifying permutations: Noninteractive zero-knowledge based on any trapdoor permutation . J. Cryptology 9 , 3, 149 -- 166 .]] Bellare, M., and Yung, M. 1996. Certifying permutations: Noninteractive zero-knowledge based on any trapdoor permutation. J. Cryptology 9, 3, 149--166.]]","journal-title":"J. Cryptology"},{"key":"e_1_2_1_7_1","first-page":"1","volume-title":"Proceedings of the 20th Symposium on Theory of Computing. ACM","author":"Ben-Or M.","unstructured":"Ben-Or , M. , Goldwasser , S. , and Wigderson , A . 1988. Completeness theorems for non-cryptographic fault-tolerant distributed computation . In Proceedings of the 20th Symposium on Theory of Computing. ACM , New York , pp. 1 -- 10 .]] 10.1145\/62212.62213 Ben-Or, M., Goldwasser, S., and Wigderson, A. 1988. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proceedings of the 20th Symposium on Theory of Computing. ACM, New York, pp. 1--10.]] 10.1145\/62212.62213"},{"key":"e_1_2_1_8_1","volume-title":"Advances in Cryptology---CRYPTO '90","volume":"537","author":"Beth T.","unstructured":"Beth , T. , and Desmedt , E . 1991. Identification tokens--or: Solving the chess grandmaster problem . In Advances in Cryptology---CRYPTO '90 . Lecture Notes in Computer Science , vol. 537 . Springer-Verlag, New York, pp. 169--177.]] Beth, T., and Desmedt, E. 1991. Identification tokens--or: Solving the chess grandmaster problem. In Advances in Cryptology---CRYPTO '90. Lecture Notes in Computer Science, vol. 537. Springer-Verlag, New York, pp. 169--177.]]"},{"key":"e_1_2_1_10_1","first-page":"1444","volume-title":"Proceedings of the International Congress of Mathematicians","author":"Blum M.","year":"1986","unstructured":"Blum , M. 1986 . How to prove a theorem so no one else can claim it . In Proceedings of the International Congress of Mathematicians ( Berkeley, Calif.). pp. 1444 -- 1451 .]] Blum, M. 1986. How to prove a theorem so no one else can claim it. In Proceedings of the International Congress of Mathematicians (Berkeley, Calif.). pp. 1444--1451.]]"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220068"},{"key":"e_1_2_1_12_1","first-page":"103","volume-title":"Proceedings of the 20th ACM Symposium on the Theory of Computing","author":"Blum M.","unstructured":"Blum M. , Feldman , P. , and Micali , S . 1988. Non-interactive zero-knowledge proof systems . In Proceedings of the 20th ACM Symposium on the Theory of Computing ( Chicago, Ill.). ACM, New York , pp. 103 -- 112 .]] 10.1145\/62212.62222 Blum M., Feldman, P., and Micali, S. 1988. Non-interactive zero-knowledge proof systems. In Proceedings of the 20th ACM Symposium on the Theory of Computing (Chicago, Ill.). ACM, New York, pp. 103--112.]] 10.1145\/62212.62222"},{"key":"e_1_2_1_13_1","first-page":"236","volume-title":"Lecture Notes in Computer Science","volume":"1880","author":"Boneh D.","unstructured":"Boneh , D. , and Naor , M . 2000. Timed commitments. In Advances in Cryptology---CRYPTO 2000 . Lecture Notes in Computer Science , vol. 1880 . Springer-Verlag, New York , pp. 236 -- 254 .]] Boneh, D., and Naor, M. 2000. Timed commitments. In Advances in Cryptology---CRYPTO 2000. Lecture Notes in Computer Science, vol. 1880. Springer-Verlag, New York, pp. 236--254.]]"},{"key":"e_1_2_1_14_1","first-page":"344","volume-title":"Lecture Notes in Computer Science","volume":"765","author":"Brands S.","unstructured":"Brands , S. , and Chaum , D . 1994. Distance-bounding protocols. In Advances in Cryptology---EUROCRYPT'93 . Lecture Notes in Computer Science , vol. 765 . Springer Verlag, New York , pp. 344 -- 359 .]] Brands, S., and Chaum, D. 1994. Distance-bounding protocols. In Advances in Cryptology---EUROCRYPT'93. Lecture Notes in Computer Science, vol. 765. Springer Verlag, New York, pp. 344--359.]]"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90005-0"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90259-5"},{"key":"e_1_2_1_17_1","first-page":"136","volume-title":"Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif.","author":"Canetti R.","year":"2001","unstructured":"Canetti , R. 2001 . Universally composable security: A new paradigm for cryptographic protocols . In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. , pp. 136 -- 145 .]] Canetti, R. 2001. Universally composable security: A new paradigm for cryptographic protocols. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 136--145.]]"},{"key":"e_1_2_1_18_1","first-page":"90","volume-title":"Advances in Cryptology---Crypto'97 Proceeding","author":"Canetti R.","unstructured":"Canetti , R. , Dwork , C. , Naor , M. , Ostrovsky , R. 1997. Deniable encryption . In Advances in Cryptology---Crypto'97 Proceeding . Springer-Verlag , New York , pp. 90 -- 104 .]] Canetti, R., Dwork, C., Naor, M., Ostrovsky, R. 1997. Deniable encryption. In Advances in Cryptology---Crypto'97 Proceeding. Springer-Verlag, New York, pp. 90--104.]]"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 32 Annual ACM Symposium on Theory of Computing (Portland, Ore., May). ACM, New York (Updated version available at the Cryptology ePrint Archive, record 1999\/022","author":"Canetti R.","unstructured":"Canetti , R. , Goldreich , O. , Goldwasser , S. , and Micali , S . 2000. Resettable zero-knowledge . In Proceedings of the 32 Annual ACM Symposium on Theory of Computing (Portland, Ore., May). ACM, New York (Updated version available at the Cryptology ePrint Archive, record 1999\/022 , http:\/\/eprint.iacr.org\/.)]] 10.1145\/335305.335334 Canetti, R., Goldreich, O., Goldwasser, S., and Micali, S. 2000. Resettable zero-knowledge. In Proceedings of the 32 Annual ACM Symposium on Theory of Computing (Portland, Ore., May). ACM, New York (Updated version available at the Cryptology ePrint Archive, record 1999\/022, http:\/\/eprint.iacr.org\/.)]] 10.1145\/335305.335334"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701392949"},{"key":"e_1_2_1_21_1","series-title":"Lecture Notes in Computer Science","first-page":"212","volume-title":"Advances in Cryptology---CRYPTO'89","author":"Chaum D.","unstructured":"Chaum , D. , and van Antwerpen , H. 1990. Undeniable signatures . In Advances in Cryptology---CRYPTO'89 . Lecture Notes in Computer Science , vol. 435 . Springer-Verlag , New York , pp. 212 -- 216 .]] Chaum, D., and van Antwerpen, H. 1990. Undeniable signatures. In Advances in Cryptology---CRYPTO'89. Lecture Notes in Computer Science, vol. 435. Springer-Verlag, New York, pp. 212--216.]]"},{"key":"e_1_2_1_22_1","first-page":"470","volume-title":"Lecture Notes in Computer Science","volume":"576","author":"Chaum D.","unstructured":"Chaum , D. , van Heijst , E. , and Pfitzmann , B . 1992. Cryptographically strong undeniable signatures, unconditionally secure for the signer. In Advances in Cryptology---CRYPTO'91 . Lecture Notes in Computer Science , vol. 576 . Springer-Verlag, New York , pp. 470 -- 484 .]] Chaum, D., van Heijst, E., and Pfitzmann, B. 1992. Cryptographically strong undeniable signatures, unconditionally secure for the signer. In Advances in Cryptology---CRYPTO'91. Lecture Notes in Computer Science, vol. 576. Springer-Verlag, New York, pp. 470--484.]]"},{"key":"e_1_2_1_23_1","volume-title":"Advances in Cryptology---CRYPTO '96","volume":"1109","author":"Cramer R.","unstructured":"Cramer , R. , and Damg\u00e5rd , I . 1996. New generation of secure and practical RSA-based signatures . In Advances in Cryptology---CRYPTO '96 . Lecture Notes in Computer Science , vol. 1109 . Springer-Verlag, New York, pp. 173--185.]] Cramer, R., and Damg\u00e5rd, I. 1996. New generation of secure and practical RSA-based signatures. In Advances in Cryptology---CRYPTO '96. Lecture Notes in Computer Science, vol. 1109. Springer-Verlag, New York, pp. 173--185.]]"},{"key":"e_1_2_1_24_1","first-page":"13","volume-title":"Lecture Notes in Computer Science","volume":"1462","author":"Cramer R.","unstructured":"Cramer , R. , and Shoup , V . 1998. A practical public-key cryptosystem provably secure against adaptive chosen ciphertext attack. Advances in Cryptology---CRYPTO'98 . Lecture Notes in Computer Science , vol. 1462 . Springer-Verlag, New York , pp. 13 -- 25 .]] Cramer, R., and Shoup, V. 1998. A practical public-key cryptosystem provably secure against adaptive chosen ciphertext attack. Advances in Cryptology---CRYPTO'98. Lecture Notes in Computer Science, vol. 1462. Springer-Verlag, New York, pp. 13--25.]]"},{"key":"e_1_2_1_25_1","first-page":"418","volume-title":"Advances in Cryptology---EUROCRYPT","author":"Damg\u00e5rd I.","year":"2000","unstructured":"Damg\u00e5rd , I. 2000. Efficient concurrent zero-knowledge in the auxiliary string model . In Advances in Cryptology---EUROCRYPT 2000 . Lecture Notes in Computer Science, vol. 1807 . Springer , pp. 418 -- 430 .]] Damg\u00e5rd, I. 2000. Efficient concurrent zero-knowledge in the auxiliary string model. In Advances in Cryptology---EUROCRYPT 2000. Lecture Notes in Computer Science, vol. 1807. Springer, pp. 418--430.]]"},{"key":"e_1_2_1_26_1","first-page":"141","volume-title":"Proc. 30th Annual ACM Symposium on the Theory of Computing","author":"Di Crescenzo G.","unstructured":"Di Crescenzo , G. , Ishai , Y. , and Ostrovsky , R . 1998. Non-interactive and non-malleable commitment . Proc. 30th Annual ACM Symposium on the Theory of Computing , Dallas , pp. 141 -- 150 .]] 10.1145\/276698.276722 Di Crescenzo, G., Ishai, Y., and Ostrovsky, R. 1998. Non-interactive and non-malleable commitment. Proc. 30th Annual ACM Symposium on the Theory of Computing, Dallas, pp. 141--150.]] 10.1145\/276698.276722"},{"key":"e_1_2_1_27_1","first-page":"485","volume-title":"Lecture Notes in Computer Science","volume":"1666","author":"Di Crescenzo G.","unstructured":"Di Crescenzo , G. , and Ostrovsky , R . 1999. On concurrent zero-knowledge with pre-processing. In Advances in Cryptology---CRYPTO'99 . Lecture Notes in Computer Science , vol. 1666 . Springer-Verlag, New York , pp. 485 -- 502 .]] Di Crescenzo, G., and Ostrovsky, R. 1999. On concurrent zero-knowledge with pre-processing. In Advances in Cryptology---CRYPTO'99. Lecture Notes in Computer Science, vol. 1666. Springer-Verlag, New York, pp. 485--502.]]"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795291562"},{"key":"e_1_2_1_29_1","first-page":"139","volume-title":"Lecture Notes in Computer Science","volume":"740","author":"Dwork C.","unstructured":"Dwork , C. , and Naor , M . 1993. Pricing via processing-or-combatting junk mail. In Advances in Cryptology---CRYPTO'92 . Lecture Notes in Computer Science , vol. 740 . Springer-Verlag, New York , pp. 139 -- 147 .]] Dwork, C., and Naor, M. 1993. Pricing via processing-or-combatting junk mail. In Advances in Cryptology---CRYPTO'92. Lecture Notes in Computer Science, vol. 740. Springer-Verlag, New York, pp. 139--147.]]"},{"key":"e_1_2_1_30_1","unstructured":"Dwork C. and Naor M. 1996. Method for message authentication from non-malleable crypto systems. US Patent No. 05539826 issued Aug. 29th 1996.]]  Dwork C. and Naor M. 1996. Method for message authentication from non-malleable crypto systems. US Patent No. 05539826 issued Aug. 29th 1996.]]"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/s001459900043","article-title":"An efficient existentially unforgeable signature scheme and its applications","volume":"11","author":"Dwork C.","year":"1998","unstructured":"Dwork , C. , and Naor , M. 1998 . An efficient existentially unforgeable signature scheme and its applications . J. Crypt. , 11 , 187 -- 208 .]] Dwork, C., and Naor, M. 1998. An efficient existentially unforgeable signature scheme and its applications. J. Crypt., 11, 187--208.]]","journal-title":"J. Crypt."},{"key":"e_1_2_1_32_1","first-page":"283","volume-title":"Proceedings of the 41st Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif.","author":"Dwork C.","unstructured":"Dwork , C. , and Naor , M . 2000. Zaps and their applications . In Proceedings of the 41st Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. , pp. 283 -- 293 .]] Dwork, C., and Naor, M. 2000. Zaps and their applications. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 283--293.]]"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950623"},{"key":"e_1_2_1_34_1","first-page":"409","volume-title":"Proceedings of the 30th ACM Symposium on the Theory of Computing. ACM","author":"Dwork C.","unstructured":"Dwork , C. , Naor , M. , and Sahai , A . 1998. Concurrent zero-knowledge . In Proceedings of the 30th ACM Symposium on the Theory of Computing. ACM , New York , pp. 409 -- 418 .]] 10.1145\/276698.276853 Dwork, C., Naor, M., and Sahai, A. 1998. Concurrent zero-knowledge. In Proceedings of the 30th ACM Symposium on the Theory of Computing. ACM, New York, pp. 409--418.]] 10.1145\/276698.276853"},{"key":"e_1_2_1_35_1","first-page":"442","volume-title":"Lecture Notes in Computer Science","volume":"1462","author":"Dwork C.","unstructured":"Dwork , C. , and Sahai , A . 1998. Concurrent zero-knowledge: Reducing the need for timing constraints . Lecture Notes in Computer Science , vol. 1462 . Springer-Verlag, New York , pp. 442 -- 457 .]] Dwork, C., and Sahai, A. 1998. Concurrent zero-knowledge: Reducing the need for timing constraints. Lecture Notes in Computer Science, vol. 1462. Springer-Verlag, New York, pp. 442--457.]]"},{"key":"e_1_2_1_36_1","first-page":"101","volume-title":"Proceedings of the 1st Theory of Cryptography Conference. Springer-Verlag","author":"Dwork C.","unstructured":"Dwork , C. , Shaltiel , R. , Smith , A. , and Trevisan , L . 2003. An analysis of a two-round zero-knowledge protocol . In Proceedings of the 1st Theory of Cryptography Conference. Springer-Verlag , New York , pp. 101 -- 120 .]] Dwork, C., Shaltiel, R., Smith, A., and Trevisan, L. 2003. An analysis of a two-round zero-knowledge protocol. In Proceedings of the 1st Theory of Cryptography Conference. Springer-Verlag, New York, pp. 101--120.]]"},{"key":"e_1_2_1_37_1","first-page":"322","volume-title":"Proceedings of the 34th Annual ACM Symposium on Theory of Computing. ACM","author":"Dwork C.","unstructured":"Dwork , C. , and Stockmeyer , L . 2002. Two-round zero knowledge and proof auditors . In Proceedings of the 34th Annual ACM Symposium on Theory of Computing. ACM , New York , pp. 322 -- 331 .]] 10.1145\/509907.509958 Dwork, C., and Stockmeyer, L. 2002. Two-round zero knowledge and proof auditors. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing. ACM, New York, pp. 322--331.]] 10.1145\/509907.509958"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02351717"},{"key":"e_1_2_1_40_1","first-page":"416","volume-title":"Proceedings of the 22nd ACM Symposium on the Theory of Computing. ACM","author":"Feige U.","unstructured":"Feige , U. , and Shamir , A . 1990. Witness indistinguishable and witness hiding protocols . In Proceedings of the 22nd ACM Symposium on the Theory of Computing. ACM , New York , pp. 416 -- 426 .]] 10.1145\/100216.100272 Feige, U., and Shamir, A. 1990. Witness indistinguishable and witness hiding protocols. In Proceedings of the 22nd ACM Symposium on the Theory of Computing. ACM, New York, pp. 416--426.]] 10.1145\/100216.100272"},{"key":"e_1_2_1_41_1","first-page":"526","volume-title":"Lecture Notes in Computer Science","volume":"435","author":"Feige U.","unstructured":"Feige , U. , and Shamir , A . 1989. Zero knowledge proofs of knowledge in two rounds. In Advances in Cryptology---CRYPTO'89 . Lecture Notes in Computer Science , vol. 435 . Springer-Verlag, New York , pp. 526 -- 544 .]] Feige, U., and Shamir, A. 1989. Zero knowledge proofs of knowledge in two rounds. In Advances in Cryptology---CRYPTO'89. Lecture Notes in Computer Science, vol. 435. Springer-Verlag, New York, pp. 526--544.]]"},{"key":"e_1_2_1_42_1","first-page":"308","volume-title":"Proceedings of 31st IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif.","author":"Feige U.","unstructured":"Feige , U. , Lapidot , D. , and Shamir , A . 1990. Multiple non-interactive zero-knowledge proofs based on a single random string . In Proceedings of 31st IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. , pp. 308 -- 317 .]] Feige, U., Lapidot, D., and Shamir, A. 1990. Multiple non-interactive zero-knowledge proofs based on a single random string. In Proceedings of 31st IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 308--317.]]"},{"key":"e_1_2_1_43_1","first-page":"132","volume-title":"Lecture Notes in Computer Science","volume":"1294","author":"Genaro R.","unstructured":"Genaro , R. , Krawczyk , H. , and Rabin , T . 1997. RSA-based undeniable signatures. In Advances in Cryptology---CRYPTO'97 . Lecture Notes in Computer Science , vol. 1294 . Springer-Verlag, New York , pp. 132 -- 149 .]] Genaro, R., Krawczyk, H., and Rabin, T. 1997. RSA-based undeniable signatures. In Advances in Cryptology---CRYPTO'97. Lecture Notes in Computer Science, vol. 1294. Springer-Verlag, New York, pp. 132--149.]]"},{"key":"e_1_2_1_44_1","volume-title":"Foundations of Cryptography","author":"Goldreich O.","unstructured":"Goldreich , O. 2001. Foundations of Cryptography , vol. 1 . Cambridge University Press .]] Goldreich, O. 2001. Foundations of Cryptography, vol. 1. Cambridge University Press.]]"},{"key":"e_1_2_1_45_1","first-page":"332","volume-title":"Proceedings of the 34th ACM Symposium on Theory of Computing. ACM","author":"Goldreich O.","year":"2002","unstructured":"Goldreich , O. 2002 . Concurrent zero-knowledge with timing, revisited . In Proceedings of the 34th ACM Symposium on Theory of Computing. ACM , New York , pp. 332 -- 340 .]] 10.1145\/509907.509959 Goldreich, O. 2002. Concurrent zero-knowledge with timing, revisited. In Proceedings of the 34th ACM Symposium on Theory of Computing. ACM, New York, pp. 332--340.]] 10.1145\/509907.509959"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6503"},{"key":"e_1_2_1_47_1","unstructured":"Goldreich O. Goldwasser S. and Micali S. 1999. Interleaved zero-knowledge in the public-key model theory of cryptography library Record 99-15 July. (Available: verb+http:\/\/ philby.ucsd.edu\/1999.html.)]]  Goldreich O. Goldwasser S. and Micali S. 1999. Interleaved zero-knowledge in the public-key model theory of cryptography library Record 99-15 July. (Available: verb+http:\/\/ philby.ucsd.edu\/1999.html.)]]"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF00208001","article-title":"How to construct constant-round zero-knowledge proof systems for NP","volume":"9","author":"Goldreich O.","year":"1996","unstructured":"Goldreich , O. , and Kahan , A. 1996 . How to construct constant-round zero-knowledge proof systems for NP . J. Crypt. 9 , 3, 167 -- 190 .]] Goldreich, O., and Kahan, A. 1996. How to construct constant-round zero-knowledge proof systems for NP. J. Crypt. 9, 3, 167--190.]]","journal-title":"J. Crypt."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791220688"},{"key":"e_1_2_1_50_1","first-page":"218","volume-title":"Proceedings of the 19th ACM Symposium on Theory of Computing. ACM","author":"Goldreich O.","unstructured":"Goldreich , O. , Micali , M. , and Wigderson , A . 1987. How to play any mental game . In Proceedings of the 19th ACM Symposium on Theory of Computing. ACM , New York , pp. 218 -- 229 .]] 10.1145\/28395.28420 Goldreich, O., Micali, M., and Wigderson, A. 1987. How to play any mental game. In Proceedings of the 19th ACM Symposium on Theory of Computing. ACM, New York, pp. 218--229.]] 10.1145\/28395.28420"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF00195207","article-title":"Definitions and properties of zero-knowledge proof systems","volume":"7","author":"Goldreich O.","year":"1994","unstructured":"Goldreich , O. , and Oren , Y. 1994 . Definitions and properties of zero-knowledge proof systems . J. Crypt. 7 , 1 (Winter), 1--32.]] Goldreich, O., and Oren, Y. 1994. Definitions and properties of zero-knowledge proof systems. J. Crypt. 7, 1 (Winter), 1--32.]]","journal-title":"J. Crypt."},{"key":"e_1_2_1_53_1","first-page":"59","volume-title":"Proceedings of the 31st IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif.","author":"Goldreich O.","year":"1991","unstructured":"Goldreich , O. , and Petrank , E . 1991. Quantifying knowledge complexity . In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. , pp. 59 -- 68 .]] 10.1109\/SFCS. 1991 .185349 Goldreich, O., and Petrank, E. 1991. Quantifying knowledge complexity. In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 59--68.]] 10.1109\/SFCS.1991.185349"},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","article-title":"Probabilistic encryption","volume":"28","author":"Goldwasser S.","year":"1984","unstructured":"Goldwasser , S. , and Micali , S. 1984 . Probabilistic encryption . J. Comput. Syst. Sci. 28 ( Apr. ), 270 -- 299 .]] Goldwasser, S., and Micali, S. 1984. Probabilistic encryption. J. Comput. Syst. Sci. 28 (Apr.), 270--299.]]","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217017"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_2_1_58_1","series-title":"Lecture Notes in Computer Science","first-page":"211","volume-title":"Advances in Cryptology---EUROCRYPT'2003","author":"Katz J.","unstructured":"Katz , J. 2003. Efficient and non-malleable proofs of plaintext knowledge and applications . In Advances in Cryptology---EUROCRYPT'2003 . Lecture Notes in Computer Science , vol. 2656 . Springer-Verlag , New York , pp. 211 -- 228 .]] Katz, J. 2003. Efficient and non-malleable proofs of plaintext knowledge and applications. In Advances in Cryptology---EUROCRYPT'2003. Lecture Notes in Computer Science, vol. 2656. Springer-Verlag, New York, pp. 211--228.]]"},{"key":"e_1_2_1_59_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s001459900032","article-title":"An efficient non-interactive zero-knowledge proof system for NP with general assumptions","volume":"11","author":"Kilian J.","year":"1998","unstructured":"Kilian , J. , and Petrank , E. 1998 . An efficient non-interactive zero-knowledge proof system for NP with general assumptions . J. Crypt. 11 , 1, 1 -- 27 .]] Kilian, J., and Petrank, E. 1998. An efficient non-interactive zero-knowledge proof system for NP with general assumptions. J. Crypt. 11, 1, 1--27.]]","journal-title":"J. Crypt."},{"key":"e_1_2_1_60_1","volume-title":"Proceedings of the 33rd annual ACM Symposium on Theory of Computing. ACM","author":"Kilian J.","unstructured":"Kilian , J. , and Petrank , E . 2001. Concurrent zero-knowledge in poly-logarithmic rounds . In Proceedings of the 33rd annual ACM Symposium on Theory of Computing. ACM , New York, 560--569.]] 10.1145\/380752.380851 Kilian, J., and Petrank, E. 2001. Concurrent zero-knowledge in poly-logarithmic rounds. In Proceedings of the 33rd annual ACM Symposium on Theory of Computing. ACM, New York, 560--569.]] 10.1145\/380752.380851"},{"key":"e_1_2_1_61_1","first-page":"484","volume-title":"Proceedings of 39th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif.","author":"Kilian J.","unstructured":"Kilian , J. , Petrank , E. , and Rackoff , C . 1998. Lower bounds for zero knowledge on the internet . In Proceedings of 39th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. , pp. 484 -- 492 .]] Kilian, J., Petrank, E., and Rackoff, C. 1998. Lower bounds for zero knowledge on the internet. In Proceedings of 39th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 484--492.]]"},{"key":"e_1_2_1_62_1","series-title":"Lecture Notes in Computer Science","first-page":"104","volume-title":"RSA, DSS and other systems. In Advances in Cryptology---CRYPTO '96","author":"Kocher P.","unstructured":"Kocher , P. 1996. Timing attacks on implementations of diffie-hellman , RSA, DSS and other systems. In Advances in Cryptology---CRYPTO '96 . Lecture Notes in Computer Science , vol. 1109 . Springer-Verlag , New York , pp. 104 -- 113 .]] Kocher, P. 1996. Timing attacks on implementations of diffie-hellman, RSA, DSS and other systems. In Advances in Cryptology---CRYPTO '96. Lecture Notes in Computer Science, vol. 1109. Springer-Verlag, New York, pp. 104--113.]]"},{"key":"e_1_2_1_63_1","first-page":"143","volume-title":"Proceedings of Network and Distributed Systems Security Symposium (NDSS). Internet Society","author":"Krawczyk H.","unstructured":"Krawczyk , H. , and Rabin , T . 2000. Chameleon hashing signatures . In Proceedings of Network and Distributed Systems Security Symposium (NDSS). Internet Society , pp. 143 -- 154 .]] Krawczyk, H., and Rabin, T. 2000. Chameleon hashing signatures. In Proceedings of Network and Distributed Systems Security Symposium (NDSS). Internet Society, pp. 143--154.]]"},{"key":"e_1_2_1_64_1","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF00196774","article-title":"Bit commitment using pseudo-randomness","volume":"4","author":"Naor M.","year":"1991","unstructured":"Naor , M. 1991 . Bit commitment using pseudo-randomness . J. Crypt. 4 , 151 -- 158 .]] Naor, M. 1991. Bit commitment using pseudo-randomness. J. Crypt. 4, 151--158.]]","journal-title":"J. Crypt."},{"key":"e_1_2_1_65_1","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1007\/3-540-45708-9_31","volume-title":"Advances in Cryptology---CRYPTO '2002","author":"Naor M.","year":"2002","unstructured":"Naor , M. 2002 . Deniable ring authentication . In Advances in Cryptology---CRYPTO '2002 . Lecture Notes in Computer Science. Springer-Verlag, New York , pp. 481 -- 498 .]] Naor, M. 2002. Deniable ring authentication. In Advances in Cryptology---CRYPTO '2002. Lecture Notes in Computer Science. Springer-Verlag, New York, pp. 481--498.]]"},{"key":"e_1_2_1_66_1","first-page":"366","volume-title":"Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif.","author":"Prabhakaran M.","unstructured":"Prabhakaran , M. , Rosen , A. , and Sahai , A . 2002. Concurrent zero knowledge with logarithmic round complexity . In Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. , pp. 366 -- 375 .]] Prabhakaran, M., Rosen, A., and Sahai, A. 2002. Concurrent zero knowledge with logarithmic round complexity. In Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 366--375.]]"},{"key":"e_1_2_1_67_1","volume-title":"Advances in Cryptology---CRYPTO '91","volume":"576","author":"Rackoff C.","unstructured":"Rackoff , C. , and Simon , D . 1992. Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack . In Advances in Cryptology---CRYPTO '91 . Lecture Notes in Computer Science , vol. 576 . Springer-Verlag, New York, pp. 433--444.]] Rackoff, C., and Simon, D. 1992. Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. In Advances in Cryptology---CRYPTO '91. Lecture Notes in Computer Science, vol. 576. Springer-Verlag, New York, pp. 433--444.]]"},{"key":"e_1_2_1_68_1","volume-title":"Advances in Cryptology---EUROCRYPT '99","volume":"1592","author":"Richardson R.","unstructured":"Richardson , R. , and Kilian , J . 1999. On the concurrent composition of zero-knowledge proofs . In Advances in Cryptology---EUROCRYPT '99 . Lecture Notes in Computer Science , vol. 1592 . Springer-Verlag, New York, pp. 415--431.]] Richardson, R., and Kilian, J. 1999. On the concurrent composition of zero-knowledge proofs. In Advances in Cryptology---EUROCRYPT '99. Lecture Notes in Computer Science, vol. 1592. Springer-Verlag, New York, pp. 415--431.]]"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359342"},{"key":"e_1_2_1_70_1","unstructured":"Rivest R. L. Shamir A. and Wagner D. A. 1996. Time-puzzles and time-release crypto. manuscript (Available: http:\/\/theory.lcs.mit.edu\/ rivest\/RivestShamirWagner-timelock.ps.)]]   Rivest R. L. Shamir A. and Wagner D. A. 1996. Time-puzzles and time-release crypto. manuscript (Available: http:\/\/theory.lcs.mit.edu\/ rivest\/RivestShamirWagner-timelock.ps.)]]"},{"key":"e_1_2_1_71_1","series-title":"Lecture Notes in Computer Science","first-page":"451","volume-title":"Advances in Cryptology---CRYPTO'2000","author":"Rosen A.","unstructured":"Rosen , A. 2000. A note on the round-complexity of concurrent zero-knowledge . In Advances in Cryptology---CRYPTO'2000 . Lecture Notes in Computer Science , vol. 1880 . Springer-Verlag , New York , pp. 451 -- 468 .]] Rosen, A. 2000. A note on the round-complexity of concurrent zero-knowledge. In Advances in Cryptology---CRYPTO'2000. Lecture Notes in Computer Science, vol. 1880. Springer-Verlag, New York, pp. 451--468.]]"},{"key":"e_1_2_1_72_1","first-page":"543","volume-title":"Proceedings of the 40th ACM Symposium on Theory of Computing. ACM","author":"Sahai A.","year":"1999","unstructured":"Sahai , A. 1999 . Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security . In Proceedings of the 40th ACM Symposium on Theory of Computing. ACM , New York , pp. 543 -- 553 .]] Sahai, A. 1999. Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In Proceedings of the 40th ACM Symposium on Theory of Computing. ACM, New York, pp. 543--553.]]"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1039488.1039489","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1039488.1039489","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:31:44Z","timestamp":1750264304000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1039488.1039489"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,11]]},"references-count":70,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2004,11]]}},"alternative-id":["10.1145\/1039488.1039489"],"URL":"https:\/\/doi.org\/10.1145\/1039488.1039489","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,11]]},"assertion":[{"value":"2004-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}