{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T01:06:20Z","timestamp":1759799180315,"version":"build-2065373602"},"reference-count":137,"publisher":"International Association for Cryptologic Research","issue":"3","license":[{"start":{"date-parts":[[2025,7,8]],"date-time":"2025-07-08T00:00:00Z","timestamp":1751932800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-2022-03187"],"award-info":[{"award-number":["RGPIN-2022-03187"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["ALLRP 578463-22"],"award-info":[{"award-number":["ALLRP 578463-22"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2025,9,2]]},"abstract":"<jats:p>  Large-scale quantum computers capable of implementing Shor's algorithm pose a significant threat to the security of the most widely used public-key cryptographic schemes.   This risk has motivated substantial efforts by standards bodies and government agencies to identify and standardize quantum-safe cryptographic systems.   Among the proposed solutions, lattice-based cryptography has emerged as the foundation for some of the most promising protocols.<\/jats:p>\n          <jats:p>  This paper describes FrodoKEM, a family of conservative key-encapsulation mechanisms (KEMs) whose security is based on generic, \u201cunstructured\u201d lattices.   FrodoKEM is proposed as an alternative to the more efficient lattice schemes that utilize algebraically structured lattices, such as the recently standardized ML-KEM scheme.   By relying on generic lattices, FrodoKEM minimizes the potential for future attacks that exploit algebraic structures while enabling simple and compact implementations.   Our plain C implementations demonstrate that, despite its conservative design and parameterization, FrodoKEM remains practical.   For instance, the full protocol at NIST security level 1 runs in approximately 0.97 ms on a server-class processor, and 4.98 ms on a smartphone-class processor.<\/jats:p>\n          <jats:p>  FrodoKEM obtains (single-target) IND-CCA security using a variant of the Fujisaki-Okamoto transform, applied to an underlying public-key encryption scheme called FrodoPKE.   In addition, using a new tool called the Salted Fujisaki-Okamoto (SFO) transform, FrodoKEM is also shown to tightly achieve multi-target security, without increasing the FrodoPKE message length and with a negligible performance impact, based on the multi-target IND-CPA security of FrodoPKE. <\/jats:p>","DOI":"10.62056\/ayivom2hd","type":"journal-article","created":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T18:49:52Z","timestamp":1759776592000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["FrodoKEM: A CCA-Secure Learning With Errors Key Encapsulation Mechanism"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-7165-6150","authenticated-orcid":false,"given":"Lewis","family":"Glabush","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/02s376052","id-type":"ROR","asserted-by":"publisher"}],"name":"EPFL","place":["Lausanne, Switzerland"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5791-6341","authenticated-orcid":false,"given":"Patrick","family":"Longa","sequence":"additional","affiliation":[{"name":"Microsoft Research","place":["Redmond, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-7119-5242","authenticated-orcid":false,"given":"Michael","family":"Naehrig","sequence":"additional","affiliation":[{"name":"Microsoft Research","place":["Redmond, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0419-7501","authenticated-orcid":false,"given":"Chris","family":"Peikert","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00jmfr291","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Michigan","place":["Ann Arbor, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9443-3170","authenticated-orcid":false,"given":"Douglas","family":"Stebila","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01aff2v68","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Waterloo","place":["Waterloo, Canada"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0001-2955","authenticated-orcid":false,"given":"Fernando","family":"Virdia","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/0220mzb33","id-type":"ROR","asserted-by":"publisher"}],"name":"King's College London","place":["London, United Kingdom"]}]}],"member":"48349","published-online":{"date-parts":[[2025,10,6]]},"reference":[{"key":"ref1:You_2005","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1063\/1.2155757","article-title":"Superconducting Circuits and Quantum Information","volume":"58","author":"J. Q. You","year":"2005","journal-title":"Physics Today","ISSN":"https:\/\/id.crossref.org\/issn\/1945-0699","issn-type":"electronic"},{"key":"ref2:Kelly_2015","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1038\/nature14270","article-title":"State preservation by repetitive error detection in a\n  superconducting quantum circuit","volume":"519","author":"J. Kelly","year":"2015","journal-title":"Nature","ISSN":"https:\/\/id.crossref.org\/issn\/1476-4687","issn-type":"electronic"},{"key":"ref3:NIST17","volume-title":"Post-Quantum Cryptography Standardization Project","author":"National Institute of Standards","year":"2017"},{"key":"ref4:Reg09","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1145\/1568318.1568324","article-title":"On lattices, learning with errors, random linear codes, and\n  cryptography","volume":"56","author":"Oded Regev","year":"2009","journal-title":"Journal of the ACM"},{"key":"ref5:STOC:Ajtai96","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1145\/237814.237838","article-title":"Generating Hard Instances of Lattice Problems (Extended\n  Abstract)","author":"Mikl\u00f3s Ajtai","year":"1996"},{"key":"ref6:MLKEM","doi-asserted-by":"crossref","DOI":"10.6028\/NIST.FIPS.203","volume-title":"Module-Lattice-Based Key-Encapsulation Mechanism Standard\n  (FIPS 203)","author":"National Institute of Standards","year":"2024"},{"key":"ref7:MLDSA","doi-asserted-by":"crossref","DOI":"10.6028\/NIST.FIPS.204","volume-title":"Module-Lattice-Based Digital Signature Standard (FIPS\n  204)","author":"National Institute of Standards","year":"2024"},{"key":"ref8:CME","volume-title":"Classic McEliece: conservative code-based cryptography","author":"Martin R. Albrecht"},{"key":"ref9:BSI","volume-title":"Cryptographic Mechanisms: Recommendations and Key Lengths,\n  BSI TR-02102-1, Version: 2024-1","author":"Federal Office for Information Security (BSI)","year":"2024"},{"key":"ref10:ANSSI","volume-title":"ANSSI views on the Post-Quantum Cryptography transition\n  (2023 follow up)","author":"National Cybersecurity Agency of France (ANSSI)","year":"2023"},{"key":"ref11:AIVD","volume-title":"Prepare for the threat of quantum computers","author":"General Intelligence","year":"2022"},{"key":"ref12:Dutch_HB","volume-title":"The PQC Migration Handbook: Guidelines for Migrating to\n  Post-Quantum Cryptography (second edition)","author":"General Intelligence","year":"2024"},{"key":"ref13:ISO","volume-title":"ISO\/IEC 18033-2:2006\/DAmd 2, Information technology \u2013\n  Security techniques \u2013 Encryption algorithms \u2013 Part 2: Asymmetric ciphers","author":"International Organization for Standardization (ISO)","year":"2024"},{"key":"ref14:Micciancio10","series-title":"Information Security and Cryptography","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/978-3-642-02295-1_13","article-title":"Cryptographic Functions from Worst-Case Complexity\n  Assumptions","author":"Daniele Micciancio","year":"2010"},{"key":"ref15:RegevLWESurvey","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1109\/CCC.2010.26","article-title":"The Learning with Errors Problem (Invited Survey)","author":"Oded Regev","year":"2010"},{"key":"ref16:DBLP:journals\/fttcs\/Peikert16","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1561\/0400000074","article-title":"A Decade of Lattice Cryptography","volume":"10","author":"Chris Peikert","year":"2016","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"ref17:STOC:AjtDwo97","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1145\/258533.258604","article-title":"A Public-Key Cryptosystem with Worst-Case\/Average-Case\n  Equivalence","author":"Mikl\u00f3s Ajtai","year":"1997"},{"key":"ref18:EPRINT:GolGolHal96a","volume-title":"Collision-Free Hashing from Lattice Problems","author":"Oded Goldreich","year":"1996"},{"key":"ref19:FOCS:CaiNer97","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1109\/SFCS.1997.646135","article-title":"An Improved Worst-Case to Average-Case Connection for\n  Lattice Problems","author":"Jin-yi Cai","year":"1997"},{"key":"ref20:STOC:Micciancio02","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1145\/509907.509995","article-title":"Improved cryptographic hash functions with\n  worst-case\/average-case connection","author":"Daniele Micciancio","year":"2002"},{"key":"ref21:DBLP:journals\/jacm\/Regev04","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1145\/1039488.1039490","article-title":"New lattice-based cryptographic constructions","volume":"51","author":"Oded Regev","year":"2004","journal-title":"J.\u00a0ACM"},{"key":"ref22:DBLP:journals\/siamcomp\/MicciancioR07","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1137\/S0097539705447360","article-title":"Worst-Case to Average-Case Reductions Based on Gaussian\n  Measures.","volume":"37","author":"Daniele Micciancio","year":"2007","journal-title":"SIAM J.\u00a0Comput."},{"key":"ref23:TCC:Peikert09_slides","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1007\/978-3-642-00457-5_5","article-title":"Some Recent Progress in Lattice-Based Cryptography","volume":"5444","author":"Chris Peikert","year":"2009"},{"key":"ref24:DifHel76","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","article-title":"New Directions in Cryptography","volume":"22","author":"Whitfield Diffie","year":"1976","journal-title":"IEEE Transactions on Information Theory"},{"key":"ref25:STOC:Peikert09","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/1536414.1536461","article-title":"Public-key cryptosystems from the worst-case shortest vector\n  problem: extended abstract","author":"Chris Peikert","year":"2009"},{"key":"ref26:C:ACPS09","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/978-3-642-03356-8_35","article-title":"Fast Cryptographic Primitives and Circular-Secure Encryption\n  Based on Hard Learning Problems","volume":"5677","author":"Benny Applebaum","year":"2009"},{"key":"ref27:STOC:BLPRS13","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1145\/2488608.2488680","article-title":"Classical hardness of learning with errors","author":"Zvika Brakerski","year":"2013"},{"key":"ref28:EC:DotMul13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/978-3-642-38348-9_2","article-title":"Lossy Codes and a New Variant of the Learning-With-Errors\n  Problem","volume":"7881","author":"Nico D\u00f6ttling","year":"2013"},{"key":"ref29:C:MicPei13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-642-40041-4_2","article-title":"Hardness of SIS and LWE with Small Parameters","volume":"8042","author":"Daniele Micciancio","year":"2013"},{"key":"ref30:STOC:PeiRegSte17","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1145\/3055399.3055489","article-title":"Pseudorandomness of ring-LWE for any ring and modulus","author":"Chris Peikert","year":"2017"},{"key":"ref31:MR09:_post_quant_crypt","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-540-88702-7_5","article-title":"Lattice-based Cryptography","author":"Daniele Micciancio","year":"2009"},{"key":"ref32:AC:CheNgu11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-25385-0_1","article-title":"BKZ 2.0: Better Lattice Security Estimates","volume":"7073","author":"Yuanmi Chen","year":"2011"},{"key":"ref33:RSA:LiuNgu13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/978-3-642-36095-4_19","article-title":"Solving BDD by Enumeration: An Update","volume":"7779","author":"Mingjie Liu","year":"2013"},{"key":"ref34:ICISC:AlbFitGop13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/978-3-319-12160-4_18","article-title":"On the Efficacy of Solving LWE by Reduction to\n  Unique-SVP","volume":"8565","author":"Martin R. Albrecht","year":"2014"},{"key":"ref35:ChenThesis","volume-title":"Lattice reduction and concrete security of fully homomorphic\n  encryption","author":"Yuanmi Chen","year":"2013"},{"key":"ref36:EPRINT:ACFP14","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1145\/2815111.2815158","article-title":"Algebraic Algorithms for LWE","volume":"49","author":"Martin R. Albrecht","year":"2015","journal-title":"ACM Commun. Comput. Algebra"},{"key":"ref37:PKC:AFFP14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/978-3-642-54631-0_25","article-title":"Lazy Modulus Switching for the BKW Algorithm on LWE","volume":"8383","author":"Martin R. Albrecht","year":"2014"},{"key":"ref38:LaarhovenThesis","volume-title":"Search problems in cryptography","author":"Thijs Laarhoven","year":"2015"},{"key":"ref39:C:KirFou15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/978-3-662-47989-6_3","article-title":"An Improved BKW Algorithm for LWE with Applications to\n  Cryptography and Lattices","volume":"9215","author":"Paul Kirchner","year":"2015"},{"key":"ref40:albrecht15:_concrete_lwe","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1515\/jmc-2015-0016","article-title":"On the concrete hardness of Learning with Errors","volume":"9","author":"Martin R. Albrecht","year":"2015","journal-title":"Journal of Mathematical Cryptology"},{"key":"ref41:USENIX:ADPS16","first-page":"327","article-title":"Post-quantum Key Exchange - A New Hope","author":"Erdem Alkim","year":"2016"},{"key":"ref42:CCS:BCDMNN16","doi-asserted-by":"publisher","first-page":"1006","DOI":"10.1145\/2976749.2978425","article-title":"Frodo: Take off the Ring! Practical, Quantum-Secure Key\n  Exchange from LWE","author":"Joppe W. Bos","year":"2016"},{"key":"ref43:EC:Albrecht17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/978-3-319-56614-6_4","article-title":"On Dual Lattice Attacks Against Small-Secret LWE and\n  Parameter Choices in HElib and SEAL","volume":"10211","author":"Martin R. Albrecht","year":"2017"},{"key":"ref44:EPRINT:AGVW17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/978-3-319-70694-8_11","article-title":"Revisiting the Expected Cost of Solving uSVP and\n  Applications to LWE","volume":"10624","author":"Martin R. Albrecht","year":"2017"},{"key":"ref45:STOC:PeiWat08","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1145\/1374376.1374406","article-title":"Lossy trapdoor functions and their applications","author":"Chris Peikert","year":"2008"},{"key":"ref46:C:PeiVaiWat08","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/978-3-540-85174-5_31","article-title":"A Framework for Efficient and Composable Oblivious\n  Transfer","volume":"5157","author":"Chris Peikert","year":"2008"},{"key":"ref47:STOC:GenPeiVai08","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1145\/1374376.1374407","article-title":"Trapdoors for hard lattices and new cryptographic\n  constructions","author":"Craig Gentry","year":"2008"},{"key":"ref48:JC:CHKP12","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1007\/s00145-011-9105-2","article-title":"Bonsai Trees, or How to Delegate a Lattice Basis","volume":"25","author":"David Cash","year":"2012","journal-title":"Journal of Cryptology"},{"key":"ref49:FOCS:BraVai11","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1109\/FOCS.2011.12","article-title":"Efficient Fully Homomorphic Encryption from (Standard)\n  LWE","author":"Zvika Brakerski","year":"2011"},{"key":"ref50:C:GenSahWat13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-40041-4_5","article-title":"Homomorphic Encryption from Learning with Errors:\n  Conceptually-Simpler, Asymptotically-Faster, Attribute-Based","volume":"8042","author":"Craig Gentry","year":"2013"},{"key":"ref51:EC:BGGHNS14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/978-3-642-55220-5_30","article-title":"Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE\n  and Compact Garbled Circuits","volume":"8441","author":"Dan Boneh","year":"2014"},{"key":"ref52:C:GorVaiWee15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/978-3-662-48000-7_25","article-title":"Predicate Encryption for Circuits from LWE","volume":"9216","author":"Sergey Gorbunov","year":"2015"},{"key":"ref53:RSA:LinPei11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-642-19074-2_21","article-title":"Better Key Sizes (and Attacks) for LWE-Based Encryption","volume":"6558","author":"Richard Lindner","year":"2011"},{"key":"ref54:NISTPQC-R1:FrodoKEM17","volume-title":"FrodoKEM","author":"Michael Naehrig","year":"2017"},{"key":"ref55:NISTPQC-R2:FrodoKEM19","volume-title":"FrodoKEM","author":"Michael Naehrig","year":"2019"},{"key":"ref56:NISTPQC-R3:FrodoKEM20","volume-title":"FrodoKEM","author":"Michael Naehrig","year":"2020"},{"key":"ref57:PKC:FujOka99","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/3-540-49162-7_5","article-title":"How to Enhance the Security of Public-Key Encryption at\n  Minimum Cost","volume":"1560","author":"Eiichiro Fujisaki","year":"1999"},{"key":"ref58:EPRINT:DinXieLin12","volume-title":"A Simple Provably Secure Key Exchange Scheme Based on the\n  Learning with Errors Problem","author":"Jintai Ding","year":"2012"},{"key":"ref59:PQCRYPTO:Peikert14","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/978-3-319-11659-4_12","article-title":"Lattice Cryptography for the Internet","author":"Chris Peikert","year":"2014"},{"key":"ref60:SP:BCNS15","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1109\/SP.2015.40","article-title":"Post-Quantum Key Exchange for the TLS Protocol from the\n  Ring Learning with Errors Problem","author":"Joppe W. Bos","year":"2015"},{"key":"ref61:ISOdraft","volume-title":"FrodoKEM Preliminary Standardization Proposal (submitted to\n  ISO)","author":"Erdem Alkim"},{"key":"ref62:DBLP:journals\/jacm\/LyubashevskyPR13","doi-asserted-by":"publisher","DOI":"10.1145\/2535925","article-title":"On Ideal Lattices and Learning with Errors Over Rings","volume":"60","author":"Vadim Lyubashevsky","year":"2013","journal-title":"Journal of the ACM"},{"key":"ref63:ITCS:BraGenVai12","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1145\/2090236.2090262","article-title":"(Leveled) fully homomorphic encryption without\n  bootstrapping","author":"Zvika Brakerski","year":"2012"},{"key":"ref64:DBLP:journals\/dcc\/LangloisS15","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/S10623-014-9938-4","article-title":"Worst-case to average-case reductions for module lattices","volume":"75","author":"Adeline Langlois","year":"2015","journal-title":"Designs, Codes and Cryptography"},{"key":"ref65:HofPipSil98","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/BFB0054868","article-title":"NTRU: A Ring-Based Public Key Cryptosystem","volume":"1423","author":"Jeffrey Hoffstein","year":"1998"},{"key":"ref66:AFRICACRYPT:Schneider13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/978-3-642-38553-7_22","article-title":"Sieving for Shortest Vectors in Ideal Lattices","volume":"7918","author":"Michael Schneider","year":"2013"},{"key":"ref67:PKC:IKMT14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/978-3-642-54631-0_24","article-title":"Parallel Gauss Sieve Algorithm: Solving the SVP Challenge\n  over a 128-Dimensional Ideal Lattice","volume":"8383","author":"Tsukasa Ishiguro","year":"2014"},{"key":"ref68:BNP_IJAC16","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1504\/IJACT.2017.10010312","article-title":"Sieving for Shortest Vectors in Ideal Lattices: a Practical\n  Perspective","volume":"3","author":"Joppe W. Bos","year":"2017","journal-title":"Int.\u00a0J.\u00a0 of Applied Cryptography"},{"key":"ref69:C:Laarhoven15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-662-47989-6_1","article-title":"Sieving for Shortest Vectors in Lattices Using Angular\n  Locality-Sensitive Hashing","volume":"9215","author":"Thijs Laarhoven","year":"2015"},{"key":"ref70:C:ELOS15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/978-3-662-47989-6_4","article-title":"Provably Weak Instances of Ring-LWE","volume":"9215","author":"Yara Elias","year":"2015"},{"key":"ref71:EPRINT:CheLauSta15","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1137\/16M1096566","article-title":"Attacks on the Search RLWE Problem with Small Errors","volume":"1","author":"Hao Chen","year":"2017","journal-title":"SIAM J. Appl. Algebra Geom."},{"key":"ref72:EC:CasIliVer16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-662-49890-3_6","article-title":"Provably Weak Instances of Ring-LWE Revisited","volume":"9665","author":"Wouter Castryck","year":"2016"},{"key":"ref73:EPRINT:CheLauSta16","volume-title":"Vulnerable Galois RLWE Families and Improved Attacks","author":"Hao Chen","year":"2016"},{"key":"ref74:SCN:Peikert16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/978-3-319-44618-9_22","article-title":"How (Not) to Instantiate Ring-LWE","volume":"9841","author":"Chris Peikert","year":"2016"},{"key":"ref75:EC:KirFou17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-56620-7_1","article-title":"Revisiting Lattice Attacks on Overstretched NTRU\n  Parameters","volume":"10210","author":"Paul Kirchner","year":"2017"},{"key":"ref76:soliloquyattack","volume-title":"Soliloquy: a Cautionary Tale","author":"Peter Campbell","year":"2014"},{"key":"ref77:EC:CDPR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1007\/978-3-662-49896-5_20","article-title":"Recovering Short Generators of Principal Ideals in\n  Cyclotomic Rings","volume":"9666","author":"Ronald Cramer","year":"2016"},{"key":"ref78:EC:CraDucWes17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/978-3-319-56620-7_12","article-title":"Short Stickelberger Class Relations and Application to\n  Ideal-SVP","volume":"10210","author":"Ronald Cramer","year":"2017"},{"key":"ref79:lenstra82:_factor","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"Arjen K. Lenstra","year":"1982","journal-title":"Mathematische Annalen"},{"key":"ref80:DBLP:journals\/tcs\/Schnorr87","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","article-title":"A Hierarchy of Polynomial Time Lattice Basis Reduction\n  Algorithms","volume":"53","author":"Claus-Peter Schnorr","year":"1987","journal-title":"Theoretical Computer Science"},{"key":"ref81:EC:PelHanSte19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1007\/978-3-030-17656-3_24","article-title":"Approx-SVP in Ideal Lattices with Pre-processing","volume":"11477","author":"Alice Pellet-Mary","year":"2019"},{"key":"ref82:perlner21","volume-title":"Multi-ciphertext attacks","author":"Ray Perlner","year":"2021"},{"key":"ref83:EPRINT:Bernstein22d","volume-title":"Multi-ciphertext security degradation for lattices","author":"Daniel J. Bernstein","year":"2022"},{"key":"ref84:EPRINT:GlaHovSte25","volume-title":"Tight Multi-challenge Security Reductions for Key\n  Encapsulation Mechanisms","author":"Lewis Glabush","year":"2025"},{"key":"ref85:GlabushThesis","volume-title":"Tight Multi-Target Security for Key Encapsulation\n  Mechanisms","author":"Lewis Glabush","year":"2024"},{"key":"ref86:TCC:HofHovKil17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/978-3-319-70500-2_12","article-title":"A Modular Analysis of the Fujisaki-Okamoto\n  Transformation","volume":"10677","author":"Dennis Hofheinz","year":"2017"},{"key":"ref87:CCS:DHKLS21","doi-asserted-by":"publisher","first-page":"2722","DOI":"10.1145\/3460120.3484819","article-title":"Faster Lattice-Based KEMs via a Generic Fujisaki-Okamoto\n  Transform Using Prefix Hashing","author":"Julien Duman","year":"2021"},{"key":"ref88:EC:BelBolMic00","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/3-540-45539-6_18","article-title":"Public-Key Encryption in a Multi-user Setting: Security\n  Proofs and Improvements","volume":"1807","author":"Mihir Bellare","year":"2000"},{"key":"ref89:dworkin2015sha","volume-title":"SHA-3 standard: Permutation-based hash and\n  extendable-output functions","author":"Morris J. Dworkin","year":"2015"},{"key":"ref90:C:FujOka99","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/3-540-48405-1_34","article-title":"Secure Integration of Asymmetric and Symmetric Encryption\n  Schemes","volume":"1666","author":"Eiichiro Fujisaki","year":"1999"},{"key":"ref91:TCC:TarUnr16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/978-3-662-53644-5_8","article-title":"Post-Quantum Security of the Fujisaki-Okamoto and OAEP\n  Transforms","volume":"9986","author":"Ehsan Ebrahimi Targhi","year":"2016"},{"key":"ref92:FrodoUpdates","volume-title":"Annex on FrodoKEM Updates","author":"Erdem Alkim","year":"2023"},{"key":"ref93:EuroSP:Kyber","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1109\/EuroSP.2018.00032","article-title":"CRYSTALS \u2014 Kyber: A CCA-Secure Module-Lattice-Based\n  KEM","author":"Joppe Bos","year":"2018"},{"key":"ref94:C:GuoJohNil20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/978-3-030-56880-1_13","article-title":"A Key-Recovery Timing Attack on Post-quantum Primitives\n  Using the Fujisaki-Okamoto Transformation and Its Application on\n  FrodoKEM","volume":"12171","author":"Qian Guo","year":"2020"},{"key":"ref95:NISTPQC-R3:CRYSTALS-Kyber20","volume-title":"CRYSTALS-KYBER","author":"Peter Schwabe","year":"2020"},{"key":"ref96:EC:LanSteSte14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-642-55220-5_14","article-title":"GGHLite: More Efficient Multilinear Maps from Ideal\n  Lattices","volume":"8441","author":"Adeline Langlois","year":"2014"},{"key":"ref97:C:JZCWM18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/978-3-319-96878-0_4","article-title":"IND-CCA-Secure Key Encapsulation Mechanism in the\n  Quantum Random Oracle Model, Revisited","volume":"10993","author":"Haodong Jiang","year":"2018"},{"key":"ref98:AC:HovHulMaj22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1007\/978-3-031-22972-5_15","article-title":"Failing Gracefully: Decryption Failures and the\n  Fujisaki-Okamoto Transform","volume":"13794","author":"Kathrin H\u00f6velmanns","year":"2022"},{"key":"ref99:dachman2020lwe","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/978-3-030-56880-1_12","article-title":"LWE with Side Information: Attacks and Concrete Security\n  Estimation","volume":"12171","author":"Dana Dachman-Soled","year":"2020"},{"key":"ref100:_JoC:LiNgu24","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-024-09527-0","article-title":"A Complete Analysis of the BKZ Lattice Reduction Algorithm","volume":"38","author":"Jianwei Li","year":"2024","journal-title":"J. Cryptol.","ISSN":"https:\/\/id.crossref.org\/issn\/0933-2790","issn-type":"electronic"},{"key":"ref101:FCT:SE91","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/3-540-54458-5_51","article-title":"Lattice basis reduction: Improved practical algorithms and\n  solving subset sum problems","volume":"529","author":"Claus-Peter Schnorr","year":"1991"},{"key":"ref102:schnorr1994lattice","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/BF01581144","article-title":"Lattice basis reduction: Improved practical algorithms and\n  solving subset sum problems","volume":"66","author":"Claus-Peter Schnorr","year":"1994","journal-title":"Mathematical Programming"},{"key":"ref103:EC:AWHT16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1007\/978-3-662-49890-3_30","article-title":"Improved Progressive BKZ Algorithms and Their Precise Cost\n  Estimation by Sharp Simulator","volume":"9665","author":"Yoshinori Aono","year":"2016"},{"key":"ref104:EC:MicWal16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1007\/978-3-662-49890-3_31","article-title":"Practical, Predictable Lattice Basis Reduction","volume":"9665","author":"Daniele Micciancio","year":"2016"},{"key":"ref105:EC:ADHKPS19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/978-3-030-17656-3_25","article-title":"The General Sieve Kernel and New Records in Lattice\n  Reduction","volume":"11477","author":"Martin R. Albrecht","year":"2019"},{"key":"ref106:SODA:BDGL16","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1137\/1.9781611974331.ch2","article-title":"New directions in nearest neighbor searching with\n  applications to lattice sieving","author":"Anja Becker","year":"2016"},{"key":"ref107:AC:ChaLoy21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/978-3-030-92068-5_3","article-title":"Lattice Sieving via Quantum Random Walks","volume":"13093","author":"Andr\u00e9 Chailloux","year":"2021"},{"key":"ref108:EC:Ducas18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-3-319-78381-9_5","article-title":"Shortest Vector from Lattice Sieving: A Few Dimensions for\n  Free","volume":"10820","author":"L\u00e9o Ducas","year":"2018"},{"key":"ref109:STOC:MNRS07","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1145\/1250790.1250874","article-title":"Search via quantum walk","author":"Fr\u00e9d\u00e9ric Magniez","year":"2007"},{"key":"ref110:AC:GuoJoh21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-030-92068-5_2","article-title":"Faster Dual Lattice Attacks for Solving LWE with\n  Applications to CRYSTALS","volume":"13093","author":"Qian Guo","year":"2021"},{"key":"ref111:MATZOV22","volume-title":"Report on the Security of LWE: Improved Dual Lattice\n  Attack","author":"MATZOV","year":"2022"},{"key":"ref112:_C:CMHST25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1007\/978-3-032-01855-7_15","article-title":"Assessing the Impact of a Variant of MATZOV's Dual Attack\n  on Kyber","volume":"16000","author":"Kevin Carrier","year":"2025"},{"key":"ref113:CiC:Jaques24","doi-asserted-by":"publisher","first-page":"6","DOI":"10.62056\/ay4fbn2hd","article-title":"Memory adds no cost to lattice sieving for computers in 3 or\n  more spatial dimensions","volume":"1","author":"Samuel Jaques","year":"2024","journal-title":"IACR Communications in Cryptology (CiC)"},{"key":"ref114:C:ABLR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"732","DOI":"10.1007\/978-3-030-84245-1_25","article-title":"Lattice Reduction with Approximate Enumeration Oracles -\n  Practical Algorithms and Concrete Performance","volume":"12826","author":"Martin R. Albrecht","year":"2021"},{"key":"ref115:C:DucPul23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-031-38548-3_2","article-title":"Does the Dual-Sieve Attack on Learning with Errors Even\n  Work?","volume":"14083","author":"L\u00e9o Ducas","year":"2023"},{"key":"ref116:EC:PouShe24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/978-3-031-58754-2_10","article-title":"Provable Dual Attacks on Learning with Errors","volume":"14657","author":"Amaury Pouly","year":"2024"},{"key":"ref117:cryptoeprint:2023\/1850","volume-title":"Accurate Score Prediction for Dual-Sieve Attacks","author":"L\u00e9o Ducas","year":"2023"},{"key":"ref118:EC:JNRV20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-030-45724-2_10","article-title":"Implementing Grover Oracles for Quantum Key Search on AES\n  and LowMC","volume":"12106","author":"Samuel Jaques","year":"2020"},{"key":"ref119:NISTPQC-R1:NTRU-HRSS-KEM17","volume-title":"NTRU-HRSS-KEM","author":"John M. Schanck","year":"2017"},{"key":"ref120:AC:AonNguShe18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/978-3-030-03326-2_14","article-title":"Quantum Lattice Enumeration and Tweaking Discrete Pruning","volume":"11272","author":"Yoshinori Aono","year":"2018"},{"key":"ref121:C:BBTV24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/978-3-031-68391-6_3","article-title":"Quantum Lattice Enumeration in Limited Depth","volume":"14925","author":"Nina Bindel","year":"2024"},{"key":"ref122:AC:AGPS20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/978-3-030-64834-3_20","article-title":"Estimating Quantum Speedups for Lattice Sieves","volume":"12492","author":"Martin R. Albrecht","year":"2020"},{"key":"ref123:cryptoeprint:2024\/1692","volume-title":"On the practicality of quantum sieving algorithms for the\n  shortest vector problem","author":"Joao F. Doriguello","year":"2024"},{"key":"ref124:EC:GruMarPat22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/978-3-031-07082-2_15","article-title":"Anonymous, Robust Post-quantum Public Key Encryption","volume":"13277","author":"Paul Grubbs","year":"2022"},{"key":"ref125:CCS:CreDaxMed24","doi-asserted-by":"publisher","first-page":"1046","DOI":"10.1145\/3658644.3670283","article-title":"Keeping Up with the KEMs: Stronger Security Notions for\n  KEMs and Automated Analysis of KEM-based Protocols","author":"Cas Cremers","year":"2024"},{"key":"ref126:SUPERCOP","volume-title":"SUPERCOP benchmarking results","author":"Daniel J. Bernstein"},{"key":"ref127:C:BFKL93","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/3-540-48329-2_24","article-title":"Cryptographic Primitives Based on Hard Learning Problems","volume":"773","author":"Avrim Blum","year":"1994"},{"key":"ref128:PKC:KawTanXag07","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-540-71677-8_21","article-title":"Multi-bit Cryptosystems Based on Lattice Problems","volume":"4450","author":"Akinori Kawachi","year":"2007"},{"key":"ref129:Hoevelmanns2021","doi-asserted-by":"publisher","DOI":"10.13154\/294-7758","volume-title":"Generic constructions of quantum-resistant cryptosystems","author":"Kathrin H\u00f6velmanns","year":"2021"},{"key":"ref130:RSA:OkaPoi01","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/3-540-45353-9_13","article-title":"REACT: Rapid Enhanced-Security Asymmetric\n  Cryptosystem Transform","volume":"2020","author":"Tatsuaki Okamoto","year":"2001"},{"key":"ref131:_SFCS:BCK96","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1109\/SFCS.1996.548510","article-title":"Pseudorandom functions revisited: the cascade construction\n  and its concrete security","author":"M. Bellare","year":"1996"},{"key":"ref132:TCC:MauRenHol04","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-540-24638-1_2","article-title":"Indifferentiability, Impossibility Results on Reductions,\n  and Applications to the Random Oracle Methodology","volume":"2951","author":"Ueli M. Maurer","year":"2004"},{"key":"ref133:C:CDMP05","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1007\/11535218_26","article-title":"Merkle-Damg\u00e5rd Revisited: How to Construct a Hash\n  Function","volume":"3621","author":"Jean-S\u00e9bastien Coron","year":"2005"},{"key":"ref134:DBLP:conf\/approx\/LiuLM06","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1007\/11830924_41","article-title":"On Bounded Distance Decoding for General Lattices","volume":"4110","author":"Yi-Kai Liu","year":"2006"},{"key":"ref135:DBLP:conf\/coco\/DadushRS14","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1109\/CCC.2014.18","article-title":"On the Closest Vector Problem with a Distance Guarantee","author":"Daniel Dadush","year":"2014"},{"key":"ref136:DBLP:journals\/jacm\/AharonovR05","doi-asserted-by":"publisher","first-page":"749","DOI":"10.1145\/1089023.1089025","article-title":"Lattice problems in NP $\\cap$ coNP","volume":"52","author":"Dorit Aharonov","year":"2005","journal-title":"Journal of the ACM"},{"key":"ref137:C:Peikert10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/978-3-642-14623-7_5","article-title":"An Efficient and Parallel Gaussian Sampler for Lattices","volume":"6223","author":"Chris Peikert","year":"2010"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T20:23:11Z","timestamp":1759782191000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/3\/25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,6]]},"references-count":137,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2025,10,6]]}},"URL":"https:\/\/doi.org\/10.62056\/ayivom2hd","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,6]]},"assertion":[{"value":"2025-07-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-3-46"}}