{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T04:14:53Z","timestamp":1746159293382,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":48,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642542411"},{"type":"electronic","value":"9783642542428"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-642-54242-8_12","type":"book-chapter","created":{"date-parts":[[2014,2,3]],"date-time":"2014-02-03T02:42:54Z","timestamp":1391395374000},"page":"265-290","source":"Crossref","is-referenced-by-count":3,"title":["On the Impossibility of Basing Public-Coin One-Way Permutations on Trapdoor Permutations"],"prefix":"10.1007","author":[{"given":"Takahiro","family":"Matsuda","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-44647-8_1","volume-title":"Advances in Cryptology - CRYPTO 2001","author":"B. Barak","year":"2001","unstructured":"Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., Yang, K.: On the (im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol.\u00a02139, pp. 1\u201318. Springer, Heidelberg (2001)"},{"key":"12_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-01001-9_1","volume-title":"Advances in Cryptology - EUROCRYPT 2009","author":"M. Bellare","year":"2009","unstructured":"Bellare, M., Hofheinz, D., Yilek, S.: Possibility and impossibility results for encryption and commitment secure under selective opening. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol.\u00a05479, pp. 1\u201335. Springer, Heidelberg (2009)"},{"key":"12_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/BFb0053428","volume-title":"Advances in Cryptology - EUROCRYPT \u201994","author":"M. Bellare","year":"1995","unstructured":"Bellare, M., Rogaway, P.: Optimal asymmetric encryption. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol.\u00a0950, pp. 92\u2013111. Springer, Heidelberg (1995)"},{"key":"12_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/3-540-68339-9_34","volume-title":"Advances in Cryptology - EUROCRYPT \u201996","author":"M. Bellare","year":"1996","unstructured":"Bellare, M., Rogaway, P.: The exact security of digital signatures \u2013 how to sign with RSA and Rabin. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol.\u00a01070, pp. 399\u2013416. Springer, Heidelberg (1996)"},{"issue":"3","key":"12_CR5","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. of Cryptology\u00a09(3), 149\u2013166 (1996)","journal-title":"J. of Cryptology"},{"key":"12_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/978-3-642-19379-8_22","volume-title":"Public Key Cryptography \u2013 PKC 2011","author":"R. Bhattacharyya","year":"2011","unstructured":"Bhattacharyya, R., Mandal, A.: On the impossibility of instantiating PSS in the standard model. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol.\u00a06571, pp. 351\u2013368. Springer, Heidelberg (2011)"},{"issue":"4","key":"12_CR7","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Computing\u00a013(4), 850\u2013864 (1984)","journal-title":"SIAM J. Computing"},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"Boneh, D., Papakonstantinou, P.A., Rackoff, C., Vahlis, Y., Waters, B.: On the impossibility of basing identity based encryption on trapdoor permutations. In: FOCS 2008, pp. 283\u2013292 (2008)","DOI":"10.1109\/FOCS.2008.67"},{"issue":"1","key":"12_CR9","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s00145-005-0317-1","volume":"19","author":"Y.-C. Chang","year":"2006","unstructured":"Chang, Y.-C., Hsiao, C.-Y., Lu, C.-J.: The impossibility of basing one-way permutations on central cryptographic primitives. J. of Cryptology\u00a019(1), 97\u2013114 (2006)","journal-title":"J. of Cryptology"},{"key":"12_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-85174-5_1","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"J.-S. Coron","year":"2008","unstructured":"Coron, J.-S., Patarin, J., Seurin, Y.: The random oracle model and the ideal cipher model are equivalent. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol.\u00a05157, pp. 1\u201320. Springer, Heidelberg (2008)"},{"key":"12_CR11","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)"},{"key":"12_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1007\/978-3-642-28914-9_36","volume-title":"Theory of Cryptography","author":"D. Fiore","year":"2012","unstructured":"Fiore, D., Schr\u00f6der, D.: Uniqueness is a different story: Impossibility of verifiable random functions from trapdoor permutations. In: Cramer, R. (ed.) TCC 2012. LNCS, vol.\u00a07194, pp. 636\u2013653. Springer, Heidelberg (2012)"},{"key":"12_CR13","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":"12_CR14","doi-asserted-by":"crossref","unstructured":"Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: STOC 2011, pp. 99\u2013108 (2011)","DOI":"10.1145\/1993636.1993651"},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"Gertner, Y., Malkin, T., Reingold, O.: On the impossibility of basing trapdoor functions on trapdoor predicates. In: FOCS 2001, pp. 126\u2013135 (2001)","DOI":"10.1109\/SFCS.2001.959887"},{"issue":"4","key":"12_CR16","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O. Goldreich","year":"1986","unstructured":"Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM\u00a033(4), 792\u2013807 (1986)","journal-title":"J. ACM"},{"key":"12_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-642-22670-0_3","volume-title":"Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation","author":"O. Goldreich","year":"2011","unstructured":"Goldreich, O., Levin, L.A., Nisan, N.: On constructing 1-1 one-way functions. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. LNCS, vol.\u00a06650, pp. 13\u201325. Springer, Heidelberg (2011)"},{"issue":"3","key":"12_CR18","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1007\/s00145-012-9131-8","volume":"26","author":"O. Goldreich","year":"2013","unstructured":"Goldreich, O., Rothblum, R.D.: Enhancements of trapdoor permutations. J. of Cryptology\u00a026(3), 484\u2013512 (2013)","journal-title":"J. of Cryptology"},{"issue":"2","key":"12_CR19","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/0217017","volume":"17","author":"S. Goldwasser","year":"1988","unstructured":"Goldwasser, S., Micali, S., Rivest, R.: A digital signature schemes secure against adaptive chosen-message attacks. SIAM J. Computing\u00a017(2), 281\u2013308 (1988)","journal-title":"SIAM J. Computing"},{"key":"12_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/978-3-540-24638-1_22","volume-title":"Theory of Cryptography","author":"I. Haitner","year":"2004","unstructured":"Haitner, I.: Implementing oblivious transfer using collection of dense trapdoor permutations. In: Naor, M. (ed.) TCC 2004. LNCS, vol.\u00a02951, pp. 394\u2013409. Springer, Heidelberg (2004)"},{"key":"12_CR21","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)"},{"issue":"4","key":"12_CR22","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J., Impagliazzo, R., Levin, L., Luby, M.: Construction of a pseudorandom generator from any one-way function. SIAM J. Computing\u00a028(4), 1364\u20131396 (1999)","journal-title":"SIAM J. Computing"},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"Holenstein, T., K\u00fcnzler, R., Tessaro, S.: The equivalence of the random oracle model and the ideal cipher model, revisited. In: STOC 2011, pp. 89\u201398 (2011)","DOI":"10.1145\/1993636.1993650"},{"key":"12_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/978-3-540-28628-8_6","volume-title":"Advances in Cryptology \u2013 CRYPTO 2004","author":"C.-Y. Hsiao","year":"2004","unstructured":"Hsiao, C.-Y., Reyzin, L.: Finding collisions on a public road, or do secure hash functions need secret coins? In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol.\u00a03152, pp. 92\u2013105. Springer, Heidelberg (2004)"},{"key":"12_CR25","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: STOC 1989, pp. 44\u201361 (1989)","DOI":"10.1145\/73007.73012"},{"key":"12_CR26","doi-asserted-by":"crossref","unstructured":"Kahn, J., Saks, M., Smyth, C.: A dual version of Reimer\u2019s inequality and a proof of Rudich\u2019s conjecture. In: CoCo 2000, pp. 98\u2013103 (2000)","DOI":"10.1109\/CCC.2000.856739"},{"key":"12_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/978-3-642-10366-7_12","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2009","author":"J. Katz","year":"2009","unstructured":"Katz, J., Yerukhimovich, A.: On black-box constructions of predicate encryption from trapdoor permutations. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol.\u00a05912, pp. 197\u2013213. Springer, Heidelberg (2009)"},{"key":"12_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/978-3-642-13190-5_34","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"E. Kiltz","year":"2010","unstructured":"Kiltz, E., Mohassel, P., O\u2019Neill, A.: Adaptive trapdoor functions and chosen-ciphertext security. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol.\u00a06110, pp. 673\u2013692. Springer, Heidelberg (2010)"},{"key":"12_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/978-3-642-01001-9_23","volume-title":"Advances in Cryptology - EUROCRYPT 2009","author":"E. Kiltz","year":"2009","unstructured":"Kiltz, E., Pietrzak, K.: On the security of padding-based encryption schemes - or - why we cannot prove OAEP secure in the standard model. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol.\u00a05479, pp. 389\u2013406. Springer, Heidelberg (2009)"},{"key":"12_CR30","doi-asserted-by":"crossref","unstructured":"Lindell, Y., Zarosim, H.: Adaptive zero-knowledge proofs and adaptively secure oblivious transfer. In: Full version of [13] (2009), http:\/\/u.cs.biu.ac.il\/~zarosih\/papers\/adaptive-fullversion.pdf","DOI":"10.1007\/978-3-642-00457-5_12"},{"key":"12_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/978-3-642-00457-5_12","volume-title":"Theory of Cryptography","author":"Y. Lindell","year":"2009","unstructured":"Lindell, Y., Zarosim, H.: Adaptive zero-knowledge proofs and adaptively secure oblivious transfer. In: Reingold, O. (ed.) TCC 2009. LNCS, vol.\u00a05444, pp. 183\u2013201. Springer, Heidelberg (2009)"},{"issue":"2","key":"12_CR32","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1137\/0217022","volume":"17","author":"M. Luby","year":"1988","unstructured":"Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Computing\u00a017(2), 373\u2013386 (1988)","journal-title":"SIAM J. Computing"},{"key":"12_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/978-3-642-19571-6_36","volume-title":"Theory of Cryptography","author":"T. Matsuda","year":"2011","unstructured":"Matsuda, T., Matsuura, K.: On black-box separations among injective one-way functions. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol.\u00a06597, pp. 597\u2013614. Springer, Heidelberg (2011)"},{"key":"12_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-540-24638-1_2","volume-title":"Theory of Cryptography","author":"U. Maurer","year":"2004","unstructured":"Maurer, U., Renner, R., Holenstein, C.: Indifferentiability, impossibility results on reductions and applications to the random oracle methodology. In: Naor, M. (ed.) TCC 2004. LNCS, vol.\u00a02951, pp. 21\u201339. Springer, Heidelberg (2004)"},{"issue":"2","key":"12_CR35","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF00196774","volume":"4","author":"M. Naor","year":"1991","unstructured":"Naor, M.: Bit commitment using pseudorandomness. J.\u00a0of Cryptology\u00a04(2), 151\u2013158 (1991)","journal-title":"J.\u00a0of Cryptology"},{"key":"12_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":"12_CR37","doi-asserted-by":"crossref","unstructured":"Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: STOC 1989, pp. 33\u201343 (1989)","DOI":"10.1145\/73007.73011"},{"key":"12_CR38","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":"12_CR39","doi-asserted-by":"crossref","unstructured":"Pass, R.: Limits of provable security from standard assumptions. In: STOC 2011, pp. 109\u2013118 (2011)","DOI":"10.1145\/1993636.1993652"},{"key":"12_CR40","unstructured":"Rabin, M.O.: Digitalized signatures as intractable as factorization. Technical Report MIT\/LCS\/TR-212, MIT Laboratory for Computer Science (January 1979)"},{"key":"12_CR41","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.: Notions of reducibility between cryptographic primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol.\u00a02951, pp. 1\u201320. Springer, Heidelberg (2004)"},{"key":"12_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/978-3-642-00457-5_25","volume-title":"Theory of Cryptography","author":"A. Rosen","year":"2009","unstructured":"Rosen, A., Segev, G.: Chosen-ciphertext security via correlated products. In: Reingold, O. (ed.) TCC 2009. LNCS, vol.\u00a05444, pp. 419\u2013436. Springer, Heidelberg (2009)"},{"key":"12_CR43","unstructured":"Rudich, S.: Limits on the provable consequences of one-way functions, PhD thesis, University of California at Berkeley (1988)"},{"key":"12_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/978-3-642-11799-2_11","volume-title":"Theory of Cryptography","author":"Y. Vahlis","year":"2010","unstructured":"Vahlis, Y.: Two is a crowd? A black-box separation of one-wayness and security under correlated inputs. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol.\u00a05978, pp. 165\u2013182. Springer, Heidelberg (2010)"},{"key":"12_CR45","doi-asserted-by":"crossref","unstructured":"Wee, H.: On obfuscating point functions. In: STOC 2005, pp. 523\u2013532 (2005)","DOI":"10.1145\/1060590.1060669"},{"key":"12_CR46","doi-asserted-by":"crossref","unstructured":"Wichs, D.: Barriers in cryptography with weak, correlated and leaky sources. In: Proc of ITCS 2013, pp. 111\u2013126 (2013)","DOI":"10.1145\/2422436.2422451"},{"key":"12_CR47","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Theory and application of trapdoor functions. In: FOCS 1982, pp. 80\u201391 (1982)","DOI":"10.1109\/SFCS.1982.45"},{"key":"12_CR48","unstructured":"Yerukhimovich, A.: A study of separation in cryptography: New results and new models, PhD thesis, the University of Maryland (2011), http:\/\/www.cs.umd.edu\/~arkady\/thesis\/thesis.pdf"}],"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-54242-8_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T19:09:01Z","timestamp":1746126541000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-54242-8_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783642542411","9783642542428"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-54242-8_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}