{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T01:42:56Z","timestamp":1791078176153,"version":"4.1.0"},"reference-count":66,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>We propose a general cryptographic primitive called lossy trapdoor functions (lossy TDFs), and we use it to develop new approaches for constructing several important cryptographic tools, including (injective) trapdoor functions, collision-resistant hash functions, oblivious transfer, and chosen ciphertext-secure cryptosystems (in the standard model). All of these constructions are simple, efficient, and black-box. We realize lossy TDFs based on a variety of cryptographic assumptions, including the hardness of the decisional Diffie\u2013Hellman (DDH) problem and the hardness of the \u201clearning with errors\u201d problem (which is implied by the worst-case hardness of various lattice problems). Taken together, our results resolve some long-standing open problems in cryptography. They give the first injective TDFs based on problems not directly related to integer factorization and provide the first chosen ciphertext-secure cryptosystem based solely on worst-case complexity assumptions.<\/jats:p>","DOI":"10.1137\/080733954","type":"journal-article","created":{"date-parts":[[2011,12,22]],"date-time":"2011-12-22T10:05:42Z","timestamp":1324548342000},"page":"1803-1844","source":"Crossref","is-referenced-by-count":104,"title":["Lossy Trapdoor Functions and Their Applications"],"prefix":"10.1137","volume":"40","author":[{"given":"Chris","family":"Peikert","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Brent","family":"Waters","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,12,22]]},"reference":[{"key":"R1","first-page":"1","volume":"13","author":"Ajtai M.","year":"2004","journal-title":"Quad. Mat."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"M. Ajtai and C. Dwork,\n                      A public-key cryptosystem with worst-case\/average-case equivalence\n                      , in Proceedings of ACM STOC, 1997, pp. 284\u2013293.","DOI":"10.1145\/258533.258604"},{"key":"R3","unstructured":"M. Ajtai and C. Dwork,\n                      The first and fourth public-key cryptosystems with worst-case\/average-case equivalence\n                      , Electronic Colloquium on Computational Complexity (ECCC), 14, 2007."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"M. Ajtai, R. Kumar, and D. Sivakumar,\n                      A sieve algorithm for the shortest lattice vector problem\n                      , in Proceedings of ACM STOC, 2001, pp. 601\u2013610.","DOI":"10.1145\/380752.380857"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.907471"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Halevi, A. Sahai, and S. P. Vadhan,\n                      Many-to-one trapdoor functions and their relation to public-key cryptosystems.\n                      , in Proceedings of CRYPTO, 1998, pp. 283\u2013298.","DOI":"10.1007\/BFb0055735"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"M. Bellare, D. Hofheinz, and S. Yilek,\n                      Possibility and impossibility results for encryption and commitment secure under selective opening\n                      , in Proceedings of EUROCRYPT, 2009, pp. 1\u201335.","DOI":"10.1007\/978-3-642-01001-9_1"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"M. Bellare and P. Rogaway,\n                      Random oracles are practical: A paradigm for designing efficient protocols.\n                      , in Proceedings of the ACM Conference on Computer and Communications Security, 1993, pp. 62\u201373.","DOI":"10.1145\/168588.168596"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792543"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/0220068"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0213053"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"A. Boldyreva, S. Fehr, and A. O'Neill,\n                      On notions of security for deterministic encryption, and efficient constructions without random oracles\n                      , in Proceedings of CRYPTO, 2008, pp. 335\u2013359.","DOI":"10.1007\/978-3-540-85174-5_19"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"D. Boneh,\n                      The decision Diffie-Hellman problem\n                      , in Proceedings of ANTS, 1998, pp. 48\u201363.","DOI":"10.1007\/BFb0054851"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970544713X"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"D. Boneh and J. Katz,\n                      Improved efficiency for CCA-secure cryptosystems built using identity-based encryption\n                      , in Proceedings of CT-RSA, 2005, pp. 87\u2013103.","DOI":"10.1007\/978-3-540-30574-3_8"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"X. Boyen, Q. Mei, and B. Waters,\n                      Direct chosen ciphertext security from identity-based techniques\n                      , in Proceedings of the ACM Conference on Computer and Communications Security, 2005, pp. 320\u2013329.","DOI":"10.1145\/1102120.1102162"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"R. Canetti, S. Halevi, and J. Katz,\n                      Chosen-ciphertext security from identity-based encryption\n                      , in Proceedings of EUROCRYPT, 2004, pp. 207\u2013222.","DOI":"10.1007\/978-3-540-24676-3_13"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"R. Cramer and I. Damg\u00e5rd,\n                      On the amortized complexity of zero-knowledge protocols\n                      , in Proceedings of CRYPTO, 2009, pp. 177\u2013191.","DOI":"10.1007\/978-3-642-03356-8_11"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"R. Cramer and V. Shoup,\n                      A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack\n                      , in Proceedings of CRYPTO, 1998, pp. 13\u201325.","DOI":"10.1007\/BFb0055717"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"R. Cramer and V. Shoup,\n                      Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption\n                      , in Proceedings of EUROCRYPT, 2002, pp. 45\u201364.","DOI":"10.1007\/3-540-46035-7_4"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403773"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055638"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/060651380"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795291562"},{"key":"R25","unstructured":"E. Elkind and A. Sahai,\n                      A Unified Methodology for Constructing Public-key Encryption Schemes Secure against Adaptive Chosen-ciphertext Attack\n                      , Cryptology ePrint Archive, Report 2002\/042, http:\/\/eprint.iacr.org\/."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1145\/3812.3818"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792230010"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"D. M. Freeman, O. Goldreich, E. Kiltz, A. Rosen, and G. Segev,\n                      More constructions of lossy and correlation-secure trapdoor functions\n                      , in Proceedings of the 13th International Conference on Practice and Theory in Public Key Cryptography, 2010.","DOI":"10.1007\/978-3-642-13013-7_17"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"E. Fujisaki and T. Okamoto,\n                      Secure integration of asymmetric and symmetric encryption schemes\n                      , in Proceedings of CRYPTO, 1999, pp. 537\u2013554.","DOI":"10.1007\/3-540-48405-1_34"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"C. Gentry, C. Peikert, and V. Vaikuntanathan,\n                      Trapdoors for hard lattices and new cryptographic constructions\n                      , in Proceedings of ACM STOC, 2008, pp. 197\u2013206.","DOI":"10.1145\/1374376.1374407"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"Y. Gertner, T. Malkin, and S. Myers,\n                      Towards a separation of semantic and CCA security for public key encryption\n                      , in Proceedings of TCC, 2007, pp. 434\u2013455.","DOI":"10.1007\/978-3-540-70936-7_24"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"Y. Gertner, T. Malkin, and O. Reingold,\n                      On the impossibility of basing trapdoor functions on trapdoor predicates\n                      , in Proceedings of FOCS, 2001, pp. 126\u2013135.","DOI":"10.1109\/SFCS.2001.959887"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"O. Goldreich,\n                      Foundations of Cryptography\n                      , Vol. II, Cambridge University Press, London, 2004.","DOI":"10.1017\/CBO9780511721656"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"O. Goldreich and L. A. Levin,\n                      A hard-core predicate for all one-way functions\n                      , in Proceedings of ACM STOC, 1989, pp. 25\u201332.","DOI":"10.1145\/73007.73010"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Micali, and A. Wigderson,\n                      How to play any mental game or a completeness theorem for protocols with honest majority\n                      , in Proceedings of ACM STOC, 1987, pp. 218\u2013229.","DOI":"10.1145\/28395.28420"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"I. Haitner,\n                      Semi-honest to malicious oblivious transfer\u2014the black-box way\n                      , in Proceedings of TCC, 2008, pp. 412\u2013426.","DOI":"10.1007\/978-3-540-78524-8_23"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"R40","doi-asserted-by":"crossref","unstructured":"D. Hofheinz and E. Kiltz,\n                      Secure hybrid encryption from weakened key encapsulation\n                      , in Proceedings of CRYPTO, 2007, pp. 553\u2013571.","DOI":"10.1007\/978-3-540-74143-5_31"},{"key":"R41","doi-asserted-by":"crossref","unstructured":"C.Y. Hsiao and L. Reyzin,\n                      Finding collisions on a public road, or do secure hash functions need secret coins?\n                      , in Proceedings of CRYPTO, 2004, pp. 92\u2013105.","DOI":"10.1007\/978-3-540-28628-8_6"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"Q. Huang, D. S. Wong, and Y. Zhao,\n                      Generic transformation to strongly unforgeable signatures\n                      , in Proceedings of ACNS, 2007, pp. 1\u201317.","DOI":"10.1007\/978-3-540-72738-5_1"},{"key":"R43","doi-asserted-by":"crossref","unstructured":"G. Kol and M. Naor,\n                      Cryptography and game theory: Designing protocols for exchanging information\n                      , in Proceedings of TCC, 2008, pp. 320\u2013339.","DOI":"10.1007\/978-3-540-78524-8_18"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"R45","doi-asserted-by":"crossref","unstructured":"P. Mol and S. Yilek,\n                      Chosen-ciphertext security from slightly lossy trapdoor functions\n                      , in Proceedings of the 13th International Conference on Practice and Theory in Public Key Cryptography, 2010.","DOI":"10.1007\/978-3-642-13013-7_18"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1618"},{"key":"R47","doi-asserted-by":"crossref","unstructured":"M. Naor and M. Yung,\n                      Universal one-way hash functions and their cryptographic applications\n                      , in Proceedings of ACM STOC, 1989, pp. 33\u201343.","DOI":"10.1145\/73007.73011"},{"key":"R48","doi-asserted-by":"crossref","unstructured":"M. Naor and M. Yung,\n                      Public-key cryptosystems provably secure against chosen ciphertext attacks\n                      , in Proceedings of ACM STOC, 1990, pp. 427\u2013437.","DOI":"10.1145\/100216.100273"},{"key":"R49","doi-asserted-by":"crossref","unstructured":"P. Paillier,\n                      Public-key cryptosystems based on composite degree residuosity classes\n                      , in Proceedings of EUROCRYPT, 1999, pp. 223\u2013238.","DOI":"10.1007\/3-540-48910-X_16"},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0251-3"},{"key":"R51","doi-asserted-by":"crossref","unstructured":"C. Peikert,\n                      Public-key cryptosystems from the worst-case shortest vector problem\n                      , in Proceedings of ACM STOC, 2009, pp. 333\u2013342.","DOI":"10.1145\/1536414.1536461"},{"key":"R52","doi-asserted-by":"crossref","unstructured":"C. Peikert and V. Vaikuntanathan,\n                      Noninteractive statistical zero-knowledge proofs for lattice problems\n                      , in Proceedings of CRYPTO, 2008, pp. 536\u2013553.","DOI":"10.1007\/978-3-540-85174-5_30"},{"key":"R53","doi-asserted-by":"crossref","unstructured":"C. Peikert, V. Vaikuntanathan, and B. Waters,\n                      A framework for efficient and composable oblivious transfer\n                      , in Proceedings of CRYPTO, 2008, pp. 554\u2013571.","DOI":"10.1007\/978-3-540-85174-5_31"},{"key":"R54","unstructured":"C. Peikert and B. Waters,\n                      Lossy trapdoor functions and their applications\n                      , SIAM J. Comput., to appear."},{"key":"R55","unstructured":"M. O. Rabin,\n                      Digitalized Signatures and Public-key Functions as Intractable as Factorization\n                      , Technical report, Massachusetts Institute of Technology, Cambridge, MA, 1979."},{"key":"R56","doi-asserted-by":"crossref","unstructured":"C. Rackoff and D. R. Simon,\n                      Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack\n                      , in Proceedings of CRYPTO, 1991, pp. 433\u2013444.","DOI":"10.1007\/3-540-46766-1_35"},{"key":"R57","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039490"},{"key":"R58","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568324"},{"key":"R59","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359342"},{"key":"R60","doi-asserted-by":"crossref","unstructured":"A. Rosen and G. Segev,\n                      Chosen-ciphertext security via correlated products\n                      , in Proceedings of TCC, 2009, pp. 419\u2013436.","DOI":"10.1007\/978-3-642-00457-5_25"},{"key":"R61","doi-asserted-by":"crossref","unstructured":"A. Sahai,\n                      Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security\n                      , in FOCS, 1999, pp. 543\u2013553.","DOI":"10.1109\/SFFCS.1999.814628"},{"key":"R62","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90064-8"},{"key":"R63","unstructured":"H. Shacham,\n                      A Cramer-Shoup Encryption Scheme from the Linear Assumption and from Progressively Weaker Linear Variants\n                      , Cryptology ePrint Archive, Report 2007\/074, http:\/\/eprint.iacr.org\/."},{"key":"R64","doi-asserted-by":"crossref","unstructured":"A. Shamir,\n                      Identity-based cryptosystems and signature schemes\n                      , in Proceedings of CRYPTO, 1984, pp. 47\u201353.","DOI":"10.1007\/3-540-39568-7_5"},{"key":"R65","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90033-7"},{"key":"R66","doi-asserted-by":"crossref","unstructured":"A. C.C. Yao,\n                      Theory and applications of trapdoor functions (extended abstract)\n                      , in Proceedings of FOCS, 1982, pp. 80\u201391.","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080733954","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:17Z","timestamp":1787337197000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080733954"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":66,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/080733954"],"URL":"https:\/\/doi.org\/10.1137\/080733954","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}