GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
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 MechanismAuthorsLewis Glabush, Patrick Longa, Michael Naehrig, Chris Peikert, Douglas Stebila, Fernando Virdia
Keywords:
Post-Quantum Cryptography
Lattice Cryptography
Key Exchange
Multi-target security
Implementation
AbstractLarge-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. [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. [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. [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 [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 [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 [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 [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 [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. [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 [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 [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 [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 [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 [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 [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 [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 [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 [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 [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 [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 [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 [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 [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 [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 [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 [Ber22]
Daniel J. Bernstein. Multi-ciphertext security degradation for lattices. Cryptology ePrint Archive, Report 2022/1580. 2022. [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 [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 [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 [BL25]
Daniel J. Bernstein and Tanja Lange. SUPERCOP benchmarking results. Available at https://bench.cr.yp.to/supercop.html. accessed on January 12, 2025. [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 [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 [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 [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 [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 [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 [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 [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. [Che13]
Yuanmi Chen. Lattice reduction and concrete security of fully homomorphic encryption. PhD thesis. Université Paris Diderot, 2013. [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 [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 [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 [CLS16]
Hao Chen, Kristin Lauter, and Katherine E. Stange. Vulnerable Galois RLWE Families and Improved Attacks. Cryptology ePrint Archive, Report 2016/193. 2016. [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 [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 [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 [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 [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 [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. [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 [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 [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 [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 [DP23b]
Léo Ducas and Ludo N. Pulles. Accurate Score Prediction for Dual-Sieve Attacks. Cryptology ePrint Archive, Paper 2023/1850. 2023. [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 [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 [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. [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. [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 [{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. [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 [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 [{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. [{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. [GGH96]
Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Collision-Free Hashing from Lattice Problems. Cryptology ePrint Archive, Report 1996/009. 1996. [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. [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 [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 [Gla24]
Lewis Glabush. Tight Multi-Target Security for Key Encapsulation Mechanisms. https://uwspace.uwaterloo.ca/items/8871c4b1-c2c6-4a42-9485-1466f1772985. 2024. [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 [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 [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 [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 [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 [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 [H{\"o}v21]
Kathrin Hövelmanns. Generic constructions of quantum-resistant cryptosystems. doctoralthesis. Ruhr-Universität Bochum, Universitätsbibliothek, 2021. [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 [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 [{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. [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 [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 [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 [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 [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 [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 [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 [Laa15a]
Thijs Laarhoven. Search problems in cryptography. PhD thesis. Eindhoven University of Technology, 2015. [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 [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. [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 [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 [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 [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 [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 [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 [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 [{MAT}22]
MATZOV. Report on the Security of LWE: Improved Dual Lattice Attack. Technical report, Israel Defense Forces. 2022. [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 [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 [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 [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 [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 [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 [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 [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 [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. [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. [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. [{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. [{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. [{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. [{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. [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 [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 [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 [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 [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 [Pei16a]
Chris Peikert. A Decade of Lattice Cryptography. Foundations and Trends in Theoretical Computer Science, 10(4):283–424, 2016. DOI: 10.1561/0400000074 [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 [Per21]
Ray Perlner. Multi-ciphertext attacks. Private communication. August 2021. [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 [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 [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 [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 [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 [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 [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 [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 [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. [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 [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 [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 [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 [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. [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 [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 How to citeLewis 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. CitationsThere are at least 8 citations. LicenseCopyright 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 citationsWe 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.
|
| 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. |