{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T14:39:54Z","timestamp":1780497594333,"version":"3.54.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2007,9,22]],"date-time":"2007-09-22T00:00:00Z","timestamp":1190419200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2009,7]]},"DOI":"10.1007\/s00145-007-9012-8","type":"journal-article","created":{"date-parts":[[2007,9,21]],"date-time":"2007-09-21T19:26:01Z","timestamp":1190402761000},"page":"283-310","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Reducing Complexity Assumptions for\u00a0Statistically-Hiding Commitment"],"prefix":"10.1007","volume":"22","author":[{"given":"Iftach","family":"Haitner","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Omer","family":"Horvitz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jonathan","family":"Katz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chiu-Yuen","family":"Koo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ruggero","family":"Morselli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ronen","family":"Shaltiel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2007,9,22]]},"reference":[{"issue":"4","key":"9012_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"N. Alon, L. Babai, A. Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, J.\u00a0Algorithms 7(4), 567\u2013583 (1986)","journal-title":"J.\u00a0Algorithms"},{"issue":"1","key":"9012_CR2","first-page":"214","volume":"39","author":"M. Bellare","year":"1992","unstructured":"M. Bellare, S. Micali, How to sign given any trapdoor permutation, J.\u00a0ACM 39(1), 214\u2013233 (1992)","journal-title":"J.\u00a0ACM"},{"key":"9012_CR3","doi-asserted-by":"crossref","unstructured":"M. Bellare, R. Impagliazzo, M. Naor, Does parallel repetition lower the error in computationally sound protocols? in 38th FOCS, pp.\u00a0374\u2013383, 1997","DOI":"10.1109\/SFCS.1997.646126"},{"key":"9012_CR4","unstructured":"M. Blum, Coin flipping by telephone, in Advances in Cryptology\u2014CRYPTO\u00a0\u201981, pp.\u00a011\u201315, 1981"},{"issue":"4","key":"9012_CR5","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"M. Blum, S. Micali, How to generate cryptographically-strong sequences of pseudorandom bits, SIAM J. Comput. 13(4), 850\u2013864 (1984)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9012_CR6","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/BF00204448","volume":"2","author":"J. Boyar","year":"1990","unstructured":"J. Boyar, S. Kurtz, M. Krentel, Discrete logarithm implementation of perfect zero-knowledge blobs, J.\u00a0Cryptol. 2(2), 63\u201376 (1990)","journal-title":"J.\u00a0Cryptol."},{"issue":"2","key":"9012_CR7","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(88)90005-0","volume":"37","author":"G. Brassard","year":"1988","unstructured":"G. Brassard, D. Chaum, C. Cr\u00e9peau, Minimum disclosure proofs of knowledge, J. Comput. Syst. Sci. 37(2), 156\u2013189 (1988)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9012_CR8","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J. Carter","year":"1979","unstructured":"J. Carter, M. Wegman, Universal classes of hash functions, J.\u00a0Comput. Syst. Sci. 18(2), 143\u2013154 (1979)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"issue":"1","key":"9012_CR9","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0885-064X(89)90015-0","volume":"5","author":"B. Chor","year":"1989","unstructured":"B. Chor, O. Goldreich, On the power of two-point based sampling, J.\u00a0Complex. 5(1), 96\u2013106 (1989)","journal-title":"J.\u00a0Complex."},{"key":"9012_CR10","series-title":"LNCS","first-page":"203","volume-title":"Eurocrypt\u00a0\u201987","author":"I. Damg\u00e5rd","year":"1988","unstructured":"I. Damg\u00e5rd, Collision free hash functions and public key signature schemes, in Eurocrypt\u00a0\u201987. LNCS, vol.\u00a0304 (Springer, Berlin, 1988), pp.\u00a0203\u2013216."},{"issue":"3","key":"9012_CR11","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s001459900026","volume":"10","author":"I. Damg\u00e5rd","year":"1997","unstructured":"I. Damg\u00e5rd, M. Pedersen, B. Pfitzmann, On the existence of statistically hiding bit commitment schemes and fail-stop signatures, J.\u00a0Cryptol. 10(3), 163\u2013194 (1997)","journal-title":"J.\u00a0Cryptol."},{"key":"9012_CR12","doi-asserted-by":"crossref","unstructured":"A. De Santis, M. Yung, On the design of provably-secure cryptographic hash functions, in EUROCRYPT: Advances in Cryptology: Proceedings of EUROCRYPT, pp.\u00a0412\u2013431, 1990","DOI":"10.1007\/3-540-46877-3_37"},{"key":"9012_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-12521-2","volume-title":"Modern Cryptography, Probabilistic Proofs, and Pseudorandomness","author":"O. Goldreich","year":"1999","unstructured":"O. Goldreich, Modern Cryptography, Probabilistic Proofs, and Pseudorandomness (Springer, Berlin, 1999)"},{"key":"9012_CR14","series-title":"Foundations of Cryptography","volume-title":"Basic Tools","author":"O. Goldreich","year":"2001","unstructured":"O. Goldreich, Basic Tools. Foundations of Cryptography, vol.\u00a01 (Cambridge University Press, Cambridge, 2001)"},{"key":"9012_CR15","series-title":"Foundations of Cryptography","volume-title":"Basic Applications","author":"O. Goldreich","year":"2004","unstructured":"O. Goldreich, Basic Applications. Foundations of Cryptography, vol.\u00a02 (Cambridge University Press, Cambridge, 2004)"},{"issue":"3","key":"9012_CR16","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s001459900010","volume":"9","author":"O. Goldreich","year":"1996","unstructured":"O. Goldreich, A. Kahan, How to construct constant-round zero-knowledge proof systems for\u00a0 $\\mathcal{NP}$ , J.\u00a0Cryptol. 9(3), 167\u2013190 (1996)","journal-title":"J.\u00a0Cryptol."},{"key":"9012_CR17","doi-asserted-by":"crossref","unstructured":"O. Goldreich, L. Levin, Hard-core predicates for any one-way function, in 21st\u00a0STOC, pp.\u00a025\u201332, 1989","DOI":"10.1145\/73007.73010"},{"key":"9012_CR18","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Goldwasser, S. Micali, On the cryptographic applications of random functions, in Advances in Cryptology\u2014CRYPTO\u00a0\u201984, pp.\u00a0276\u2013288, 1985","DOI":"10.1007\/3-540-39568-7_22"},{"issue":"4","key":"9012_CR19","first-page":"792","volume":"33","author":"O. Goldreich","year":"1986","unstructured":"O. Goldreich, S. Goldwasser, S. Micali, How to construct random functions, J.\u00a0ACM 33(4), 792\u2013807 (1986)","journal-title":"J.\u00a0ACM"},{"key":"9012_CR20","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Micali, A. Widgerson, How to play any mental game\u2014a\u00a0completeness theorem for protocols with honest majority, in 19th\u00a0STOC, pp.\u00a0218\u2013229, 1987","DOI":"10.1145\/28395.28420"},{"key":"9012_CR21","unstructured":"O. Goldreich, R. Impagliazzo, L. Levin, R. Venkatesan, D. Zuckerman, Security preserving amplification of hardness, in 31st\u00a0FOCS, pp.\u00a0169\u2013178, 1990"},{"issue":"1","key":"9012_CR22","first-page":"691","volume":"38","author":"O. Goldreich","year":"1991","unstructured":"O. Goldreich, S. Micali, A. Widgerson, Proofs that yield nothing but their validity or all languages in $\\mathcal{NP}$ have zero-knowledge proof systems, J.\u00a0ACM 38(1), 691\u2013729 (1991)","journal-title":"J.\u00a0ACM"},{"issue":"6","key":"9012_CR23","doi-asserted-by":"publisher","first-page":"1163","DOI":"10.1137\/0222069","volume":"22","author":"O. Goldreich","year":"1993","unstructured":"O. Goldreich, H. Krawczyk, M. Luby, On the existence of pseudorandom generators, SIAM J. Comput. 22(6), 1163\u20131175 (1993)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9012_CR24","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/0217017","volume":"17","author":"S. Goldwasser","year":"1988","unstructured":"S. Goldwasser, S. Micali, R. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM J. Comput. 17(2), 281\u2013308 (1988)","journal-title":"SIAM J. Comput."},{"key":"9012_CR25","doi-asserted-by":"crossref","unstructured":"I. Haitner, O. Reingold, A new interactive hashing theorem, in 22nd Computational Complexity Conference, 2007. Draft of full version appears in www.wisdom.weizmann.ac.il\/iftachh\/papers\/IneractiveHashing.pdf","DOI":"10.1109\/CCC.2007.3"},{"key":"9012_CR26","doi-asserted-by":"crossref","unstructured":"I. Haitner, O. Reingold, Statistically-hiding commitment from any one-way function, in 39th\u00a0STOC, 2007","DOI":"10.1145\/1250790.1250792"},{"key":"9012_CR27","doi-asserted-by":"crossref","unstructured":"I. Haitner, O. Horvitz, J. Katz, C. Koo, R.\u00a0Morselli, R.\u00a0Shaltiel, Reducing complexity assumptions for statistically-hiding commitment, in Advances in Cryptology\u2014Eurocrypt 2005, pp.\u00a058\u201377, 2005","DOI":"10.1007\/11426639_4"},{"key":"9012_CR28","doi-asserted-by":"crossref","unstructured":"S. Halevi, S. Micali, Practical and provably-secure commitment schemes from collision-free hashing, in Advances in Cryptology\u2014CRYPTO\u00a0\u201996, pp.\u00a0201\u2013215, 1996","DOI":"10.1007\/3-540-68697-5_16"},{"issue":"4","key":"9012_CR29","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J. H\u00e5stad","year":"1999","unstructured":"J. H\u00e5stad, R. Impagliazzo, L. Levin, M. Luby, A\u00a0pseudorandom generator from any one-way function, SIAM J. Comput. 28(4), 1364\u20131396 (1999)","journal-title":"SIAM J. Comput."},{"key":"9012_CR30","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, M. Luby, One-way functions are essential for complexity-based cryptography, in 30th FOCS, pp.\u00a0230\u2013235, 1989","DOI":"10.1109\/SFCS.1989.63483"},{"key":"9012_CR31","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, S. Rudich, Limits on the provable consequences of one-way permutations, in 21st\u00a0STOC, pp.\u00a044\u201361, 1989","DOI":"10.1145\/73007.73012"},{"issue":"3","key":"9012_CR32","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s00145-002-0143-7","volume":"16","author":"Y. Lindell","year":"2003","unstructured":"Y. Lindell, Parallel coin-tossing and constant-round secure two-party computation, J.\u00a0Cryptol. 16(3), 143\u2013184 (2003)","journal-title":"J.\u00a0Cryptol."},{"issue":"2","key":"9012_CR33","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF00196774","volume":"4","author":"M. Naor","year":"1991","unstructured":"M. Naor, Bit commitment using pseudorandomness, J.\u00a0Cryptol. 4(2), 151\u2013158 (1991)","journal-title":"J.\u00a0Cryptol."},{"key":"9012_CR34","doi-asserted-by":"crossref","unstructured":"M. Naor, M. Yung, Universal one-way hash functions and their cryptographic applications, in 21st\u00a0STOC, pp.\u00a033\u201343, 1989","DOI":"10.1145\/73007.73011"},{"issue":"2","key":"9012_CR35","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s001459900037","volume":"11","author":"M. Naor","year":"1998","unstructured":"M. Naor, R. Ostrovsky, R. Venkatesan, M. Yung, Perfect zero-knowledge arguments for $\\mathcal{NP}$ using any one-way permutation, J.\u00a0Cryptol. 11(2), 87\u2013108 (1998)","journal-title":"J.\u00a0Cryptol."},{"key":"9012_CR36","unstructured":"M. Nguyen, S. Ong, S. Vadhan, Statistical zero-knowledge arguments for $\\mathcal{NP}$ from any one-way function, in 39th\u00a0FOCS, 2006"},{"key":"9012_CR37","doi-asserted-by":"crossref","unstructured":"R. Ostrovsky, R. Venkatesan, M. Yung, Secure commitment against a powerful adversary, in STACS, pp.\u00a0439\u2013448, 1992","DOI":"10.1007\/3-540-55210-3_203"},{"key":"9012_CR38","doi-asserted-by":"crossref","unstructured":"R. Ostrovsky, R. Venkatesan, M. Yung, Fair games against an all-powerful adversary, in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a013, pp.\u00a0418\u2013429, 1993","DOI":"10.1007\/978-1-4613-9323-8_31"},{"issue":"3","key":"9012_CR39","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"R. Raz, A parallel repetition theorem, SIAM J. Comput. 27(3), 763\u2013803 (1998)","journal-title":"SIAM J. Comput."},{"key":"9012_CR40","doi-asserted-by":"crossref","unstructured":"J. Rompel, One-way functions are necessary and sufficient for secure signatures, in 22nd\u00a0STOC, pp.\u00a0387\u2013394, 1990","DOI":"10.1145\/100216.100269"},{"issue":"2","key":"9012_CR41","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF00190757","volume":"8","author":"A. Russell","year":"1995","unstructured":"A. Russell, Necessary and sufficient conditions for collision-free hashing, J.\u00a0Cryptol. 8(2), 87\u2013100 (1995)","journal-title":"J.\u00a0Cryptol."},{"key":"9012_CR42","doi-asserted-by":"crossref","unstructured":"A. Yao, Theory and application of trapdoor functions, in 23rd\u00a0FOCS, pp.\u00a080\u201391, 1982","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-007-9012-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-007-9012-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-007-9012-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-007-9012-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T04:18:29Z","timestamp":1737433109000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-007-9012-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9,22]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,7]]}},"alternative-id":["9012"],"URL":"https:\/\/doi.org\/10.1007\/s00145-007-9012-8","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9,22]]},"assertion":[{"value":"2 November 2006","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 August 2007","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 September 2007","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}