{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,17]],"date-time":"2025-11-17T02:59:08Z","timestamp":1763348348292,"version":"3.41.0"},"reference-count":78,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T00:00:00Z","timestamp":1616371200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"AFOSR Award","award":["FA9550-19-1-0200"],"award-info":[{"award-number":["FA9550-19-1-0200"]}]},{"name":"AFOSR YIP Award","award":["FA9550-15-1-0274"],"award-info":[{"award-number":["FA9550-15-1-0274"]}]},{"name":"DARPA\/ARL SAFEWARE Award","award":["W911NF15C0210"],"award-info":[{"award-number":["W911NF15C0210"]}]},{"name":"NSF SaTC Award","award":["1936826"],"award-info":[{"award-number":["1936826"]}]},{"name":"NSF CRII Award","award":["1464397"],"award-info":[{"award-number":["1464397"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>We provide the first constructions of identity-based encryption and hierarchical identity-based encryption based on the hardness of the (Computational) Diffie-Hellman Problem (without use of groups with pairings) or Factoring. Our construction achieves the standard notion of identity-based encryption as considered by Boneh and Franklin [CRYPTO 2001]. We bypass known impossibility results using garbled circuits that make a non-black-box use of the underlying cryptographic primitives.<\/jats:p>","DOI":"10.1145\/3422370","type":"journal-article","created":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T16:22:02Z","timestamp":1616430122000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Identity-based Encryption from the Diffie-Hellman Assumption"],"prefix":"10.1145","volume":"68","author":[{"given":"Nico","family":"D\u00f6ttling","sequence":"first","affiliation":[{"name":"Helmholtz Center for Information Security (CISPA), Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjam","family":"Garg","sequence":"additional","affiliation":[{"name":"University of California, Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,3,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5_28"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1881412.1881420"},{"key":"e_1_2_1_4_1","unstructured":"Shweta Agrawal and Xavier Boyen. 2009. Identity-based encryption from lattices in the standard model. Manuscript. Retrieved from http:\/\/www.cs.stanford.edu\/ xb\/ab09\/.  Shweta Agrawal and Xavier Boyen. 2009. Identity-based encryption from lattices in the standard model. Manuscript. Retrieved from http:\/\/www.cs.stanford.edu\/ xb\/ab09\/."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/647086.715699"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946355"},{"volume-title":"Advances in Cryptology \u2013 EUROCRYPT\u201914 (Lecture Notes in Computer Science), Phong Q","author":"Barbulescu Razvan","key":"e_1_2_1_8_1","unstructured":"Razvan Barbulescu , Pierrick Gaudry , Antoine Joux , and Emmanuel Thom\u00e9 . 2014. A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic . In Advances in Cryptology \u2013 EUROCRYPT\u201914 (Lecture Notes in Computer Science), Phong Q . Nguyen and Elisabeth Oswald (Eds.), Vol. 8441 . Springer , Germany , 1\u201316. DOI:https:\/\/doi.org\/10.1007\/978-3-642-55220-5_1 10.1007\/978-3-642-55220-5_1 Razvan Barbulescu, Pierrick Gaudry, Antoine Joux, and Emmanuel Thom\u00e9. 2014. A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. In Advances in Cryptology \u2013 EUROCRYPT\u201914 (Lecture Notes in Computer Science), Phong Q. Nguyen and Elisabeth Oswald (Eds.), Vol. 8441. Springer, Germany, 1\u201316. DOI:https:\/\/doi.org\/10.1007\/978-3-642-55220-5_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382279"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/646754.705198"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/168588.168596"},{"volume-title":"Advances in Cryptology \u2013 EUROCRYPT\u201904 (Lecture Notes in Computer Science)","author":"Boneh Dan","key":"e_1_2_1_13_1","unstructured":"Dan Boneh and Xavier Boyen . 2004a. Efficient selective-ID secure identity based encryption without random oracles . In Advances in Cryptology \u2013 EUROCRYPT\u201904 (Lecture Notes in Computer Science) , Christian Cachin and Jan Camenisch (Eds.), Vol. 3027 . Springer , Germany , 223\u2013238. DOI:https:\/\/doi.org\/10.1007\/978-3-540-24676-3_14 10.1007\/978-3-540-24676-3_14 Dan Boneh and Xavier Boyen. 2004a. Efficient selective-ID secure identity based encryption without random oracles. In Advances in Cryptology \u2013 EUROCRYPT\u201904 (Lecture Notes in Computer Science), Christian Cachin and Jan Camenisch (Eds.), Vol. 3027. Springer, Germany, 223\u2013238. DOI:https:\/\/doi.org\/10.1007\/978-3-540-24676-3_14"},{"volume-title":"Advances in Cryptology \u2013 CRYPTO\u201904 (Lecture Notes in Computer Science)","author":"Boneh Dan","key":"e_1_2_1_14_1","unstructured":"Dan Boneh and Xavier Boyen . 2004b. Secure identity based encryption without random oracles . In Advances in Cryptology \u2013 CRYPTO\u201904 (Lecture Notes in Computer Science) , Matthew Franklin (Ed.), Vol. 3152 . Springer , Germany , 443\u2013459. DOI:https:\/\/doi.org\/10.1007\/978-3-540-28628-8_27 10.1007\/978-3-540-28628-8_27 Dan Boneh and Xavier Boyen. 2004b. Secure identity based encryption without random oracles. In Advances in Cryptology \u2013 CRYPTO\u201904 (Lecture Notes in Computer Science), Matthew Franklin (Ed.), Vol. 3152. Springer, Germany, 443\u2013459. DOI:https:\/\/doi.org\/10.1007\/978-3-540-28628-8_27"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11426639_26"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/646766.704155"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.64"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.67"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54242-8_3"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54631-0_29"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90005-0"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276741"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1766171.1766193"},{"volume-title":"Advances in Cryptology \u2013 EUROCRYPT\u201904 (Lecture Notes in Computer Science), Christian Cachin and Jan Camenisch (Eds.), Vol.\u00a03027","author":"Canetti Ran","key":"e_1_2_1_24_1","unstructured":"Ran Canetti , Shai Halevi , and Jonathan Katz . 2004. Chosen-ciphertext security from identity-based encryption . In Advances in Cryptology \u2013 EUROCRYPT\u201904 (Lecture Notes in Computer Science), Christian Cachin and Jan Camenisch (Eds.), Vol.\u00a03027 . Springer , Germany , 207\u2013222. DOI:https:\/\/doi.org\/10.1007\/978-3-540-24676-3_13 10.1007\/978-3-540-24676-3_13 Ran Canetti, Shai Halevi, and Jonathan Katz. 2004. Chosen-ciphertext security from identity-based encryption. In Advances in Cryptology \u2013 EUROCRYPT\u201904 (Lecture Notes in Computer Science), Christian Cachin and Jan Camenisch (Eds.), Vol.\u00a03027. Springer, Germany, 207\u2013222. DOI:https:\/\/doi.org\/10.1007\/978-3-540-24676-3_13"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5_27"},{"volume-title":"Advances in Cryptology \u2013 CRYPTO\u201917, Part II (Lecture Notes in Computer Science)","author":"Cho Chongwon","key":"e_1_2_1_26_1","unstructured":"Chongwon Cho , Nico D\u00f6ttling , Sanjam Garg , Divya Gupta , Peihan Miao , and Antigoni Polychroniadou . 2017. Laconic oblivious transfer and its applications . In Advances in Cryptology \u2013 CRYPTO\u201917, Part II (Lecture Notes in Computer Science) , Jonathan Katz and Hovav Shacham (Eds.), Vol. 10402 . Springer , Germany , 33\u201365. DOI:https:\/\/doi.org\/10.1007\/978-3-319-63715-0_2 10.1007\/978-3-319-63715-0_2 Chongwon Cho, Nico D\u00f6ttling, Sanjam Garg, Divya Gupta, Peihan Miao, and Antigoni Polychroniadou. 2017. Laconic oblivious transfer and its applications. In Advances in Cryptology \u2013 CRYPTO\u201917, Part II (Lecture Notes in Computer Science), Jonathan Katz and Hovav Shacham (Eds.), Vol. 10402. Springer, Germany, 33\u201365. DOI:https:\/\/doi.org\/10.1007\/978-3-319-63715-0_2"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/647995.742435"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1965598"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11745853_12"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055638"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-70500-2_13"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-76578-5_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488667"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-03807-6_25"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17259-6_3"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.22"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746593"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00457-5_26"},{"volume-title":"Advances in Cryptology \u2013 EUROCRYPT\u201914 (Lecture Notes in Computer Science), Phong Q","author":"Gentry Craig","key":"e_1_2_1_39_1","unstructured":"Craig Gentry , Shai Halevi , Steve Lu , Rafail Ostrovsky , Mariana Raykova , and Daniel Wichs . 2014. Garbled RAM revisited . In Advances in Cryptology \u2013 EUROCRYPT\u201914 (Lecture Notes in Computer Science), Phong Q . Nguyen and Elisabeth Oswald (Eds.), Vol. 8441 . Springer , Germany , 405\u2013422. DOI:https:\/\/doi.org\/10.1007\/978-3-642-55220-5_23 10.1007\/978-3-642-55220-5_23 Craig Gentry, Shai Halevi, Steve Lu, Rafail Ostrovsky, Mariana Raykova, and Daniel Wichs. 2014. Garbled RAM revisited. In Advances in Cryptology \u2013 EUROCRYPT\u201914 (Lecture Notes in Computer Science), Phong Q. Nguyen and Elisabeth Oswald (Eds.), Vol. 8441. Springer, Germany, 405\u2013422. DOI:https:\/\/doi.org\/10.1007\/978-3-642-55220-5_23"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374407"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/647098.717144"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1984.715949"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73010"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802212"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/0406010"},{"key":"e_1_2_1_46_1","volume-title":"Zur Theorie der abstrakten elliptischen Funktionenk\u00f6rper III. Die Struktur des Meromorphismenrings. Die Riemannsche Vermutung. J. reine und angewandte Math. 175","author":"Hasse Helmut","year":"1936","unstructured":"Helmut Hasse . 1936. Zur Theorie der abstrakten elliptischen Funktionenk\u00f6rper III. Die Struktur des Meromorphismenrings. Die Riemannsche Vermutung. J. reine und angewandte Math. 175 ( 1936 ), 193\u2013208. Helmut Hasse. 1936. Zur Theorie der abstrakten elliptischen Funktionenk\u00f6rper III. Die Struktur des Meromorphismenrings. Die Riemannsche Vermutung. J. reine und angewandte Math. 175 (1936), 193\u2013208."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_2_1_48_1","volume-title":"Reyneri","author":"Hellman Martin E.","year":"1983","unstructured":"Martin E. Hellman and Justin M . Reyneri . 1983 . Fast computation of discrete logarithms in GF (q). In Advances in Cryptology. Springer , 3\u201313. Martin E. Hellman and Justin M. Reyneri. 1983. Fast computation of discrete logarithms in GF (q). In Advances in Cryptology. Springer, 3\u201313."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/1777777.1777821"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03356-8_37"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/647087.715830"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73009"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/648185.749894"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-02-01482-5"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/11818175_19"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1987-0866109-5"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103466"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11799-2_27"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-008-9036-8"},{"volume-title":"Advances in Cryptology \u2013 EUROCRYPT\u201913 (Lecture Notes in Computer Science), Thomas Johansson and Phong Q","author":"Lu Steve","key":"e_1_2_1_61_1","unstructured":"Steve Lu and Rafail Ostrovsky . 2013. How to garble RAM programs . In Advances in Cryptology \u2013 EUROCRYPT\u201913 (Lecture Notes in Computer Science), Thomas Johansson and Phong Q . Nguyen (Eds.), Vol. 7881 . Springer , Germany , 719\u2013734. DOI:https:\/\/doi.org\/10.1007\/978-3-642-38348-9_42 10.1007\/978-3-642-38348-9_42 Steve Lu and Rafail Ostrovsky. 2013. How to garble RAM programs. In Advances in Cryptology \u2013 EUROCRYPT\u201913 (Lecture Notes in Computer Science), Thomas Johansson and Phong Q. Nguyen (Eds.), Vol. 7881. Springer, Germany, 719\u2013734. DOI:https:\/\/doi.org\/10.1007\/978-3-642-38348-9_42"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02351718"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.5555\/18262.25413"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73011"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.5555\/1803784"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.5555\/1881412.1881427"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85174-5_31"},{"volume-title":"Algebraic and Combinatoric Aspects of Cryptography. Number 6602","author":"Pohlig Stephen Carl","key":"e_1_2_1_69_1","unstructured":"Stephen Carl Pohlig . 1977. Algebraic and Combinatoric Aspects of Cryptography. Number 6602 . Stanford University . Stephen Carl Pohlig. 1977. Algebraic and Combinatoric Aspects of Cryptography. Number 6602. Stanford University."},{"key":"e_1_2_1_70_1","first-page":"918","article-title":"Monte Carlo methods for index computation (mod p)","volume":"32","author":"Pollard John M.","year":"1978","unstructured":"John M. Pollard . 1978 . Monte Carlo methods for index computation (mod p) . Math. Comput. 32 , 143 (1978), 918 \u2013 924 . John M. Pollard. 1978. Monte Carlo methods for index computation (mod p). Math. Comput. 32, 143 (1978), 918\u2013924.","journal-title":"Math. Comput."},{"key":"e_1_2_1_71_1","first-page":"187","article-title":"How to exchange secrets with oblivious transfer","volume":"2005","author":"Rabin Michael O.","year":"2005","unstructured":"Michael O. Rabin . 2005 . How to exchange secrets with oblivious transfer . IACR Cryptology ePrint Archive 2005 (2005), 187 . Michael O. Rabin. 2005. How to exchange secrets with oblivious transfer. IACR Cryptology ePrint Archive 2005 (2005), 187.","journal-title":"IACR Cryptology ePrint Archive"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060603"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359342"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299874.3319483"},{"key":"e_1_2_1_75_1","volume-title":"Proceedings of the Number Theory Conference. 217\u2013224","author":"Shanks Daniel","year":"1972","unstructured":"Daniel Shanks . 1972 . The infrastructure of a real quadratic field and its applications . In Proceedings of the Number Theory Conference. 217\u2013224 . Daniel Shanks. 1972. The infrastructure of a real quadratic field and its applications. In Proceedings of the Number Theory Conference. 217\u2013224."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_46"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.5555\/1754542.1754568"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03356-8_36"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1007\/11426639_7"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.5555\/1382436.1382751"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.25"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3422370","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3422370","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:03:21Z","timestamp":1750197801000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3422370"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,22]]},"references-count":78,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3422370"],"URL":"https:\/\/doi.org\/10.1145\/3422370","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2021,3,22]]},"assertion":[{"value":"2017-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}