GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Home
  • Papers
  • Submissions
  • Call for papers
  • Frequently asked questions
  • Publication ethics
  • Irregular submissions
  • Conflict of interest
  • Retraction policy
  • Contact
  • Editorial board
  • Admin login
  • Volume 2
  • Issue 3

This view

  • Original page
  • New address

GeezerVison is showing cic.iacr.org — FrodoKEM: A CCA-Secure Learning With Errors Key Encapsulation Mechanism

FrodoKEM: A CCA-Secure Learning With Errors Key Encapsulation Mechanism

Authors

Lewis Glabush, Patrick Longa, Michael Naehrig, Chris Peikert, Douglas Stebila, Fernando Virdia
Lewis Glabush ORCID
EPFL, Lausanne, Switzerland
lewis dot glabush at epfl dot ch
Patrick Longa ORCID
Microsoft Research, Redmond, United States
plonga at microsoft dot com
Michael Naehrig ORCID
Microsoft Research, Redmond, United States
mnaehrig at microsoft dot com
Chris Peikert ORCID
University of Michigan, Ann Arbor, United States
cpeikert at umich dot edu
Douglas Stebila ORCID
University of Waterloo, Waterloo, Canada
dstebila at uwaterloo dot ca
Fernando Virdia ORCID
King's College London, London, United Kingdom
fernando dot virdia at kcl dot ac dot uk
Keywords: Post-Quantum Cryptography Lattice Cryptography Key Exchange Multi-target security Implementation

Abstract

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.

This paper describes FrodoKEM, a family of conservative key-encapsulation mechanisms (KEMs) whose security is based on generic, “unstructured” 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.

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.

References

