Lattice-based cryptography has attracted attention for its flexibility, and small lattice-based encryption systems have attracted attention for their performance. However, lattice-based cryptography also has an extremely complicated attack picture with many different attack tools, many losses of security, and many security claims that turned out to be wrong.
The standard response to these failures is to discard the systems shown to be broken, while continuing to claim confidence in the remaining systems. However, there is no reason to believe that the new attacks published in the last few years are the end of the story. A better approach is to proactively modify cryptographic designs to reduce the attack surface.
The NTRU Prime project recommends switching from "cyclotomics" to "large Galois groups" to reduce the attack surface in lattice-based cryptography. After this recommendation was published, Gentry's original (STOC 2009) fully homomorphic encryption system was shown to be broken in quantum polynomial time for cyclotomics.
Within the NTRU Prime project, Streamlined NTRU Prime is a small lattice-based KEM aiming for the standard goal of IND-CCA2 security. There are other proposals of small lattice-based KEMs aiming for IND-CCA2, but Streamlined NTRU Prime is systematically designed to minimize the complexity of a thorough security review. It turns out to be possible at low cost to eliminate many of the complications of lattice security review, while still meeting the constraint of being a small lattice-based KEM. Concretely, this design strategy implies
- using large Galois groups instead of cyclotomics;
- using "inert" moduli instead of "split" moduli;
- eliminating decryption failures;
- using "rounding" instead of "noise";
- using "ternary" distributions; and
- using "rings" instead of "modules".
The success of the proactive Streamlined NTRU Prime design strategy is illustrated by subsequently published decryption-failure attacks violating the security claims of LAC and Round5.
Streamlined NTRU Prime uses "Quotient NTRU", which avoids some security questions raised by "Product NTRU" (aka "LPR", aka "the Ring-LWE cryptosystem"). However, Product NTRU also avoids some security questions raised by Quotient NTRU, and the literature has not yet established which of these is better for the security reviewer. The NTRU Prime project therefore also offers NTRU LPRime (pronounced "ell-prime"), which uses Product NTRU.
Contributors (alphabetical order)
- Daniel J. Bernstein, University of Illinois at Chicago, USA, and Ruhr University Bochum, Germany, and Academia Sinica, Taiwan
- Billy Bob Brumley, Tampere University, Finland
- Ming-Shing Chen, Academia Sinica, Taiwan
- Chitchanok Chuengsatiansup, The University of Adelaide, Australia
- Tanja Lange, Technische Universiteit Eindhoven, Netherlands, and Academia Sinica, Taiwan
- Adrian Marotzke, Hamburg University of Technology, Germany and NXP Semiconductors, Germany
- Bo-Yuan Peng, National Taiwan University and Academia Sinica, Taiwan
- Nicola Tuveri, Tampere University, Finland
- Christine van Vredendaal, Technische Universiteit Eindhoven, Netherlands
- Bo-Yin Yang, Academia Sinica, Taiwan
Acknowledgments
This work was supported by the Cisco University Research Program under the "Post-quantum networking" project.
This work was supported by the U.S. National Science Foundation under grant 1314919. "Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation."
This work was supported by the Commission of the European Communities through the Horizon 2020 program under project number 645622 (PQCRYPTO), project number 645421 (ECRYPT-CSA), and project number 804476 (SCARE).
This work was supported by the Federal Ministry of Education and Research (BMBF) of the Federal Republic of Germany (grant 16KIS0658K, SysKit_HW).
This work was labelled by the EUREKA cluster PENTA and funded by German authorities under grant agreement PENTA-2018e-17004-SunRISE.
This work was supported by the Netherlands Organisation for Scientific Research (NWO) under grant 639.073.005.
Taiwanese authors were supported by Taiwan Ministry of Science and Technology Grants 108-2221-E-001-008 and 109-2221-E-001-009-MY3, Sinica Investigator Award AS-IA-109-M01, Executive Yuan Data Safety and Talent Cultivation Project (AS-KPQ-109-DSTCP).
Calculations were carried out on the Saber cluster of the Cryptographic Implementations group at Technische Universiteit Eindhoven.
Some of this work was performed while Chuengsatiansup was affiliated with Technische Universiteit Eindhoven (Netherlands) and École Normale Supérieure de Lyon (France).
Version: This is version 2022.03.03 of the "Intro" web page.
