{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T19:34:07Z","timestamp":1767987247051,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":48,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642365935","type":"print"},{"value":"9783642365942","type":"electronic"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-36594-2_19","type":"book-chapter","created":{"date-parts":[[2013,2,7]],"date-time":"2013-02-07T02:43:27Z","timestamp":1360205007000},"page":"334-354","source":"Crossref","is-referenced-by-count":30,"title":["Unprovable Security of Perfect NIZK and Non-interactive Non-malleable Commitments"],"prefix":"10.1007","author":[{"given":"Rafael","family":"Pass","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"19_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/978-3-540-70936-7_7","volume-title":"Theory of Cryptography","author":"M. Abe","year":"2007","unstructured":"Abe, M., Fehr, S.: Perfect NIZK with Adaptive Soundness. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol.\u00a04392, pp. 118\u2013136. Springer, Heidelberg (2007)"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Akavia, A., Goldreich, O., Goldwasser, S., Moshkovitz, D.: On basing one-way functions on NP-hardness. In: STOC 2006, pp. 701\u2013710 (2006)","DOI":"10.1145\/1132516.1132614"},{"key":"19_CR3","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1109\/SFCS.2002.1181957","volume-title":"FOCS 2002: Proceedings of the 43rd Symposium on Foundations of Computer Science","author":"B. Barak","year":"2002","unstructured":"Barak, B.: Constant-round coin-tossing with a man in the middle or realizing the shared random string model. In: FOCS 2002: Proceedings of the 43rd Symposium on Foundations of Computer Science, pp. 345\u2013355. IEEE Computer Society, Washington, DC (2002)"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications (extended abstract). In: STOC, pp. 103\u2013112 (1988)","DOI":"10.1145\/62212.62222"},{"key":"19_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/978-3-540-79263-5_5","volume-title":"Topics in Cryptology \u2013 CT-RSA 2008","author":"E. Bresson","year":"2008","unstructured":"Bresson, E., Monnerat, J., Vergnaud, D.: Separation Results on the \u201cOne-More\u201d Computational Problems. In: Malkin, T. (ed.) CT-RSA 2008. LNCS, vol.\u00a04964, pp. 71\u201387. Springer, Heidelberg (2008)"},{"issue":"3","key":"19_CR6","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/s00145-002-0120-1","volume":"16","author":"M. Bellare","year":"2003","unstructured":"Bellare, M., Namprempre, C., Pointcheval, D., Semanko, M.: The one-more-rsa-inversion problems and the security of chaum\u2019s blind signature scheme. J. Cryptology\u00a016(3), 185\u2013215 (2003)","journal-title":"J. Cryptology"},{"key":"19_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/3-540-45708-9_11","volume-title":"Advances in Cryptology - CRYPTO 2002","author":"M. Bellare","year":"2002","unstructured":"Bellare, M., Palacio, A.: GQ and Schnorr Identification Schemes: Proofs of Security against Impersonation under Active and Concurrent Attacks. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol.\u00a02442, pp. 162\u2013177. Springer, Heidelberg (2002)"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: ACM Conference on Computer and Communications Security, pp. 62\u201373 (1993)","DOI":"10.1145\/168588.168596"},{"issue":"6","key":"19_CR9","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1109\/TIT.1983.1056754","volume":"29","author":"G. Brassard","year":"1983","unstructured":"Brassard, G.: Relativized cryptography. IEEE Transactions on Information Theory\u00a029(6), 877\u2013893 (1983)","journal-title":"IEEE Transactions on Information Theory"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Trevisan, L.: On worst-case to average-case reductions for np problems. In: FOCS, pp. 308\u2013317 (2003)","DOI":"10.1109\/SFCS.2003.1238205"},{"key":"19_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BFb0054117","volume-title":"Advances in Cryptology - EUROCRYPT \u201998","author":"D. Boneh","year":"1998","unstructured":"Boneh, D., Venkatesan, R.: Breaking RSA May Not Be Equivalent to Factoring. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol.\u00a01403, pp. 59\u201371. Springer, Heidelberg (1998)"},{"issue":"3","key":"19_CR12","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s001459900009","volume":"9","author":"M. Bellare","year":"1996","unstructured":"Bellare, M., Yung, M.: Certifying permutations: Noninteractive zero-knowledge based on any trapdoor permutation. J. Cryptology\u00a09(3), 149\u2013166 (1996)","journal-title":"J. Cryptology"},{"issue":"4","key":"19_CR13","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1145\/1008731.1008734","volume":"51","author":"R. Canetti","year":"2004","unstructured":"Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. J. ACM\u00a051(4), 557\u2013594 (2004)","journal-title":"J. ACM"},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"Di Crescenzo, G., Ishai, Y., Ostrovsky, R.: Non-interactive and non-malleable commitment. In: STOC, pp. 141\u2013150 (1998)","DOI":"10.1145\/276698.276722"},{"key":"19_CR15","unstructured":"Chung, K.-M., Lui, E., Mahmoody, M., Pass, R.: Unprovable security of two-message zero-knowledge (2012)"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"Chung, K.-M., Lin, H., Mahmoody, M., Pass, R.: On the power of non-uniform proof of security. In: ITCS 2013 (2013)","DOI":"10.1145\/2422436.2422480"},{"key":"19_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1007\/3-540-46766-1_36","volume-title":"Advances in Cryptology - CRYPTO \u201991","author":"I.B. Damg\u00e5rd","year":"1992","unstructured":"Damg\u00e5rd, I.B.: Towards Practical Public Key Systems Secure against Chosen Ciphertext Attacks. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol.\u00a0576, pp. 445\u2013456. Springer, Heidelberg (1992)"},{"issue":"2","key":"19_CR18","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1137\/S0097539795291562","volume":"30","author":"D. Dolev","year":"2000","unstructured":"Dolev, D., Dwork, C., Naor, M.: Nonmalleable cryptography. SIAM Journal on Computing\u00a030(2), 391\u2013437 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"19_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/11535218_27","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"Y. Dodis","year":"2005","unstructured":"Dodis, Y., Oliveira, R., Pietrzak, K.: On the Generic Insecurity of the Full Domain Hash. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol.\u00a03621, pp. 449\u2013466. Springer, Heidelberg (2005)"},{"issue":"5","key":"19_CR20","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1137\/0222061","volume":"22","author":"J. Feigenbaum","year":"1993","unstructured":"Feigenbaum, J., Fortnow, L.: Random-self-reducibility of complete sets. SIAM Journal on Computing\u00a022(5), 994\u20131005 (1993)","journal-title":"SIAM Journal on Computing"},{"key":"19_CR21","unstructured":"Feige, U., Lapidot, D., Shamir, A.: Multiple non-interactive zero knowledge proofs based on a single random string. In: FOCS 1990, pp. 308\u2013317 (1990)"},{"key":"19_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/3-540-47721-7_12","volume-title":"Advances in Cryptology - CRYPTO \u201986","author":"A. Fiat","year":"1987","unstructured":"Fiat, A., Shamir, A.: How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol.\u00a0263, pp. 186\u2013194. Springer, Heidelberg (1987)"},{"key":"19_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/978-3-642-13190-5_10","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"M. Fischlin","year":"2010","unstructured":"Fischlin, M., Schr\u00f6der, D.: On the Impossibility of Three-Move Blind Signature Schemes. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol.\u00a06110, pp. 197\u2013215. Springer, Heidelberg (2010)"},{"key":"19_CR24","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kalai, Y.T.: On the (in)security of the fiat-shamir paradigm. In: FOCS 2003, pp. 102\u2013111 (2003)","DOI":"10.1109\/SFCS.2003.1238185"},{"key":"19_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/11761679_21","volume-title":"Advances in Cryptology - EUROCRYPT 2006","author":"J. Groth","year":"2006","unstructured":"Groth, J., Ostrovsky, R., Sahai, A.: Perfect Non-interactive Zero Knowledge for NP. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol.\u00a04004, pp. 339\u2013358. Springer, Heidelberg (2006)"},{"key":"19_CR26","doi-asserted-by":"crossref","unstructured":"Goyal, V.: Constant round non-malleable protocols using one way functions. In: STOC, pp. 695\u2013704 (2011)","DOI":"10.1145\/1993636.1993729"},{"key":"19_CR27","doi-asserted-by":"crossref","unstructured":"Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: STOC, pp. 99\u2013108 (2011)","DOI":"10.1145\/1993636.1993651"},{"key":"19_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/978-3-642-00457-5_13","volume-title":"Theory of Cryptography","author":"I. Haitner","year":"2009","unstructured":"Haitner, I., Holenstein, T.: On the (Im)Possibility of Key Dependent Encryption. In: Reingold, O. (ed.) TCC 2009. LNCS, vol.\u00a05444, pp. 202\u2013219. Springer, Heidelberg (2009)"},{"key":"19_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/978-3-642-00457-5_14","volume-title":"Theory of Cryptography","author":"I. Haitner","year":"2009","unstructured":"Haitner, I., Rosen, A., Shaltiel, R.: On the (Im)Possibility of Arthur-Merlin Witness Hiding Protocols. In: Reingold, O. (ed.) TCC 2009. LNCS, vol.\u00a05444, pp. 220\u2013237. Springer, Heidelberg (2009)"},{"key":"19_CR30","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R.: A personal view of average-case complexity. In: Structure in Complexity Theory 1995, pp. 134\u2013147 (1995)","DOI":"10.1109\/SCT.1995.514853"},{"key":"19_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1007\/0-387-34799-2_2","volume-title":"Advances in Cryptology - CRYPTO \u201988","author":"R. Impagliazzo","year":"1990","unstructured":"Impagliazzo, R., Rudich, S.: Limits on the Provable Consequences of One-Way Permutations. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol.\u00a0403, pp. 8\u201326. Springer, Heidelberg (1990)"},{"key":"19_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/3-540-45682-1_23","volume-title":"Advances in Cryptology - ASIACRYPT 2001","author":"M. Liskov","year":"2001","unstructured":"Liskov, M., Lysyanskaya, A., Micali, S., Reyzin, L., Smith, A.: Mutually Independent Commitments. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol.\u00a02248, pp. 385\u2013401. Springer, Heidelberg (2001)"},{"key":"19_CR33","doi-asserted-by":"crossref","unstructured":"Lin, H., Pass, R.: Non-malleability amplification. In: STOC 2009, pp. 189\u2013198 (2009)","DOI":"10.1145\/1536414.1536442"},{"key":"19_CR34","doi-asserted-by":"crossref","unstructured":"Lin, H., Pass, R.: Constant-round non-malleable commitments from any one-way function. In: STOC, pp. 705\u2013714 (2011)","DOI":"10.1145\/1993636.1993730"},{"key":"19_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1007\/978-3-540-78524-8_31","volume-title":"Theory of Cryptography","author":"H. Lin","year":"2008","unstructured":"Lin, H., Pass, R., Venkitasubramaniam, M.: Concurrent Non-malleable Commitments from Any One-Way Function. In: Canetti, R. (ed.) TCC 2008. LNCS, vol.\u00a04948, pp. 571\u2013588. Springer, Heidelberg (2008)"},{"key":"19_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/978-3-540-45146-4_6","volume-title":"Advances in Cryptology - CRYPTO 2003","author":"M. Naor","year":"2003","unstructured":"Naor, M.: On Cryptographic Assumptions and Challenges. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol.\u00a02729, pp. 96\u2013109. Springer, Heidelberg (2003)"},{"key":"19_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/978-3-540-45146-4_19","volume-title":"Advances in Cryptology - CRYPTO 2003","author":"R. Pass","year":"2003","unstructured":"Pass, R.: On Deniability in the Common Reference String and Random Oracle Model. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol.\u00a02729, pp. 316\u2013337. Springer, Heidelberg (2003)"},{"key":"19_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/3-540-39200-9_10","volume-title":"Advances in Cryptology \u2013 EUROCRPYT 2003","author":"R. Pass","year":"2003","unstructured":"Pass, R.: Simulation in Quasi-Polynomial Time, and its Application to Protocol Composition. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol.\u00a02656, pp. 160\u2013176. Springer, Heidelberg (2003)"},{"key":"19_CR39","doi-asserted-by":"crossref","unstructured":"Pass, R.: Parallel repetition of zero-knowledge proofs and the possibility of basing cryptography on np-hardness. In: IEEE Conference on Computational Complexity, pp. 96\u2013110 (2006)","DOI":"10.1109\/CCC.2006.33"},{"key":"19_CR40","doi-asserted-by":"crossref","unstructured":"Pass, R.: Limits of provable security from standard assumptions. In: STOC, pp. 109\u2013118 (2011)","DOI":"10.1145\/1993636.1993652"},{"key":"19_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/978-3-540-85174-5_4","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"O. Pandey","year":"2008","unstructured":"Pandey, O., Pass, R., Vaikuntanathan, V.: Adaptive One-Way Functions and Applications. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol.\u00a05157, pp. 57\u201374. Springer, Heidelberg (2008)"},{"key":"19_CR42","doi-asserted-by":"crossref","unstructured":"Pass, R., Rosen, A.: Concurrent non-malleable commitments. In: FOCS 2005, pp. 563\u2013572 (2005)","DOI":"10.1109\/SFCS.2005.27"},{"key":"19_CR43","doi-asserted-by":"crossref","unstructured":"Pass, R., Rosen, A.: New and improved constructions of non-malleable cryptographic protocols. In: STOC 2005, pp. 533\u2013542 (2005)","DOI":"10.1145\/1060590.1060670"},{"key":"19_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1007\/978-3-642-19571-6_35","volume-title":"Theory of Cryptography","author":"R. Pass","year":"2011","unstructured":"Pass, R., Tseng, W.-L.D., Venkitasubramaniam, M.: Towards Non-Black-Box Lower Bounds in Cryptography. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol.\u00a06597, pp. 579\u2013596. Springer, Heidelberg (2011)"},{"key":"19_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1007\/978-3-642-13190-5_32","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"R. Pass","year":"2010","unstructured":"Pass, R., Wee, H.: Constant-Round Non-malleable Commitments from Sub-exponential One-Way Functions. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol.\u00a06110, pp. 638\u2013655. Springer, Heidelberg (2010)"},{"key":"19_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-24638-1_1","volume-title":"Theory of Cryptography","author":"O. Reingold","year":"2004","unstructured":"Reingold, O., Trevisan, L., Vadhan, S.P.: Notions of Reducibility between Cryptographic Primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol.\u00a02951, pp. 1\u201320. Springer, Heidelberg (2004)"},{"issue":"2","key":"19_CR47","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/s00037-010-0291-3","volume":"19","author":"G.N. Rothblum","year":"2010","unstructured":"Rothblum, G.N., Vadhan, S.P.: Are pcps inherent in efficient arguments? Computational Complexity\u00a019(2), 265\u2013304 (2010)","journal-title":"Computational Complexity"},{"key":"19_CR48","doi-asserted-by":"crossref","unstructured":"Wee, H.: Black-box, round-efficient secure computation via non-malleability amplification. In: FOCS 2010, pp. 531\u2013540 (2010)","DOI":"10.1109\/FOCS.2010.87"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36594-2_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T20:11:22Z","timestamp":1745957482000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36594-2_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642365935","9783642365942"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36594-2_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}