NTRU Prime

Several ideal-lattice-based cryptosystems have been broken by recent attacks that exploit special structures of the rings used in those cryptosystems. The same structures are also used in the leading proposals for post-quantum lattice-based cryptography, including the classic NTRU cryptosystem and typical Ring-LWE-based cryptosystems.

NTRU Prime tweaks NTRU to use rings without these structures. Here are two public-key cryptosystems in the NTRU Prime family, both designed for the standard goal of IND-CCA2 security:

sntrup653, sntrup761, sntrup857, ntrulpr653, ntrulpr761, and ntrulpr857 are Streamlined NTRU Prime and NTRU LPRime with high-security post-quantum parameters. The resulting sizes and Haswell speeds (medians from the official supercop-20200417 benchmarks for hiphop) show that reducing the attack surface has very low cost:

System ciphertext bytes public-key bytes enc cycles dec cycles keygen cycles
sntrup653 897 994 46620 59324 752904
ntrulpr653 1025 897 69400 82732 41756
sntrup761 1039 1158 48780 59120 810148
ntrulpr761 1167 1039 72372 85908 44092
sntrup857 1184 1322 60668 80904 1227380
ntrulpr857 1312 1184 91416 112116 55440

2020.04 news: A new web-browsing demo takes just 166000 Haswell cycles to generate a new sntrup761 public key for each TLS 1.3 session.

sntrup4591761 and ntrulpr4591761 are older versions of sntrup761 and ntrulpr761 using the same mathematical one-way functions:

System ciphertext bytes public-key bytes enc cycles dec cycles keygen cycles
sntrup4591761 1047 1218 44892 94664 1067268
ntrulpr4591761 1175 1047 80592 114340 44196

Contributors (alphabetical order)

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) and project number 645421 (ECRYPT-CSA).

This work was supported by the Netherlands Organisation for Scientific Research (NWO) under grant 639.073.005.

Calculations were carried out on the Saber cluster of the Cryptographic Implementations group at Technische Universiteit Eindhoven.


Version: This is version 2020.04.19 of the "Intro" web page.