{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,27]],"date-time":"2026-10-27T18:06:28Z","timestamp":1793124388681,"version":"4.5.0"},"reference-count":62,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2003,1]]},"abstract":"<jats:p>A new public-key encryption scheme, along with several variants, is proposed and analyzed. The scheme and its variants are quite practical and are proved secure against adaptive chosen ciphertext attack under standard intractability assumptions. These appear to be the first public-key encryption schemes in the literature that are simultaneously practical and provably secure.<\/jats:p>","DOI":"10.1137\/s0097539702403773","type":"journal-article","created":{"date-parts":[[2004,1,6]],"date-time":"2004-01-06T21:00:50Z","timestamp":1073422850000},"page":"167-226","source":"Crossref","is-referenced-by-count":676,"title":["Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack"],"prefix":"10.1137","volume":"33","author":[{"given":"Ronald","family":"Cramer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Victor","family":"Shoup","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","unstructured":"M. Abdalla, M. Bellare, and P. Rogaway,\n                      DHAES: An Encryption Scheme Based on the Diffie\u2010Hellman Problem\n                      , Cryptology ePrint Archive, Report 1999\/007, http:\/\/eprint.iacr.org (1999)."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Michel Abdalla, Mihir Bellare, Phillip Rogaway, The oracle Diffie\u2010Hellman assumptions and an analysis of DHIES, Lecture Notes in Comput. Sci., Vol. 2020, Springer, Berlin, 2001, 143\u20131581907095","DOI":"10.1007\/3-540-45353-9_12"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1109\/49.839935"},{"key":"R4","volume-title":"Algorithmic number theory. Vol. 1","author":"Bach Eric","year":"1996"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1962-0148632-7"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Paul Bateman, Roger Horn, Primes represented by irreducible polynomials in one variable, Amer. Math. Soc., Providence, R.I., 1965, 119\u201313231:1234","DOI":"10.1090\/pspum\/008\/0176966"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"M. Bellare, A. Boldyreva, and S. Micali,\n                      Public\u2010key encryption in a multi\u2010user setting: Security proofs and improvements\n                      , in Advances in Cryptology\u2014Eurocrypt 2000, Lecture Notes in Comput. Sci. 1807, B. Preneel, ed., Springer\u2010Verlag, Heidelberg, 2000, pp. 259\u2013274.","DOI":"10.1007\/3-540-45539-6_18"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway,\n                      Relations among notions of security for public\u2010key encryption schemes\n                      , in Advances in Cryptology\u2014Crypto \u201998, Lecture Notes in Comput. Sci. 1462, H. Krawczyk, ed., Springer\u2010Verlag, Heidelberg, 1998, pp. 26\u201345.","DOI":"10.1007\/BFb0055718"},{"key":"R9","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 First ACM Conference on Computer and Communications Security, Fairfax, VA, 1993, pp. 62\u201373.","DOI":"10.1145\/168588.168596"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"M. Bellare and P. Rogaway,\n                      Optimal asymmetric encryption\n                      , in Advances in Cryptology\u2014Eurocrypt \u201994, Lecture Notes in Comput. Sci. 950, A. De Santis, ed., Springer\u2010Verlag, Heidelberg, 1994, pp. 92\u2013111.","DOI":"10.1007\/BFb0053428"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"M. Bellare and P. Rogaway,\n                      Collision\u2010resistant hashing: Towards making UOWHFs practical\n                      , in Advances in Cryptology\u2014Crypto \u201997, Lecture Notes in Comput. Sci. 1294, B. S. Kaliski, Jr., ed., Springer\u2010Verlag, Heidelberg, 1997, pp. 470\u2013484.","DOI":"10.1007\/BFb0052256"},{"key":"R12","volume-title":"Elliptic curves in cryptography","author":"Blake I.","year":"2000"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"D. Bleichenbacher,\n                      Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1\n                      , in Advances in Cryptology\u2014Crypto \u201998, Lecture Notes in Comput. Sci. 1462, H. Krawczyk, ed., Springer\u2010Verlag, Heidelberg, 1998, pp. 1\u201312.","DOI":"10.1007\/BFb0055716"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Dan Boneh, The decision Diffie\u2010Hellman problem, Lecture Notes in Comput. Sci., Vol. 1423, Springer, Berlin, 1998, 48\u2013632000k:94024","DOI":"10.1007\/BFb0054851"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Dan Boneh, Simplified OAEP for the RSA and Rabin functions, Lecture Notes in Comput. Sci., Vol. 2139, Springer, Berlin, 2001, 275\u20132912003h:94021","DOI":"10.1007\/3-540-44647-8_17"},{"key":"R16","unstructured":"S. Brands,\n                      An Efficient Off\u2010Line Electronic Cash System Based on the Representation Problem\n                      , CWI Technical report CS\u2010R9323, Centre for Mathematics and Computer Science, Amsterdam, 1993."},{"key":"R17","doi-asserted-by":"crossref","unstructured":"E. F. Brickell, D. M. Gordon, K. S. McCurley, and D. B. Wilson,\n                      Fast exponentiation with precomputation\n                      , in Advances in Cryptology\u2014Eurocrypt \u201992, Lecture Notes in Comput. Sci. 658, R. A. Rueppel, ed., Springer\u2010Verlag, Heidelberg, 1993, pp. 200\u2013207.","DOI":"10.1007\/3-540-47555-9_18"},{"key":"R18","unstructured":"R. Canetti,\n                      Universally Composable Security: A New Paradigm for Cryptographic Protocols\n                      , Cryptology ePrint Archive, Report 2000\/067, http:\/\/eprint.iacr.org (2000)."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"R. Canetti, O. Goldreich, and S. Halevi,\n                      The random oracle methodology, revisited\n                      , in Proceedings of the 30th Annual ACM Symposium on Theory of Computing, Dallas, TX, 1998, pp. 209\u2013218.","DOI":"10.1145\/276698.276741"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"R. Canetti and S. Goldwasser,\n                      An efficient threshold public key cryptosystem secure against adaptive chosen ciphertext attack\n                      , in Advances in Cryptology\u2014Eurocrypt \u201999, Lecture Notes in Comput. Sci. 1592, J. Stern, ed., Springer\u2010Verlag, Heidelberg, 1999, pp. 90\u2013106.","DOI":"10.1007\/3-540-48910-X_7"},{"key":"R21","volume-title":"Introduction to algorithms","author":"Cormen Thomas","year":"2001"},{"key":"R22","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 Advances in Cryptology\u2014Crypto \u201998, Lecture Notes in Comput. Sci. 1462, H. Krawczyk, ed., Springer\u2010Verlag, Heidelberg, 1998, pp. 13\u201325.","DOI":"10.1007\/BFb0055717"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1145\/357830.357847"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"Ronald Cramer, Victor Shoup, Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public\u2010key encryption, Lecture Notes in Comput. Sci., Vol. 2332, Springer, Berlin, 2002, 45\u2013641975527","DOI":"10.1007\/3-540-46035-7_4"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"I. Damg\u00e5rd,\n                      Towards practical public key cryptosystems secure against chosen ciphertext attacks\n                      , in Advances in Cryptology\u2014Crypto \u201991, Lecture Notes in Comput. Sci. 576, J. Feigenbaum, ed., Springer\u2010Verlag, Heidelberg, 1992, pp. 445\u2013456.","DOI":"10.1007\/3-540-46766-1_36"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055638"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"D. Dolev, C. Dwork, and M. Naor,\n                      Non\u2010malleable cryptography\n                      , in Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, New Orleans, LA, 1991, pp. 542\u2013552.","DOI":"10.1145\/103418.103474"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795291562"},{"key":"R29","unstructured":"C. Dwork and M. Naor,\n                      Method for Message Authentication from Non\u2010malleable Cryptosystems\n                      , U.S. Patent No. 05539826, 1996."},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1985.1057074"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"Y. Frankel and M. Yung,\n                      Cryptanalysis of immunized LL public key systems\n                      , in Advances in Cryptology\u2014Crypto \u201995, Lecture Notes in Comput. Sci. 963, D. Coppersmith, ed., Springer\u2010Verlag, Heidelberg, 1995, pp. 287\u2013296.","DOI":"10.1007\/3-540-44750-4_23"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval, Jacques Stern, RSA\u2010OAEP is secure underthe RSA assumption, Lecture Notes in Comput. Sci., Vol. 2139, Springer, Berlin, 2001, 260\u20132742003g:94037","DOI":"10.1007\/3-540-44647-8_16"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"O. Goldreich and L. A. Levin,\n                      A hard\u2010core predicate for all one\u2010way functions\n                      , in Proceedings of the 21st Annual ACM Symposium on Theory of Computing, Seattle, WA, 1989, pp. 25\u201332.","DOI":"10.1145\/73007.73010"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, L. Levin, and M. Luby,\n                      Pseudo\u2010random number generation from any one\u2010way function\n                      , in Proceedings of the 21st Annual ACM Symposium on Theory of Computing, Seattle, WA, 1989, pp. 12\u201324.","DOI":"10.1145\/73007.73009"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and D. Zuckermann,\n                      How to recycle random bits\n                      , in Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, NC, 1989, pp. 248\u2013253.","DOI":"10.1109\/SFCS.1989.63486"},{"key":"R38","unstructured":"A. Joux and K. Nguyen,\n                      Separating Decision Diffie\u2010Hellman from Diffie\u2010Hellman in Cryptographic Groups\n                      , Cryptology ePrint Archive, Report 2001\/003, http:\/\/eprint.iacr.org (2001)."},{"key":"R39","doi-asserted-by":"crossref","unstructured":"C. H. Lim and P. J. Lee,\n                      Another method for attaining security against adaptively chosen ciphertext attacks\n                      , in Advances in Cryptology\u2014Crypto \u201993, Lecture Notes in Comput. Sci. 773, D. R. Stinson, ed., Springer\u2010Verlag, Heidelberg, 1994, pp. 420\u2013434.","DOI":"10.1007\/3-540-48329-2_36"},{"key":"R40","doi-asserted-by":"crossref","unstructured":"C. H. Lim and P. J. Lee,\n                      More flexible exponentiation with precomputation\n                      , in Advances in Cryptology\u2014Crypto \u201994, Lecture Notes in Comput. Sci. 839, Y. G. Desmedt, ed., Springer\u2010Verlag, Heidelberg, 1994, pp. 95\u2013107.","DOI":"10.1007\/3-540-48658-5_11"},{"key":"R41","doi-asserted-by":"crossref","unstructured":"J. Manger,\n                      A chosen ciphertext attack on RSA optimal asymmetric encryption padding (OAEP) as standardized in PKCS # 1 v2.0\n                      , in Advances in Cryptology\u2014Crypto 2001, Lecture Notes in Comput. Sci. 2139, J. Kilian, ed., Springer\u2010Verlag, Heidelberg, 2001, pp. 230\u2013238.","DOI":"10.1007\/3-540-44647-8_14"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"U. Maurer and S. Wolf,\n                      Diffie\u2010Hellman, decision Diffie\u2010Hellman, and discrete logarithms\n                      , in Proceedings of the IEEE International Symposium on Information Theory (ISIT \u201998), Cambridge, MA, 1998, p. 327.","DOI":"10.1109\/ISIT.1998.708932"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008302122286"},{"key":"R44","unstructured":"A. Menezes, P. van Oorschot, and S. Vanstone,\n                      Handbook of Applied Cryptography\n                      , CRC Press, Boca Raton, FL, 1997."},{"key":"R45","doi-asserted-by":"crossref","unstructured":"M. Naor and O. Reingold,\n                      Number\u2010theoretic constructions of efficient pseudo\u2010random functions\n                      , in Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Miami Beach, FL, 1997, pp. 458\u2013467.","DOI":"10.1109\/SFCS.1997.646134"},{"key":"R46","unstructured":", Proceedings of the Twenty\u2010first Annual ACM Symposium on Theory of Computing, Association for Computing Machinery (ACM), 1989, 0\u20130, viii+600, Held in Seattle, Washington, May 15\u201317, 198990c:68003"},{"key":"R47","doi-asserted-by":"crossref","unstructured":"M. Naor and M. Yung,\n                      Public\u2010key cryptosystems provably secure against chosen ciphertext attacks\n                      , in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, Baltimore, MD, 1990, pp. 427\u2013437.","DOI":"10.1145\/100216.100273"},{"key":"R48","doi-asserted-by":"crossref","unstructured":"Tatsuaki Okamoto, David Pointcheval, The gap\u2010problems: a new class of problems for the security of cryptographic schemes, Lecture Notes in Comput. Sci., Vol. 1992, Springer, Berlin, 2001, 104\u20131182003c:94041","DOI":"10.1007\/3-540-44586-2_8"},{"key":"R49","doi-asserted-by":"crossref","unstructured":"P. Paillier,\n                      Public\u2010key cryptosystems based on composite degree residuosity classes\n                      , in Advances in Cryptology\u2014Eurocrypt \u201999, Lecture Notes in Comput. Sci. 1592, J. Stern, ed., Springer\u2010Verlag, Heidelberg, 1999, pp. 223\u2013238.","DOI":"10.1007\/3-540-48910-X_16"},{"key":"R50","doi-asserted-by":"crossref","unstructured":"C. Rackoff and D. Simon,\n                      Noninteractive zero\u2010knowledge proof of knowledge and chosen ciphertext attack\n                      , in Advances in Cryptology\u2014Crypto \u201991, Lecture Notes in Comput. Sci. 576, J. Feigenbaum, ed., Springer\u2010Verlag, Heidelberg, 1992, pp. 433\u2013444.","DOI":"10.1007\/3-540-46766-1_35"},{"key":"R51","doi-asserted-by":"crossref","unstructured":"J. Rompel,\n                      One\u2010way functions are necessary and sufficient for digital signatures\n                      , in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, Baltimore, MD, 1990, pp. 387\u2013394.","DOI":"10.1145\/100216.100269"},{"key":"R52","unstructured":"Secure Hash Standard\n                      , FIPS Publication 180\u20101, National Institute of Standards and Technology (NIST), Gaithersburg, MD, 1995."},{"key":"R53","doi-asserted-by":"crossref","unstructured":"V. Shoup,\n                      Lower bounds for discrete logarithms and related problems\n                      , in Advances in Cryptology\u2014Eurocrypt \u201997, Lecture Notes in Comput. Sci. 1233, W. Fumy, ed., Springer\u2010Verlag, Heidelberg, 1997, pp. 256\u2013266.","DOI":"10.1007\/3-540-69053-0_18"},{"key":"R54","unstructured":"V. Shoup,\n                      On Formal Models for Secure Key Exchange\n                      , Cryptology ePrint Archive, Report 1999\/012, http:\/\/eprint.iacr.org (1999)."},{"key":"R55","unstructured":", Advances in cryptology\u2014EUROCRYPT 2000, Proceedings of the 19th International Annual Conference on the Theory and Application of Cryptographic Techniques held in Bruges, May 14\u201318, 2000, Lecture Notes in Computer Science, Vol. 1807, Springer\u2010Verlag, 2000, 0\u20130, xiv+6082001b:94028"},{"key":"R56","doi-asserted-by":"crossref","unstructured":"V. Shoup,\n                      Using hash functions as a hedge against chosen ciphertext attack\n                      , in Advances in Cryptology\u2014Eurocrypt 2000, Lecture Notes in Comput. Sci. 1807, B. Preneel, ed., Springer\u2010Verlag, Heidelberg, 2000, pp. 275\u2013288.","DOI":"10.1007\/3-540-45539-6_19"},{"key":"R57","doi-asserted-by":"crossref","unstructured":"Victor Shoup, OAEP reconsidered (extended abstract), Lecture Notes in Comput. Sci., Vol. 2139, Springer, Berlin, 2001, 239\u20132592003h:94048","DOI":"10.1007\/3-540-44647-8_15"},{"key":"R58","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-001-0020-9"},{"key":"R59","doi-asserted-by":"crossref","unstructured":"D. Simon,\n                      Finding collisions on a one\u2010way street: Can secure hash functions be based on general assumptions?\n                      , in Advances in Cryptology\u2014Eurocrypt \u201998, Lecture Notes in Comput. Sci. 1403, G. Goos and K. Nyberg, eds., Springer\u2010Verlag, Heidelberg, 1998, pp. 334\u2013345.","DOI":"10.1007\/BFb0054137"},{"key":"R60","doi-asserted-by":"publisher","DOI":"10.1007\/s001459900052"},{"key":"R61","doi-asserted-by":"crossref","unstructured":"M. Stadler,\n                      Publicly verifiable secret sharing\n                      , in Advances in Cryptology\u2014Eurocrypt \u201996, Lecture Notes in Comput. Sci. 1070, U. Maurer, ed., Springer\u2010Verlag, Heidelberg, 1996, pp. 190\u2013199.","DOI":"10.1007\/3-540-68339-9_17"},{"key":"R62","doi-asserted-by":"crossref","unstructured":"Y. Zheng and J. Seberry,\n                      Practical approaches to attaining security against adaptively chosen ciphertext attacks\n                      , in Advances in Cryptology\u2014Crypto \u201992, Lecture Notes in Comput. Sci. 740, E. F. Brickell, ed., Springer\u2010Verlag, Heidelberg, 1993, pp. 292\u2013304.","DOI":"10.1007\/3-540-48071-4_20"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539702403773","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:20:12Z","timestamp":1787336412000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539702403773"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,1]]},"references-count":62,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,1]]}},"alternative-id":["10.1137\/S0097539702403773"],"URL":"https:\/\/doi.org\/10.1137\/s0097539702403773","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,1]]}}}