{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T14:57:53Z","timestamp":1773154673566,"version":"3.50.1"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,1,6]],"date-time":"2021-01-06T00:00:00Z","timestamp":1609891200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NWO","award":["639.021.645"],"award-info":[{"award-number":["639.021.645"]}]},{"name":"European Union Horizon 2020 Research and Innovation Program","award":["780701"],"award-info":[{"award-number":["780701"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,4,30]]},"abstract":"<jats:p>\n            In this article, we study the geometry of units and ideals of cyclotomic rings and derive an algorithm to find a mildly short vector in any given cyclotomic ideal lattice in quantum polynomial time, under some plausible number-theoretic assumptions. More precisely, given an ideal lattice of the cyclotomic ring of conductor\n            <jats:italic>m<\/jats:italic>\n            , the algorithm finds an approximation of the shortest vector by a factor exp (\u00d5(\u221a\n            <jats:italic>m<\/jats:italic>\n            )). This result exposes an unexpected hardness gap between these structured lattices and general lattices: The best known polynomial time generic lattice algorithms can only reach an approximation factor exp (\u00d5(m)). Following a recent series of attacks, these results call into question the hardness of various problems over structured lattices, such as Ideal-SVP and Ring-LWE, upon which relies the security of a number of cryptographic schemes.\n          <\/jats:p>\n          <jats:p>\n            N\n            <jats:sc>OTE<\/jats:sc>\n            . This article is an extended version of a conference paper\u00a0[11]. The results are generalized to arbitrary cyclotomic fields. In particular, we also extend some results of Reference\u00a0[10] to arbitrary cyclotomic fields. In addition, we prove the numerical stability of the method of Reference\u00a0[10]. These extended results appeared in the Ph.D. dissertation of the third author\u00a0[46].\n          <\/jats:p>","DOI":"10.1145\/3431725","type":"journal-article","created":{"date-parts":[[2021,1,6]],"date-time":"2021-01-06T13:25:38Z","timestamp":1609939538000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Mildly Short Vectors in Cyclotomic Ideal Lattices in Quantum Polynomial Time"],"prefix":"10.1145","volume":"68","author":[{"given":"Ronald","family":"Cramer","sequence":"first","affiliation":[{"name":"CWI, Amsterdam and Leiden University, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L\u00e9o","family":"Ducas","sequence":"additional","affiliation":[{"name":"CWI, Amsterdam, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Wesolowski","sequence":"additional","affiliation":[{"name":"Univ. Bordeaux, CNRS, IMB, UMR 5251 and INRIA, LFANT, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,1,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48523-6_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579403"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1990-1023756-8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-56620-7_2"},{"key":"e_1_2_1_5_1","volume-title":"Advances in Cryptology -- (EUROCRYPT'17)","author":"Biasse Jean-Fran\u00e7ois","unstructured":"Jean-Fran\u00e7ois Biasse , Thomas Espitau , Pierre-Alain Fouque , Alexandre G\u00e9lin , and Paul Kirchner . 2017. Computing Generator in Cyclotomic Integer Rings . In Advances in Cryptology -- (EUROCRYPT'17) , J. S. Coron, J. Nielsen (Eds.). Lecture Notes in Computer Science, vol 10210. Springer , Cham. https:\/\/doi.org\/10.1007\/978-3-319-56620-7_3 10.1007\/978-3-319-56620-7_3 Jean-Fran\u00e7ois Biasse, Thomas Espitau, Pierre-Alain Fouque, Alexandre G\u00e9lin, and Paul Kirchner. 2017. Computing Generator in Cyclotomic Integer Rings. In Advances in Cryptology -- (EUROCRYPT'17), J. S. Coron, J. Nielsen (Eds.). Lecture Notes in Computer Science, vol 10210. Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-319-56620-7_3"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1112\/S1461157014000345"},{"key":"e_1_2_1_7_1","volume-title":"Selected Areas in Cryptography -- SAC","author":"Biasse Jean-Fran\u00e7ois","year":"2017","unstructured":"Jean-Fran\u00e7ois Biasse . 2018. Approximate short vectors in ideal lattices of Q(\u03b6pe) with precomputation of the class group . In Selected Areas in Cryptography -- SAC 2017 . Lecture Notes in Computer Science, Vol. 10719 , Carlisle Adams and Jan Camenisch (Eds.). Springer , 374--393. Jean-Fran\u00e7ois Biasse. 2018. Approximate short vectors in ideal lattices of Q(\u03b6pe) with precomputation of the class group. In Selected Areas in Cryptography -- SAC 2017. Lecture Notes in Computer Science, Vol. 10719, Carlisle Adams and Jan Camenisch (Eds.). Springer, 374--393."},{"key":"e_1_2_1_8_1","volume-title":"High Primes and Misdemeanours: Lectures in Honour of the 60th Birthday of Hugh Cowie Williams","author":"Buhler Joe","unstructured":"Joe Buhler , Carl Pomerance , and Leanne Robertson . 2004. Heuristics for class numbers of prime-power real cyclotomic fields . In High Primes and Misdemeanours: Lectures in Honour of the 60th Birthday of Hugh Cowie Williams . Fields Institute Communications - Springer , 149--157. Joe Buhler, Carl Pomerance, and Leanne Robertson. 2004. Heuristics for class numbers of prime-power real cyclotomic fields. In High Primes and Misdemeanours: Lectures in Honour of the 60th Birthday of Hugh Cowie Williams. Fields Institute Communications - Springer, 149--157."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch64"},{"key":"e_1_2_1_10_1","volume-title":"Recovering Short Generators of Principal Ideals in Cyclotomic Rings","author":"Cramer Ronald","unstructured":"Ronald Cramer , L\u00e9o Ducas , Chris Peikert , and Oded Regev . 2016. Recovering Short Generators of Principal Ideals in Cyclotomic Rings . Springer Berlin , 559--585. Ronald Cramer, L\u00e9o Ducas, Chris Peikert, and Oded Regev. 2016. Recovering Short Generators of Principal Ideals in Cyclotomic Rings. Springer Berlin, 559--585."},{"key":"e_1_2_1_11_1","volume-title":"Advances in Cryptology (EUROCRYPT\u201917) Jean-S\u00e9bastien Coron and Jesper Buus Nielsen (Eds.)","author":"Cramer Ronald","unstructured":"Ronald Cramer , L\u00e9o Ducas , and Benjamin Wesolowski . 2017. Short Stickelberger class relations and application to ideal-SVP . In Advances in Cryptology (EUROCRYPT\u201917) Jean-S\u00e9bastien Coron and Jesper Buus Nielsen (Eds.) . Springer International Publishing , Cham , 324--348. Ronald Cramer, L\u00e9o Ducas, and Benjamin Wesolowski. 2017. Short Stickelberger class relations and application to ideal-SVP. In Advances in Cryptology (EUROCRYPT\u201917) Jean-S\u00e9bastien Coron and Jesper Buus Nielsen (Eds.). Springer International Publishing, Cham, 324--348."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of theETSI 2nd Quantum-Safe Crypto Workshop","author":"Campbell Peter","year":"2014","unstructured":"Peter Campbell , Michael Groves , and Dan Shepherd . 2014 . Soliloquy: A cautionary tale . In Proceedings of theETSI 2nd Quantum-Safe Crypto Workshop Retrieved from http:\/\/docbox.etsi.org\/Workshop\/2014\/201410_CRYPTO\/S07_Systems_and_Attacks\/S07_Groves_Annex.pdf. Peter Campbell, Michael Groves, and Dan Shepherd. 2014. Soliloquy: A cautionary tale. In Proceedings of theETSI 2nd Quantum-Safe Crypto Workshop Retrieved from http:\/\/docbox.etsi.org\/Workshop\/2014\/201410_CRYPTO\/S07_Systems_and_Attacks\/S07_Groves_Annex.pdf."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45724-2_12"},{"key":"e_1_2_1_14_1","series-title":"Lecture Notes in Computer Science, vol 11692","volume-title":"Advances in Cryptology -- (CRYPTO'19), A. Boldyreva and D. Micciancio (Eds)","author":"Ducas L\u00e9o","unstructured":"L\u00e9o Ducas , Maxime Plan\u00e7on , and Benjamin Wesolowski . 2019. On the shortness of vectors to be found by the Ideal-SVP Quantum Algorithm . In Advances in Cryptology -- (CRYPTO'19), A. Boldyreva and D. Micciancio (Eds) . Lecture Notes in Computer Science, vol 11692 . Springer , Cham . https:\/\/doi.org\/10.1007\/978-3-030-26948-7_12 10.1007\/978-3-030-26948-7_12 L\u00e9o Ducas, Maxime Plan\u00e7on, and Benjamin Wesolowski. 2019. On the shortness of vectors to be found by the Ideal-SVP Quantum Algorithm. In Advances in Cryptology -- (CRYPTO'19), A. Boldyreva and D. Micciancio (Eds). Lecture Notes in Computer Science, vol 11692. Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-030-26948-7_12"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.40"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591860"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01393839"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38348-9_1"},{"key":"e_1_2_1_19_1","volume-title":"Buchmann","author":"Holzer Patrick","year":"2017","unstructured":"Patrick Holzer , Thomas Wunderer , and Johannes A . Buchmann . 2017 . Recovering short generators of principal fractional ideals in cyclotomic fields of conductor p\u03b1 q\u03b2. In Proceedings of the International Conference on Cryptology. Springer , 346--368. Patrick Holzer, Thomas Wunderer, and Johannes A. Buchmann. 2017. Recovering short generators of principal fractional ideals in cyclotomic fields of conductor p\u03b1 q\u03b2. In Proceedings of the International Conference on Cryptology. Springer, 346--368."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jnt.2008.11.006"},{"key":"e_1_2_1_21_1","volume-title":"On graphs of isogenies of principally polarizable Abelian surfaces and the discrete logarithm problem. CoRR","author":"Jetchev Dimitar","year":"2015","unstructured":"Dimitar Jetchev and Benjamin Wesolowski . 2015. On graphs of isogenies of principally polarizable Abelian surfaces and the discrete logarithm problem. CoRR ( 2015 ), abs\/1506.00522. Dimitar Jetchev and Benjamin Wesolowski. 2015. On graphs of isogenies of principally polarizable Abelian surfaces and the discrete logarithm problem. CoRR (2015), abs\/1506.00522."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-314X(92)90003-8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_13"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535925"},{"key":"e_1_2_1_26_1","unstructured":"Changmin Lee Alice Pellet-Mary Damien Stehl\u00e9 and Alexandre Wallet. 2019. An LLL algorithm for module lattices. Retrieved from https:\/\/eprint.iacr.org\/2019\/1035.  Changmin Lee Alice Pellet-Mary Damien Stehl\u00e9 and Alexandre Wallet. 2019. An LLL algorithm for module lattices. Retrieved from https:\/\/eprint.iacr.org\/2019\/1035."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55220-5_14"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0234-9"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2015-02924-X"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17656-3_24"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_8"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055489"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the International Symposium on Information Theory and Its Applications (ISITA).","author":"Rekaya Ghaya","year":"2004","unstructured":"Ghaya Rekaya , Jean-Claude Belfiore , and Emanuele Viterbo . 2004 . A very efficient lattice reduction tool on fast fading channels . In Proceedings of the International Symposium on Information Theory and Its Applications (ISITA). Ghaya Rekaya, Jean-Claude Belfiore, and Emanuele Viterbo. 2004. A very efficient lattice reduction tool on fast fading channels. In Proceedings of the International Symposium on Information Theory and Its Applications (ISITA)."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568324"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90064-8"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-98-00939-9"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-02-01432-1"},{"key":"e_1_2_1_38_1","unstructured":"Ren\u00e9 Schoof. 2010. Catalan\u2019s Conjecture. Springer Science 8 Business Media.  Ren\u00e9 Schoof. 2010. Catalan\u2019s Conjecture. Springer Science 8 Business Media."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581144"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.2307\/1970932"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10366-7_36"},{"key":"e_1_2_1_43_1","volume-title":"Smart and Frederik Vercauteren","author":"Nigel","year":"2010","unstructured":"Nigel P. Smart and Frederik Vercauteren . 2010 . Fully homomorphic encryption with relatively small key and ciphertext sizes. In Proceedings of the International Workshop on Public Key Cryptography. Springer , 420--443. Nigel P. Smart and Frederik Vercauteren. 2010. Fully homomorphic encryption with relatively small key and ciphertext sizes. In Proceedings of the International Workshop on Public Key Cryptography. Springer, 420--443."},{"key":"e_1_2_1_44_1","volume-title":"Introduction to Cyclotomic Fields","author":"Washington Lawrence C.","unstructured":"Lawrence C. Washington . 2012. Introduction to Cyclotomic Fields , Vol. 83 . Springer Science 8 Business Media. Lawrence C. Washington. 2012. Introduction to Cyclotomic Fields, Vol. 83. Springer Science 8 Business Media."},{"key":"e_1_2_1_45_1","unstructured":"Andr\u00e9 Weil. 1974. Sommes de Jacobi et caract\u00e8res de Hecke. Nachrichten der Akademie der Wissenschaften in G\u00f6ttingen 2 Mathematisch-Physikalische Klasse. Vandenhoeck 8 Ruprecht.  Andr\u00e9 Weil. 1974. Sommes de Jacobi et caract\u00e8res de Hecke. Nachrichten der Akademie der Wissenschaften in G\u00f6ttingen 2 Mathematisch-Physikalische Klasse. Vandenhoeck 8 Ruprecht."},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 13th Algorithmic Number Theory Symposium (ANTS\u201918)","author":"Wesolowski Benjamin","year":"2018","unstructured":"Benjamin Wesolowski . 2018 . Generating subgroups of ray class groups with small prime ideals . In Proceedings of the 13th Algorithmic Number Theory Symposium (ANTS\u201918) . Benjamin Wesolowski. 2018. Generating subgroups of ray class groups with small prime ideals. In Proceedings of the 13th Algorithmic Number Theory Symposium (ANTS\u201918)."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3431725","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3431725","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:46Z","timestamp":1750195486000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3431725"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,6]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4,30]]}},"alternative-id":["10.1145\/3431725"],"URL":"https:\/\/doi.org\/10.1145\/3431725","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,6]]},"assertion":[{"value":"2019-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}