[ABC+24]
Martin R. Albrecht, Daniel J. Bernstein, Tung Chou, Carlos Cid, Jan Gilcher, Tanja Lange, Varun Maram, Ingo von Maurich, Rafael Misoczki, Ruben Niederhagen, Kenneth G. Paterson, Edoardo Persichetti, Christiane Peters, Peter Schwabe, Nicolas Sendrier, Jakub Szefer, Cen Jung Tjhai, Martin Tomlinson, and Wen Wang. Classic McEliece: conservative code-based cryptography. Specification document available at https://classic.mceliece.org/. 2017–2024.
Google Scholar ePrint
[ABD+23]
Erdem Alkim, Joppe W. Bos, Léo Ducas, Patrick Longa, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Chris Peikert, Ananth Raghunathan, and Douglas Stebila. Annex on FrodoKEM Updates. https://frodokem.org/files/FrodoKEM-annex-20230418.pdf. 2023.
Google Scholar ePrint
[ABD+25]
Erdem Alkim, Joppe W. Bos, Léo Ducas, Patrick Longa, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Chris Peikert, Ananth Raghunathan, and Douglas Stebila. FrodoKEM Preliminary Standardization Proposal (submitted to ISO). https://frodokem.org/files/FrodoKEM_standard_proposal_20250929.pdf. updated Sept. 2025.
Google Scholar ePrint
[ABLR21]
Martin R. Albrecht, Shi Bai, Jianwei Li, and Joe Rowell. Lattice Reduction with Approximate Enumeration Oracles - Practical Algorithms and Concrete Performance. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, Part II, volume 12826 of Lecture Notes in Computer Science, pages 732–759, Virtual Event. August 2021. Springer, Cham. DOI: 10.1007/978-3-030-84245-1_25
Google Scholar ePrint
[ACFP15]
Martin R. Albrecht, Carlos Cid, Jean-Charles Faugère, and Ludovic Perret. Algebraic Algorithms for LWE. ACM Commun. Comput. Algebra, 49(2):62, 2015. https://eprint.iacr.org/2014/1018 DOI: 10.1145/2815111.2815158
Google Scholar ePrint
[ACPS09]
Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai. Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems. In Shai Halevi, editor, Advances in Cryptology – CRYPTO 2009, volume 5677 of Lecture Notes in Computer Science, pages 595–618. August 2009. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-03356-8_35
Google Scholar ePrint
[AD97]
Miklós Ajtai and Cynthia Dwork. A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. In 29th Annual ACM Symposium on Theory of Computing, pages 284–293. May 1997. ACM Press. DOI: 10.1145/258533.258604
Google Scholar ePrint
[ADH+19]
Martin R. Albrecht, Léo Ducas, Gottfried Herold, Elena Kirshanova, Eamonn W. Postlethwaite, and Marc Stevens. The General Sieve Kernel and New Records in Lattice Reduction. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, Part II, volume 11477 of Lecture Notes in Computer Science, pages 717–746. May 2019. Springer, Cham. DOI: 10.1007/978-3-030-17656-3_25
Google Scholar ePrint
[ADPS16]
Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Post-quantum Key Exchange - A New Hope. In Thorsten Holz and Stefan Savage, editors, USENIX Security 2016: 25th USENIX Security Symposium, pages 327–343. August 2016. USENIX Association.
Google Scholar ePrint
[AFFP14]
Martin R. Albrecht, Jean-Charles Faugère, Robert Fitzpatrick, and Ludovic Perret. Lazy Modulus Switching for the BKW Algorithm on LWE. In Hugo Krawczyk, editor, PKC 2014: 17th International Conference on Theory and Practice of Public Key Cryptography, volume 8383 of Lecture Notes in Computer Science, pages 429–445. March 2014. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-54631-0_25
Google Scholar ePrint
[AFG14]
Martin R. Albrecht, Robert Fitzpatrick, and Florian Göpfert. On the Efficacy of Solving LWE by Reduction to Unique-SVP. In Hyang-Sook Lee and Dong-Guk Han, editors, ICISC 13: 16th International Conference on Information Security and Cryptology, volume 8565 of Lecture Notes in Computer Science, pages 293–310. November 2014. Springer, Cham. DOI: 10.1007/978-3-319-12160-4_18
Google Scholar ePrint
[AGPS20]
Martin R. Albrecht, Vlad Gheorghiu, Eamonn W. Postlethwaite, and John M. Schanck. Estimating Quantum Speedups for Lattice Sieves. In Shiho Moriai and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2020, Part II, volume 12492 of Lecture Notes in Computer Science, pages 583–613. December 2020. Springer, Cham. DOI: 10.1007/978-3-030-64834-3_20
Google Scholar ePrint
[AGVW17]
Martin R. Albrecht, Florian Göpfert, Fernando Virdia, and Thomas Wunderer. Revisiting the Expected Cost of Solving uSVP and Applications to LWE. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology – ASIACRYPT 2017, Part I, volume 10624 of Lecture Notes in Computer Science, pages 297–322. December 2017. Springer, Cham. DOI: 10.1007/978-3-319-70694-8_11 https://eprint.iacr.org/2017/815
Google Scholar ePrint
[Ajt96]
Miklós Ajtai. Generating Hard Instances of Lattice Problems (Extended Abstract). In 28th Annual ACM Symposium on Theory of Computing, pages 99–108. May 1996. ACM Press. DOI: 10.1145/237814.237838
Google Scholar ePrint
[Alb17]
Martin R. Albrecht. On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in Cryptology – EUROCRYPT 2017, Part II, volume 10211 of Lecture Notes in Computer Science, pages 103–129. 2017. Springer, Cham. DOI: 10.1007/978-3-319-56614-6_4
Google Scholar ePrint
[ANS18]
Yoshinori Aono, Phong Q. Nguyen, and Yixin Shen. Quantum Lattice Enumeration and Tweaking Discrete Pruning. In Thomas Peyrin and Steven Galbraith, editors, Advances in Cryptology – ASIACRYPT 2018, Part I, volume 11272 of Lecture Notes in Computer Science, pages 405–434. December 2018. Springer, Cham. DOI: 10.1007/978-3-030-03326-2_14
Google Scholar ePrint
[APS15]
Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of Learning with Errors. Journal of Mathematical Cryptology, 9(3):169-203, November 2015. DOI: 10.1515/jmc-2015-0016
Google Scholar ePrint
[AR05]
Dorit Aharonov and Oded Regev. Lattice problems in NP $\cap$ coNP. Journal of the ACM, 52(5):749-765, 2005. Preliminary version in FOCS 2004 DOI: 10.1145/1089023.1089025
Google Scholar ePrint
[AWHT16]
Yoshinori Aono, Yuntao Wang, Takuya Hayashi, and Tsuyoshi Takagi. Improved Progressive BKZ Algorithms and Their Precise Cost Estimation by Sharp Simulator. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology – EUROCRYPT 2016, Part I, volume 9665 of Lecture Notes in Computer Science, pages 789–819. May 2016. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-49890-3_30
Google Scholar ePrint
[BBM00]
Mihir Bellare, Alexandra Boldyreva, and Silvio Micali. Public-Key Encryption in a Multi-user Setting: Security Proofs and Improvements. In Bart Preneel, editor, Advances in Cryptology – EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 259–274. May 2000. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-45539-6_18
Google Scholar ePrint
[BBTV24]
Nina Bindel, Xavier Bonnetain, Marcel Tiepelt, and Fernando Virdia. Quantum Lattice Enumeration in Limited Depth. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology – CRYPTO 2024, Part VI, volume 14925 of Lecture Notes in Computer Science, pages 72–106. August 2024. Springer, Cham. DOI: 10.1007/978-3-031-68391-6_3
Google Scholar ePrint
[BCD+16]
Joppe W. Bos, Craig Costello, Léo Ducas, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Ananth Raghunathan, and Douglas Stebila. Frodo: Take off the Ring! Practical, Quantum-Secure Key Exchange from LWE. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016: 23rd Conference on Computer and Communications Security, pages 1006–1018. October 2016. ACM Press. DOI: 10.1145/2976749.2978425
Google Scholar ePrint
[BCK96]
M. Bellare, R. Canetti, and H. Krawczyk. Pseudorandom functions revisited: the cascade construction and its concrete security. In Proceedings of 37th Conference on Foundations of Computer Science, pages 514-523. 1996. DOI: 10.1109/SFCS.1996.548510
Google Scholar ePrint
[BCNS15]
Joppe W. Bos, Craig Costello, Michael Naehrig, and Douglas Stebila. Post-Quantum Key Exchange for the TLS Protocol from the Ring Learning with Errors Problem. In 2015 IEEE Symposium on Security and Privacy, pages 553–570. May 2015. IEEE Computer Society Press. DOI: 10.1109/SP.2015.40
Google Scholar ePrint
[BDGL16]
Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. New directions in nearest neighbor searching with applications to lattice sieving. In Robert Krauthgamer, editor, 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 10–24. January 2016. ACM-SIAM. DOI: 10.1137/1.9781611974331.ch2
Google Scholar ePrint
[BDK+18]
Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS — Kyber: A CCA-Secure Module-Lattice-Based KEM. In 2018 IEEE European Symposium on Security and Privacy (EuroS&P), pages 353-367. April 2018. DOI: 10.1109/EuroSP.2018.00032
Google Scholar ePrint
[Ber22]
Daniel J. Bernstein. Multi-ciphertext security degradation for lattices. Cryptology ePrint Archive, Report 2022/1580. 2022.
Google Scholar ePrint
[BFKL94]
Avrim Blum, Merrick L. Furst, Michael J. Kearns, and Richard J. Lipton. Cryptographic Primitives Based on Hard Learning Problems. In Douglas R. Stinson, editor, Advances in Cryptology – CRYPTO'93, volume 773 of Lecture Notes in Computer Science, pages 278–291. August 1994. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-48329-2_24
Google Scholar ePrint
[BGG+14]
Dan Boneh, Craig Gentry, Sergey Gorbunov, Shai Halevi, Valeria Nikolaenko, Gil Segev, Vinod Vaikuntanathan, and Dhinakaran Vinayagamurthy. Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits. In Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology – EUROCRYPT 2014, volume 8441 of Lecture Notes in Computer Science, pages 533–556. May 2014. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-55220-5_30
Google Scholar ePrint
[BGV12]
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. In Shafi Goldwasser, editor, ITCS 2012: 3rd Innovations in Theoretical Computer Science, pages 309–325. January 2012. Association for Computing Machinery. DOI: 10.1145/2090236.2090262
Google Scholar ePrint
[BL25]
Daniel J. Bernstein and Tanja Lange. SUPERCOP benchmarking results. Available at https://bench.cr.yp.to/supercop.html. accessed on January 12, 2025.
Google Scholar ePrint
[BLP+13]
Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé. Classical hardness of learning with errors. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, 45th Annual ACM Symposium on Theory of Computing, pages 575–584. June 2013. ACM Press. DOI: 10.1145/2488608.2488680
Google Scholar ePrint
[BNvdP17]
Joppe W. Bos, Michael Naehrig, and Joop van de Pol. Sieving for Shortest Vectors in Ideal Lattices: a Practical Perspective. Int. J.  of Applied Cryptography, 3(4):313–329, January 2017. DOI: 10.1504/IJACT.2017.10010312
Google Scholar ePrint
[BV11]
Zvika Brakerski and Vinod Vaikuntanathan. Efficient Fully Homomorphic Encryption from (Standard) LWE. In Rafail Ostrovsky, editor, 52nd Annual Symposium on Foundations of Computer Science, pages 97–106. October 2011. IEEE Computer Society Press. DOI: 10.1109/FOCS.2011.12
Google Scholar ePrint
[CDM24]
Cas Cremers, Alexander Dax, and Niklas Medinger. Keeping Up with the KEMs: Stronger Security Notions for KEMs and Automated Analysis of KEM-based Protocols. In Bo Luo, Xiaojing Liao, Jun Xu, Engin Kirda, and David Lie, editors, ACM CCS 2024: 31st Conference on Computer and Communications Security, pages 1046–1060. October 2024. ACM Press. DOI: 10.1145/3658644.3670283
Google Scholar ePrint
[CDMP05]
Jean-Sébastien Coron, Yevgeniy Dodis, Cécile Malinaud, and Prashant Puniya. Merkle-Damgård Revisited: How to Construct a Hash Function. In Victor Shoup, editor, Advances in Cryptology – CRYPTO 2005, volume 3621 of Lecture Notes in Computer Science, pages 430–448. August 2005. Springer, Berlin, Heidelberg. DOI: 10.1007/11535218_26
Google Scholar ePrint
[CDPR16]
Ronald Cramer, Léo Ducas, Chris Peikert, and Oded Regev. Recovering Short Generators of Principal Ideals in Cyclotomic Rings. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology – EUROCRYPT 2016, Part II, volume 9666 of Lecture Notes in Computer Science, pages 559–585. May 2016. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-49896-5_20
Google Scholar ePrint
[CDW17]
Ronald Cramer, Léo Ducas, and Benjamin Wesolowski. Short Stickelberger Class Relations and Application to Ideal-SVP. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in Cryptology – EUROCRYPT 2017, Part I, volume 10210 of Lecture Notes in Computer Science, pages 324–348. 2017. Springer, Cham. DOI: 10.1007/978-3-319-56620-7_12
Google Scholar ePrint
[CGS14]
Peter Campbell, Michael Groves, and Dan Shepherd. Soliloquy: a Cautionary Tale. http://docbox.etsi.org/Workshop/2014/201410_CRYPTO/S07_Systems_and_Attacks/S07_Groves_Annex.pdf. ETSI 2nd Quantum-Safe Crypto Workshop. 2014.
Google Scholar ePrint
[Che13]
Yuanmi Chen. Lattice reduction and concrete security of fully homomorphic encryption. PhD thesis. Université Paris Diderot, 2013.
Google Scholar ePrint
[CHKP12]
David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert. Bonsai Trees, or How to Delegate a Lattice Basis. Journal of Cryptology, 25(4):601–639, October 2012. DOI: 10.1007/s00145-011-9105-2
Google Scholar ePrint
[CIV16]
Wouter Castryck, Ilia Iliashenko, and Frederik Vercauteren. Provably Weak Instances of Ring-LWE Revisited. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology – EUROCRYPT 2016, Part I, volume 9665 of Lecture Notes in Computer Science, pages 147–167. May 2016. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-49890-3_6
Google Scholar ePrint
[CL21]
André Chailloux and Johanna Loyer. Lattice Sieving via Quantum Random Walks. In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2021, Part IV, volume 13093 of Lecture Notes in Computer Science, pages 63–91. December 2021. Springer, Cham. DOI: 10.1007/978-3-030-92068-5_3
Google Scholar ePrint
[CLS16]
Hao Chen, Kristin Lauter, and Katherine E. Stange. Vulnerable Galois RLWE Families and Improved Attacks. Cryptology ePrint Archive, Report 2016/193. 2016.
Google Scholar ePrint
[CLS17]
Hao Chen, Kristin Lauter, and Katherine E. Stange. Attacks on the Search RLWE Problem with Small Errors. SIAM J. Appl. Algebra Geom., 1(1):665–682, 2017. https://eprint.iacr.org/2015/971 DOI: 10.1137/16M1096566
Google Scholar ePrint
[CMHST25]
Kevin Carrier, Charles Meyer-Hilfiger, Yixin Shen, and Jean-Pierre Tillich. Assessing the Impact of a Variant of MATZOV's Dual Attack on Kyber. In Yael Tauman Kalai and Seny F. Kamara, editors, Advances in Cryptology - CRYPTO 2025 - 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2025, Proceedings, Part I, volume 16000 of Lecture Notes in Computer Science, pages 444–476. 2025. Springer. DOI: 10.1007/978-3-032-01855-7_15
Google Scholar ePrint
[CN97]
Jin-yi Cai and Ajay Nerurkar. An Improved Worst-Case to Average-Case Connection for Lattice Problems. In 38th Annual Symposium on Foundations of Computer Science, pages 468–477. October 1997. IEEE Computer Society Press. DOI: 10.1109/SFCS.1997.646135
Google Scholar ePrint
[CN11]
Yuanmi Chen and Phong Q. Nguyen. BKZ 2.0: Better Lattice Security Estimates. In Dong Hoon Lee and Xiaoyun Wang, editors, Advances in Cryptology – ASIACRYPT 2011, volume 7073 of Lecture Notes in Computer Science, pages 1–20. December 2011. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-25385-0_1
Google Scholar ePrint
[DDGR20]
Dana Dachman-Soled, Léo Ducas, Huijing Gong, and Mélissa Rossi. LWE with Side Information: Attacks and Concrete Security Estimation. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology - CRYPTO 2020, volume 12171 of Lecture Notes in Computer Science, pages 329–358. 2020. Springer. DOI: 10.1007/978-3-030-56880-1_12 https://eprint.iacr.org/2020/292.pdf
Google Scholar ePrint
[DGLM24]
Joao F. Doriguello, George Giapitzakis, Alessandro Luongo, and Aditya Morolia. On the practicality of quantum sieving algorithms for the shortest vector problem. https://eprint.iacr.org/2024/1692. Cryptology ePrint Archive, Paper 2024/1692. 2024.
Google Scholar ePrint
[DH76]
Whitfield Diffie and Martin E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory, 22(6):644–654, 1976. DOI: 10.1109/TIT.1976.1055638
Google Scholar ePrint
[DHK+21]
Julien Duman, Kathrin Hövelmanns, Eike Kiltz, Vadim Lyubashevsky, and Gregor Seiler. Faster Lattice-Based KEMs via a Generic Fujisaki-Okamoto Transform Using Prefix Hashing. In Giovanni Vigna and Elaine Shi, editors, ACM CCS 2021: 28th Conference on Computer and Communications Security, pages 2722–2737. November 2021. ACM Press. DOI: 10.1145/3460120.3484819
Google Scholar ePrint
[DM13]
Nico Döttling and Jörn Müller-Quade. Lossy Codes and a New Variant of the Learning-With-Errors Problem. In Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology – EUROCRYPT 2013, volume 7881 of Lecture Notes in Computer Science, pages 18–34. May 2013. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-38348-9_2
Google Scholar ePrint
[DP23a]
Léo Ducas and Ludo N. Pulles. Does the Dual-Sieve Attack on Learning with Errors Even Work?. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology – CRYPTO 2023, Part III, volume 14083 of Lecture Notes in Computer Science, pages 37–69. August 2023. Springer, Cham. DOI: 10.1007/978-3-031-38548-3_2
Google Scholar ePrint
[DP23b]
Léo Ducas and Ludo N. Pulles. Accurate Score Prediction for Dual-Sieve Attacks. Cryptology ePrint Archive, Paper 2023/1850. 2023.
Google Scholar ePrint
[DRS14]
Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. On the Closest Vector Problem with a Distance Guarantee. In IEEE Conference on Computational Complexity, pages 98-109. 2014. DOI: 10.1109/CCC.2014.18
Google Scholar ePrint
[Duc18]
Léo Ducas. Shortest Vector from Lattice Sieving: A Few Dimensions for Free. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2018, Part I, volume 10820 of Lecture Notes in Computer Science, pages 125–145. 2018. Springer, Cham. DOI: 10.1007/978-3-319-78381-9_5
Google Scholar ePrint
[Dwo15]
Morris J. Dworkin. SHA-3 standard: Permutation-based hash and extendable-output functions. Technical report number 202, National Institute of Standards and Technology. August 2015.
Google Scholar ePrint
[DXL12]
Jintai Ding, Xiang Xie, and Xiaodong Lin. A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem. Cryptology ePrint Archive, Report 2012/688. 2012.
Google Scholar ePrint
[ELOS15]
Yara Elias, Kristin E. Lauter, Ekin Ozman, and Katherine E. Stange. Provably Weak Instances of Ring-LWE. In Rosario Gennaro and Matthew J. B. Robshaw, editors, Advances in Cryptology – CRYPTO 2015, Part I, volume 9215 of Lecture Notes in Computer Science, pages 63–92. August 2015. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-47989-6_4
Google Scholar ePrint
[{Fed}24]
Federal Office for Information Security (BSI). Cryptographic Mechanisms: Recommendations and Key Lengths, BSI TR-02102-1, Version: 2024-1. Available at https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/TechGuidelines/TG02102/BSI-TR-02102-1.pdf?__blob=publicationFile&v=7. 2024.
Google Scholar ePrint
[FO99a]
Eiichiro Fujisaki and Tatsuaki Okamoto. How to Enhance the Security of Public-Key Encryption at Minimum Cost. In Hideki Imai and Yuliang Zheng, editors, PKC'99: 2nd International Workshop on Theory and Practice in Public Key Cryptography, volume 1560 of Lecture Notes in Computer Science, pages 53–68. March 1999. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-49162-7_5
Google Scholar ePrint
[FO99b]
Eiichiro Fujisaki and Tatsuaki Okamoto. Secure Integration of Asymmetric and Symmetric Encryption Schemes. In Michael J. Wiener, editor, Advances in Cryptology – CRYPTO'99, volume 1666 of Lecture Notes in Computer Science, pages 537–554. August 1999. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-48405-1_34
Google Scholar ePrint
[{Gen}22]
General Intelligence and Security Service (AIVD). Prepare for the threat of quantum computers. Available at https://english.aivd.nl/publications/publications/2022/01/18/prepare-for-the-threat-of-quantumcomputers. 2022.
Google Scholar ePrint
[{Gen}24]
General Intelligence, Security Service (AIVD), Centrum Wiskunde & Informatica (CWI), and Netherlands Organization for Applied Scientific Research (TNO). The PQC Migration Handbook: Guidelines for Migrating to Post-Quantum Cryptography (second edition). Available at https://publications.tno.nl/publication/34643386/fXcPVHsX/TNO-2024-pqc-en.pdf. 2024.
Google Scholar ePrint
[GGH96]
Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Collision-Free Hashing from Lattice Problems. Cryptology ePrint Archive, Report 1996/009. 1996.
Google Scholar ePrint
[GHS25]
Lewis Glabush, Kathrin Hövelmanns, and Douglas Stebila. Tight Multi-challenge Security Reductions for Key Encapsulation Mechanisms. Cryptology ePrint Archive, Paper 2025/343. 2025.
Google Scholar ePrint
[GJ21]
Qian Guo and Thomas Johansson. Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS. In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2021, Part IV, volume 13093 of Lecture Notes in Computer Science, pages 33–62. December 2021. Springer, Cham. DOI: 10.1007/978-3-030-92068-5_2
Google Scholar ePrint
[GJN20]
Qian Guo, Thomas Johansson, and Alexander Nilsson. A Key-Recovery Timing Attack on Post-quantum Primitives Using the Fujisaki-Okamoto Transformation and Its Application on FrodoKEM. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology – CRYPTO 2020, Part II, volume 12171 of Lecture Notes in Computer Science, pages 359–386. August 2020. Springer, Cham. DOI: 10.1007/978-3-030-56880-1_13
Google Scholar ePrint
[Gla24]
Lewis Glabush. Tight Multi-Target Security for Key Encapsulation Mechanisms. https://uwspace.uwaterloo.ca/items/8871c4b1-c2c6-4a42-9485-1466f1772985. 2024.
Google Scholar ePrint
[GMP22]
Paul Grubbs, Varun Maram, and Kenneth G. Paterson. Anonymous, Robust Post-quantum Public Key Encryption. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology – EUROCRYPT 2022, Part III, volume 13277 of Lecture Notes in Computer Science, pages 402–432. 2022. Springer, Cham. DOI: 10.1007/978-3-031-07082-2_15
Google Scholar ePrint
[GPV08]
Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Richard E. Ladner and Cynthia Dwork, editors, 40th Annual ACM Symposium on Theory of Computing, pages 197–206. May 2008. ACM Press. DOI: 10.1145/1374376.1374407
Google Scholar ePrint
[GSW13]
Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology – CRYPTO 2013, Part I, volume 8042 of Lecture Notes in Computer Science, pages 75–92. August 2013. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-40041-4_5
Google Scholar ePrint
[GVW15]
Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. Predicate Encryption for Circuits from LWE. In Rosario Gennaro and Matthew J. B. Robshaw, editors, Advances in Cryptology – CRYPTO 2015, Part II, volume 9216 of Lecture Notes in Computer Science, pages 503–523. August 2015. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-48000-7_25
Google Scholar ePrint
[HHK17]
Dennis Hofheinz, Kathrin Hövelmanns, and Eike Kiltz. A Modular Analysis of the Fujisaki-Okamoto Transformation. In Yael Kalai and Leonid Reyzin, editors, TCC 2017: 15th Theory of Cryptography Conference, Part I, volume 10677 of Lecture Notes in Computer Science, pages 341–371. November 2017. Springer, Cham. DOI: 10.1007/978-3-319-70500-2_12
Google Scholar ePrint
[HHM22]
Kathrin Hövelmanns, Andreas Hülsing, and Christian Majenz. Failing Gracefully: Decryption Failures and the Fujisaki-Okamoto Transform. In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology – ASIACRYPT 2022, Part IV, volume 13794 of Lecture Notes in Computer Science, pages 414–443. December 2022. Springer, Cham. DOI: 10.1007/978-3-031-22972-5_15
Google Scholar ePrint
[H{\"o}v21]
Kathrin Hövelmanns. Generic constructions of quantum-resistant cryptosystems. doctoralthesis. Ruhr-Universität Bochum, Universitätsbibliothek, 2021.
Google Scholar ePrint
[HPS98]
Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NTRU: A Ring-Based Public Key Cryptosystem. In Third Algorithmic Number Theory Symposium (ANTS), volume 1423 of Lecture Notes in Computer Science, pages 267–288. June 1998. Springer. DOI: 10.1007/BFB0054868
Google Scholar ePrint
[IKMT14]
Tsukasa Ishiguro, Shinsaku Kiyomoto, Yutaka Miyake, and Tsuyoshi Takagi. Parallel Gauss Sieve Algorithm: Solving the SVP Challenge over a 128-Dimensional Ideal Lattice. In Hugo Krawczyk, editor, PKC 2014: 17th International Conference on Theory and Practice of Public Key Cryptography, volume 8383 of Lecture Notes in Computer Science, pages 411–428. March 2014. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-54631-0_24
Google Scholar ePrint
[{Int}24]
International Organization for Standardization (ISO). ISO/IEC 18033-2:2006/DAmd 2, Information technology – Security techniques – Encryption algorithms – Part 2: Asymmetric ciphers. Available at https://www.iso.org/standard/86890.html. 2024.
Google Scholar ePrint
[Jaq24]
Samuel Jaques. Memory adds no cost to lattice sieving for computers in 3 or more spatial dimensions. IACR Communications in Cryptology (CiC), 1(3):6, 2024. DOI: 10.62056/ay4fbn2hd
Google Scholar ePrint
[JNRV20]
Samuel Jaques, Michael Naehrig, Martin Roetteler, and Fernando Virdia. Implementing Grover Oracles for Quantum Key Search on AES and LowMC. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, Part II, volume 12106 of Lecture Notes in Computer Science, pages 280–310. May 2020. Springer, Cham. DOI: 10.1007/978-3-030-45724-2_10
Google Scholar ePrint
[JZC+18]
Haodong Jiang, Zhenfeng Zhang, Long Chen, Hong Wang, and Zhi Ma. IND-CCA-Secure Key Encapsulation Mechanism in the Quantum Random Oracle Model, Revisited. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, Part III, volume 10993 of Lecture Notes in Computer Science, pages 96–125. August 2018. Springer, Cham. DOI: 10.1007/978-3-319-96878-0_4
Google Scholar ePrint
[KBF+15]
J. Kelly, R. Barends, A. G. Fowler, A. Megrant, E. Jeffrey, T. C. White, D. Sank, J. Y. Mutus, B. Campbell, Yu Chen, Z. Chen, B. Chiaro, A. Dunsworth, I.-C. Hoi, C. Neill, P. J. J. O’Malley, C. Quintana, P. Roushan, A. Vainsencher, J. Wenner, A. N. Cleland, and John M. Martinis. State preservation by repetitive error detection in a superconducting quantum circuit. Nature, 519(7541):66–69, March 2015. DOI: 10.1038/nature14270
Google Scholar ePrint
[KF15]
Paul Kirchner and Pierre-Alain Fouque. An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices. In Rosario Gennaro and Matthew J. B. Robshaw, editors, Advances in Cryptology – CRYPTO 2015, Part I, volume 9215 of Lecture Notes in Computer Science, pages 43–62. August 2015. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-47989-6_3
Google Scholar ePrint
[KF17]
Paul Kirchner and Pierre-Alain Fouque. Revisiting Lattice Attacks on Overstretched NTRU Parameters. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in Cryptology – EUROCRYPT 2017, Part I, volume 10210 of Lecture Notes in Computer Science, pages 3–26. 2017. Springer, Cham. DOI: 10.1007/978-3-319-56620-7_1
Google Scholar ePrint
[KTX07]
Akinori Kawachi, Keisuke Tanaka, and Keita Xagawa. Multi-bit Cryptosystems Based on Lattice Problems. In Tatsuaki Okamoto and Xiaoyun Wang, editors, PKC 2007: 10th International Conference on Theory and Practice of Public Key Cryptography, volume 4450 of Lecture Notes in Computer Science, pages 315–329. April 2007. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-71677-8_21
Google Scholar ePrint
[Laa15a]
Thijs Laarhoven. Search problems in cryptography. PhD thesis. Eindhoven University of Technology, 2015.
Google Scholar ePrint
[Laa15b]
Thijs Laarhoven. Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing. In Rosario Gennaro and Matthew J. B. Robshaw, editors, Advances in Cryptology – CRYPTO 2015, Part I, volume 9215 of Lecture Notes in Computer Science, pages 3–22. August 2015. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-47989-6_1
Google Scholar ePrint
[LLL82]
Arjen K. Lenstra, Hendrik W. Lenstra Jr., and László Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515-534, December 1982.
Google Scholar ePrint
[LLM06]
Yi-Kai Liu, Vadim Lyubashevsky, and Daniele Micciancio. On Bounded Distance Decoding for General Lattices. In Josep Díaz, Klaus Jansen, José D. P. Rolim, and Uri Zwick, editors, APPROX-RANDOM, volume 4110 of Lecture Notes in Computer Science, pages 450–461. 2006. Springer. DOI: 10.1007/11830924_41
Google Scholar ePrint
[LN13]
Mingjie Liu and Phong Q. Nguyen. Solving BDD by Enumeration: An Update. In Ed Dawson, editor, Topics in Cryptology – CT-RSA 2013, volume 7779 of Lecture Notes in Computer Science, pages 293–309. 2013. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-36095-4_19
Google Scholar ePrint
[LN24]
Jianwei Li and Phong Q. Nguyen. A Complete Analysis of the BKZ Lattice Reduction Algorithm. J. Cryptol., 38(1), December 2024. DOI: 10.1007/s00145-024-09527-0
Google Scholar ePrint
[LP11]
Richard Lindner and Chris Peikert. Better Key Sizes (and Attacks) for LWE-Based Encryption. In Aggelos Kiayias, editor, Topics in Cryptology – CT-RSA 2011, volume 6558 of Lecture Notes in Computer Science, pages 319–339. February 2011. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-19074-2_21
Google Scholar ePrint
[LPR13]
Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On Ideal Lattices and Learning with Errors Over Rings. Journal of the ACM, 60(6):43:1–43:35, November 2013. Preliminary version in Eurocrypt 2010 DOI: 10.1145/2535925
Google Scholar ePrint
[LS15]
Adeline Langlois and Damien Stehlé. Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, 75(3):565–599, 2015. DOI: 10.1007/S10623-014-9938-4
Google Scholar ePrint
[LSS14]
Adeline Langlois, Damien Stehlé, and Ron Steinfeld. GGHLite: More Efficient Multilinear Maps from Ideal Lattices. In Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology – EUROCRYPT 2014, volume 8441 of Lecture Notes in Computer Science, pages 239–256. May 2014. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-55220-5_14
Google Scholar ePrint
[{MAT}22]
MATZOV. Report on the Security of LWE: Improved Dual Lattice Attack. Technical report, Israel Defense Forces. 2022.
Google Scholar ePrint
[Mic02]
Daniele Micciancio. Improved cryptographic hash functions with worst-case/average-case connection. In 34th Annual ACM Symposium on Theory of Computing, pages 609–618. May 2002. ACM Press. DOI: 10.1145/509907.509995
Google Scholar ePrint
[Mic10]
Daniele Micciancio. Cryptographic Functions from Worst-Case Complexity Assumptions. In Phong Q. Nguyen and Brigitte Vallée, editors, The LLL Algorithm - Survey and Applications, pages 427–452. Springer 2010. DOI: 10.1007/978-3-642-02295-1_13
Google Scholar ePrint
[MNRS07]
Frédéric Magniez, Ashwin Nayak, Jeremie Roland, and Miklos Santha. Search via quantum walk. In David S. Johnson and Uriel Feige, editors, 39th Annual ACM Symposium on Theory of Computing, pages 575–584. June 2007. ACM Press. DOI: 10.1145/1250790.1250874
Google Scholar ePrint
[MP13]
Daniele Micciancio and Chris Peikert. Hardness of SIS and LWE with Small Parameters. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology – CRYPTO 2013, Part I, volume 8042 of Lecture Notes in Computer Science, pages 21–39. August 2013. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-40041-4_2
Google Scholar ePrint
[MR07]
Daniele Micciancio and Oded Regev. Worst-Case to Average-Case Reductions Based on Gaussian Measures.. SIAM J. Comput., 37(1):267-302, 2007. Preliminary version in FOCS 2004 DOI: 10.1137/S0097539705447360
Google Scholar ePrint
[MR09]
Daniele Micciancio and Oded Regev. Lattice-based Cryptography. In Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen, editors, Post Quantum Cryptography, pages 147-191. Springer 2009. DOI: 10.1007/978-3-540-88702-7_5
Google Scholar ePrint
[MRH04]
Ueli M. Maurer, Renato Renner, and Clemens Holenstein. Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology. In Moni Naor, editor, TCC 2004: 1st Theory of Cryptography Conference, volume 2951 of Lecture Notes in Computer Science, pages 21–39. February 2004. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-24638-1_2
Google Scholar ePrint
[MW16]
Daniele Micciancio and Michael Walter. Practical, Predictable Lattice Basis Reduction. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology – EUROCRYPT 2016, Part I, volume 9665 of Lecture Notes in Computer Science, pages 820–849. May 2016. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-49890-3_31
Google Scholar ePrint
[NAB+17]
Michael Naehrig, Erdem Alkim, Joppe Bos, Léo Ducas, Karen Easterbrook, Brian LaMacchia, Patrick Longa, Ilya Mironov, Valeria Nikolaenko, Christopher Peikert, Ananth Raghunathan, and Douglas Stebila. FrodoKEM. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-1-submissions. 2017.
Google Scholar ePrint
[NAB+19]
Michael Naehrig, Erdem Alkim, Joppe Bos, Léo Ducas, Karen Easterbrook, Brian LaMacchia, Patrick Longa, Ilya Mironov, Valeria Nikolaenko, Christopher Peikert, Ananth Raghunathan, and Douglas Stebila. FrodoKEM. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-2-submissions. 2019.
Google Scholar ePrint
[NAB+20]
Michael Naehrig, Erdem Alkim, Joppe Bos, Léo Ducas, Karen Easterbrook, Brian LaMacchia, Patrick Longa, Ilya Mironov, Valeria Nikolaenko, Christopher Peikert, Ananth Raghunathan, and Douglas Stebila. FrodoKEM. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions. 2020.
Google Scholar ePrint
[{Nat}17]
National Institute of Standards and Technology (NIST). Post-Quantum Cryptography Standardization Project. Call for proposals: https://frodokem.org/files/FrodoKEM-standard_proposal-20230314.pdf. 2017.
Google Scholar ePrint
[{Nat}23]
National Cybersecurity Agency of France (ANSSI). ANSSI views on the Post-Quantum Cryptography transition (2023 follow up). Available at https://cyber.gouv.fr/en/publications/follow-position-paper-post-quantum-cryptography. 2023.
Google Scholar ePrint
[{Nat}24a]
National Institute of Standards and Technology (NIST). Module-Lattice-Based Digital Signature Standard (FIPS 204). Available at https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.pdf. 2024.
Google Scholar ePrint
[{Nat}24b]
National Institute of Standards and Technology (NIST). Module-Lattice-Based Key-Encapsulation Mechanism Standard (FIPS 203). Available at https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.pdf. 2024.
Google Scholar ePrint
[OP01]
Tatsuaki Okamoto and David Pointcheval. REACT: Rapid Enhanced-Security Asymmetric Cryptosystem Transform. In David Naccache, editor, Topics in Cryptology – CT-RSA 2001, volume 2020 of Lecture Notes in Computer Science, pages 159–175. April 2001. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-45353-9_13
Google Scholar ePrint
[Pei09a]
Chris Peikert. Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In Michael Mitzenmacher, editor, 41st Annual ACM Symposium on Theory of Computing, pages 333–342. 2009. ACM Press. DOI: 10.1145/1536414.1536461
Google Scholar ePrint
[Pei09b]
Chris Peikert. Some Recent Progress in Lattice-Based Cryptography. In Omer Reingold, editor, TCC 2009: 6th Theory of Cryptography Conference, volume 5444 of Lecture Notes in Computer Science, pages 72. March 2009. Springer, Berlin, Heidelberg. Invited talk. Slides available at http://web.eecs.umich.edu/ cpeikert/pubs/slides-tcc09.pdf
Google Scholar ePrint
[Pei10]
Chris Peikert. An Efficient and Parallel Gaussian Sampler for Lattices. In Tal Rabin, editor, Advances in Cryptology – CRYPTO 2010, volume 6223 of Lecture Notes in Computer Science, pages 80–97. August 2010. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-14623-7_5
Google Scholar ePrint
[Pei14]
Chris Peikert. Lattice Cryptography for the Internet. In Michele Mosca, editor, Post-Quantum Cryptography - 6th International Workshop, PQCrypto 2014, pages 197–219. October 2014. Springer, Cham. DOI: 10.1007/978-3-319-11659-4_12
Google Scholar ePrint
[Pei16a]
Chris Peikert. A Decade of Lattice Cryptography. Foundations and Trends in Theoretical Computer Science, 10(4):283–424, 2016. DOI: 10.1561/0400000074
Google Scholar ePrint
[Pei16b]
Chris Peikert. How (Not) to Instantiate Ring-LWE. In Vassilis Zikas and Roberto De Prisco, editors, SCN 16: 10th International Conference on Security in Communication Networks, volume 9841 of Lecture Notes in Computer Science, pages 411–430. 2016. Springer, Cham. DOI: 10.1007/978-3-319-44618-9_22
Google Scholar ePrint
[Per21]
Ray Perlner. Multi-ciphertext attacks. Private communication. August 2021.
Google Scholar ePrint
[PHS19]
Alice Pellet-Mary, Guillaume Hanrot, and Damien Stehlé. Approx-SVP in Ideal Lattices with Pre-processing. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, Part II, volume 11477 of Lecture Notes in Computer Science, pages 685–716. May 2019. Springer, Cham. DOI: 10.1007/978-3-030-17656-3_24
Google Scholar ePrint
[PRS17]
Chris Peikert, Oded Regev, and Noah Stephens-Davidowitz. Pseudorandomness of ring-LWE for any ring and modulus. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, 49th Annual ACM Symposium on Theory of Computing, pages 461–473. June 2017. ACM Press. DOI: 10.1145/3055399.3055489
Google Scholar ePrint
[PS24]
Amaury Pouly and Yixin Shen. Provable Dual Attacks on Learning with Errors. In Marc Joye and Gregor Leander, editors, Advances in Cryptology – EUROCRYPT 2024, Part VII, volume 14657 of Lecture Notes in Computer Science, pages 256–285. May 2024. Springer, Cham. DOI: 10.1007/978-3-031-58754-2_10
Google Scholar ePrint
[PVW08]
Chris Peikert, Vinod Vaikuntanathan, and Brent Waters. A Framework for Efficient and Composable Oblivious Transfer. In David Wagner, editor, Advances in Cryptology – CRYPTO 2008, volume 5157 of Lecture Notes in Computer Science, pages 554–571. August 2008. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-85174-5_31
Google Scholar ePrint
[PW08]
Chris Peikert and Brent Waters. Lossy trapdoor functions and their applications. In Richard E. Ladner and Cynthia Dwork, editors, 40th Annual ACM Symposium on Theory of Computing, pages 187–196. May 2008. ACM Press. DOI: 10.1145/1374376.1374406
Google Scholar ePrint
[Reg04]
Oded Regev. New lattice-based cryptographic constructions. J. ACM, 51(6):899–942, 2004. Preliminary version in STOC 2003 DOI: 10.1145/1039488.1039490
Google Scholar ePrint
[Reg09]
Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 56(6):34, 2009. Preliminary version in STOC 2005 DOI: 10.1145/1568318.1568324
Google Scholar ePrint
[Reg10]
Oded Regev. The Learning with Errors Problem (Invited Survey). In IEEE Conference on Computational Complexity, pages 191-204. 2010. DOI: 10.1109/CCC.2010.26
Google Scholar ePrint
[SAB+20]
Peter Schwabe, Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Gregor Seiler, and Damien Stehlé. CRYSTALS-KYBER. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions. 2020.
Google Scholar ePrint
[Sch87]
Claus-Peter Schnorr. A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms. Theoretical Computer Science, 53:201-224, 1987. DOI: 10.1016/0304-3975(87)90064-8
Google Scholar ePrint
[Sch13]
Michael Schneider. Sieving for Shortest Vectors in Ideal Lattices. In Amr Youssef, Abderrahmane Nitaj, and Aboul Ella Hassanien, editors, AFRICACRYPT 13: 6th International Conference on Cryptology in Africa, volume 7918 of Lecture Notes in Computer Science, pages 375–391. June 2013. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-38553-7_22
Google Scholar ePrint
[SE91]
Claus-Peter Schnorr and M Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. In Lothar Budach, editor, FCT, volume 529 of Lecture Notes in Computer Science, pages 68–85. 1991. Springer. DOI: 10.1007/3-540-54458-5_51
Google Scholar ePrint
[SE94]
Claus-Peter Schnorr and Martin Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical Programming, 66:181–199, 1994. DOI: 10.1007/BF01581144
Google Scholar ePrint
[SHRS17]
John M. Schanck, Andreas Hulsing, Joost Rijneveld, and Peter Schwabe. NTRU-HRSS-KEM. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-1-submissions. 2017.
Google Scholar ePrint
[TU16]
Ehsan Ebrahimi Targhi and Dominique Unruh. Post-Quantum Security of the Fujisaki-Okamoto and OAEP Transforms. In Martin Hirt and Adam D. Smith, editors, TCC 2016-B: 14th Theory of Cryptography Conference, Part II, volume 9986 of Lecture Notes in Computer Science, pages 192–216. 2016. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-53644-5_8
Google Scholar ePrint
[YN05]
J. Q. You and Franco Nori. Superconducting Circuits and Quantum Information. Physics Today, 58(11):42–47, November 2005. DOI: 10.1063/1.2155757
Google Scholar ePrint

PDFPDF Open access

DOI: https://doi.org/10.62056/ayivom2hd
History
Submitted: 2025-07-08
Accepted: 2025-09-02
Published: 2025-10-06
Crossmark logo
How to cite

Lewis Glabush, Patrick Longa, Michael Naehrig, Chris Peikert, Douglas Stebila, and Fernando Virdia, FrodoKEM: A CCA-Secure Learning With Errors Key Encapsulation Mechanism. IACR Communications in Cryptology, vol. 2, no. 3, Oct 06, 2025, doi: 10.62056/ayivom2hd.

Citations

There are at least 8 citations.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

How to cite this

@article{10.62056/ayivom2hd,
         author={Lewis Glabush and Patrick Longa and Michael Naehrig and Chris Peikert and Douglas Stebila and Fernando Virdia},
         title={Frodo{KEM}: A {CCA}-Secure Learning With Errors Key Encapsulation Mechanism},
         volume={2},
         number={3},
         year={2025},
         date={2025-10-06},
         issn={3006-5496},
         doi={10.62056/ayivom2hd},
         journal={{IACR} Communications in Cryptology},
         publisher={International Association for Cryptologic Research}
}
TY  - JOUR
AU  - Lewis Glabush
AU  - Patrick Longa
AU  - Michael Naehrig
AU  - Chris Peikert
AU  - Douglas Stebila
AU  - Fernando Virdia
PY  - 2025
TI  - FrodoKEM: A CCA-Secure Learning With Errors Key Encapsulation Mechanism
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 2
IS  - 3
DO  - 10.62056/ayivom2hd
UR  - https://doi.org/10.62056/ayivom2hd
AB  - <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.</p><p>  This paper describes FrodoKEM, a family of conservative key-encapsulation mechanisms (KEMs) whose security is based on generic, “unstructured” 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.</p><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. </p>
ER  -
Lewis Glabush, Patrick Longa, Michael Naehrig, Chris Peikert, Douglas Stebila, and Fernando Virdia, FrodoKEM: A CCA-Secure Learning With Errors Key Encapsulation Mechanism. IACR Communications in Cryptology, vol. 2, no. 3, Oct 06, 2025, doi: 10.62056/ayivom2hd.

Known citations

We do not crawl the web, so we are only able to identify citations from papers that are registered with a DOI in crossref.org and the publisher reports their citations to crossref, and crossref can identify a DOI from the reference. That includes (most) articles from Springer and many from ACM, but it excludes citations from USENIX because they don't issue DOIs. It also excludes citations from arxiv and eprint. You may find more citations in Google Scholar.

  1. Baosheng Huang, Guoqing Zhou, Lin Wang, Yue Cao, Sen Hou, Jingting Xu and Yu Li. Disjoint Simulatability and Security Reduction of a Class of Lattice-Based Schemes. 2026 8th International Conference on Electronics and Communication, Network and Computer Technology (ECNCT) (2026), p. 533 DOI: 10.1109/ECNCT70535.2026.11661428
  2. Sayan Das, Aarav Varshney, Prasanna Ravi and Anupam Chattopadhyay. Quantum Safe Networks: A Case Study on Securing QKD Interfaces Using PQC. IEEE Transactions on Network Science and Engineering (2026) Vol 13, p. 8795 DOI: 10.1109/TNSE.2026.3676261
  3. Gökçe Düzyol, Muhammed Said Gündoğan and Atakan Arslan. Can FrodoKEM Run in a Millisecond? FPGA Says Yes!. Proceedings of the 15th International Workshop on Hardware and Architectural Support for Security and Privacy (2026), p. 83 DOI: 10.1145/3857307.3857317
  4. Jingfeng Wang and Yingying Yao. An Efficient Post-Quantum Cross-Domain Authentication Scheme for 6G V2X Using Accelerated FrodoKEM. 2026 11th International Conference on Computer and Communication Systems (ICCCS) (2026), p. 833 DOI: 10.1109/ICCCS69761.2026.11613267
  5. Lukas Köder, Nils Lohmiller, Nick Leist, Bastian Buck and Tobias Heer. WPA3-Personal Meets Post-Quantum Cryptography: Early Experimental Performance Observations. 2026 IEEE Symposium on Computers and Communications (ISCC) (2026), p. 1 DOI: 10.1109/ISCC70364.2026.11740071
  6. Thi-Bac Do and Khanh-Linh Dinh. Simultaneous Integration of Kyber and Dilithium on Embedded Microcontrollers: Towards Quantum-Resistant IoT Systems. Engineering, Technology & Applied Science Research (2026) Vol 16, Issue 2, p. 33589 DOI: 10.48084/etasr.17148
  7. Simon Abelard, Juan Antonio Vieira Giestinhas, Delaram Kahrobaei, Ludovic Perret, Timothy Spiller and Christoph Striecks. Assessment of provably secure hybrid authenticated key exchange for dual-use applications. EPJ Quantum Technology (2026) Vol 13, Issue 1 DOI: 10.1140/epjqt/s40507-026-00532-9
  8. Jian Lu, Zhuang Xu, Shunxian Gao, Bin Wei, Jianyang Li, Meng Li, Linpeng Wang, Juan Ren and Yun Wang. A Novel Masking Scheme with Low Additional Overhead for LWE-Based PQC Family. Topics in Cryptology – CT-RSAC 2026 Lecture Notes in Computer Science Volume 16496 (2026), p. 155 DOI: 10.1007/978-3-032-22931-1_6
You are visitor 01402605 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.