NTRU Prime

This is not a comprehensive list. See these papers and "NTRU Prime: round 3" for further references to related literature. Order is reverse chronological for first version; date shown is for most recent version.

[https://eprint.iacr.org/2023/105] 25pp. Georg Land, Adrian Marotzke, Jan Richter-Brockmann, Tim Güneysu. "Gate-Level Masking of Streamlined NTRU Prime Decapsulation in Hardware". Date: 2023.01.28. Reports an arbitrary-order gate-level masked implementation of the decapsulation of sntrup761 for the Xilinx Artix-7 FPGA and 45nm ASIC. The side-channel resistance of the implementation is formally verified using the VERICA tool. Achieves practically feasible results regarding area, randomness demand and latency.

[https://eprint.iacr.org/2021/1444] 37pp. Bo-Yuan Peng, Adrian Marotzke, Ming-Han Tsai, Bo-Yin Yang, Ho-Lin Chen. "Streamlined NTRU Prime on FPGA". Journal of Cryptographic Engineering, Springer 2022. Date: 2021.10.28. Reports a high-speed implementation and a low-area implementration of sntrup761 for the Xilinx Zynq Ultrascale+ and Xilinx Artix-7 FPGA. Achieves the to-date fastest speeds for Streamlined NTRU Prime, with speeds of 5007, 10989 and 64026 cycles for encapsulation, decapsulation, and key generation respectively, while running at 285 MHz on a Xilinx Zynq Ultrascale+. The entire design uses 40060 LUT, 26384 flip-flops, 36.5 Bram and 31 DSP.

[https://eprint.iacr.org/2021/1428] 58pp. Daniel J. Bernstein, Tanja Lange. "Non-randomness of S-unit lattices". Date: 2021.10.23. Shows that S-unit lattices have special analytic features, with much shorter vectors and much higher reduction effectiveness than standard heuristics predict for random lattices. These features are a prerequisite for the success of S-unit attacks.

[https://eprint.iacr.org/2021/1384] 54pp. Olivier Bernard, Andrea Lesavourey, Tuong-Huy Nguyen, Adeline Roux-Langlois. "Log-S-unit lattices using explicit Stickelberger generators to solve Approx Ideal-SVP". Date: 2021.10.15. Further development of S-unit attacks, including experiments in degree 190.

[https://eprint.iacr.org/2021/826] 18pp. Daniel J. Bernstein, Billy Bob Brumley, Ming-Shing Chen, Nicola Tuveri. "OpenSSLNTRU: Faster post-quantum TLS key exchange". USENIX Security 2022, to appear. Date: 2021.10.06. Reports much faster key generation for sntrup (156317 Haswell cycles for sntrup761 key generation, 46914 cycles for encapsulation, and 56214 cycles for decapsulation), and integration into TLS 1.3.

[https://eprint.iacr.org/2021/718] 40pp. Prasanna Ravi, Martianus Frederic Ezerman, Shivam Bhasin, Anupam Chattopadhyay, Sujoy Sinha Roy. " Will you cross the threshold for me? Generic side-channel assisted chosen-ciphertext attacks on NTRU-based KEMs". CHES 2022, to appear. Date: 2021.10.14. Reports electromagnetic analysis of a non-masked implementation of Streamlined NTRU Prime.

[https://eprint.iacr.org/2020/1216] 29pp. Erdem Alkim, Dean Yun-Li Cheng, Chi-Ming Marvin Chung, Hülya Evkan, Leo Wei-Lun Huang, Vincent Hwang, Ching-Lin Trista Li, Ruben Niederhagen, Cheng-Jhih Shih, Julian Wälde, Bo-Yin Yang. "Polynomial multiplication in NTRU Prime: comparison of optimization strategies on Cortex-M4". IACR Transactions on Cryptographic Hardware and Embedded Systems 2021.1 (2021), 217–238. Date: 2020.10.26. Reports an ARM Cortex-M4 microcontroller implementation of sntrup761 using 10777811 cycles for key generation, 694000 cycles for encapsulation, and 571895 cycles for decapsulation.

[https://eprint.iacr.org/2020/1081] 53pp. Olivier Bernard, Adeline Roux-Langlois. "Twisted-PHS: using the product formula to solve Approx-SVP in ideal lattices". Advances in Cryptology—ASIACRYPT 2020—26th international conference on the theory and application of cryptology and information security, Daejeon, South Korea, December 7–11, 2020, proceedings, part II, edited by Shiho Moriai, Huaxiong Wang, Lecture Notes in Computer Science 12492, Springer, 2020. Date: 2020.09.08. Continued development of S-unit attacks.

[https://eprint.iacr.org/2020/1067] 15pp. Adrian Marotzke. "A constant time full hardware implementation of Streamlined NTRU Prime". Smart Card Research and Advanced Applications—19th International Conference, {CARDIS} 2020, virtual event, November 18–19, 2020, revised selected papers, edited by Pierre-Yvan Liardet and Nele Mentens, Lecture Notes in Computer Science 12609, Springer, 2021. Date: 2020.10.01. Reports a Xilinx Zynq Ultrascale+ FPGA implementation of sntrup761 fitting all operations into 1841 slices (with 14 BRAMs and 19 DSPs), reaching a frequency of 271MHz, completing key generation, encapsulation, and decapsulation in 4808, 524, and 958 microseconds respectively.

[https://hdl.handle.net/10993/42985] 17pp. Hao Cheng, Dumitru-Daniel Dinu, Johann Groszschädl, Peter Roenne, Peter Ryan. "A lightweight implementation of NTRU Prime for the post-quantum Internet of Things". Information Security Theory and Practice, 13th IFIP WG 11.2 International Conference, WISTP 2019, Paris, France, December 11–12, 2019, proceedings, edited by Maryline Laurent and Thanassis Giannetsos, Lecture Notes in Computer Science 12024, Springer, 2019. Date: 2019.12. Reports an AVR ATmega1284 microcontroller implementation of sntrup653 using 8160665 cycles for encapsulation and 15602748 cycles for decapsulation.

[https://eprint.iacr.org/2019/100] 29pp. Wei-Lun Huang, Jiun-Peng Chen, Bo-Yin Yang. "Power analysis on NTRU Prime". IACR Transactions on Cryptographic Hardware and Embedded Systems 2020.1 (2020), 123–151. Date: 2019.10.15. Reports power analysis of non-masked implementations of NTRU Prime.

[https://cr.yp.to/papers.html#latticeproofs] 52pp. Daniel J. Bernstein. "Comparing proofs of security for lattice-based encryption". Second PQC Standardization Conference. Date: 2019.07.19. Document ID: 4c6385d1a904c0a83bc9fe9ab8651dcc456ef7db. Surveys and compares what can be proven about the security of proposed KEMs, and identifies errors in several claimed proofs.

[http://nutmic2019.imj-prg.fr/confpapers/MultiCubic.pdf] 46pp. Andrea Lesavourey, Thomas Plantard, Willy Susilo. "On ideal lattices in multicubic fields". Journal of Mathematical Cryptology 14 (2020), 359–392. Date: 2019.06.27. Fast algorithm to find short generators in a family of fields that have small Galois groups (as in the previous multiquadratic and cyclotomic attacks) but not minimum-size Galois groups. This fits the 2014 recommendation to choose a "very large Galois group".

[https://cr.yp.to/papers.html#paretoviz] 16pp. Daniel J. Bernstein. "Visualizing size-security tradeoffs for lattice-based encryption." Second PQC Standardization Conference. Date: 2019.06.03. Document ID: da0f0331c34c346771e3d0d57e083677f54892a0.

[https://gcd.cr.yp.to/papers.html#safegcd] 59pp. Daniel J. Bernstein, Bo-Yin Yang. "Fast constant-time gcd computation and modular inversion". IACR Transactions on Cryptographic Hardware and Embedded Systems 2019.3 (2019), 340–398. Date: 2019.04.13. Document ID: c130922fff0455e43cc7c5ca180787781b409f63.

[https://ntruprime.cr.yp.to/papers.html#divergence] 10pp. (PDF) Daniel J. Bernstein. "Divergence bounds for random fixed-weight vectors obtained by sorting". Document ID: a04dbdd157ddfbd056db4672629d74d27dfbfacf. Date: 2018.04.30. Supersedes: (PDF) 2017.12.12.

[https://ntruprime.cr.yp.to/papers.html#ntruprime-paper] 55pp. (PDF) Daniel J. Bernstein, Chitchanok Chuengsatiansup, Tanja Lange, Christine van Vredendaal. "NTRU Prime: reducing attack surface at low cost". Pages 235–260 in Selected Areas in Cryptography—SAC 2017, 24th international conference, Ottawa, ON, Canada, August 16–18, 2017, revised selected papers, edited by Carlisle Adams, Jan Camenisch. Lecture Notes in Computer Science 10719, Springer, 2018. ISBN 978-3-319-72564-2. Document ID: 99a9debfc18b7d6937a13bac4f943a2b2cd46022. Date: 2017.08.16. Supersedes: (PDF) 2016.05.11. This is the original NTRU Prime paper.

[https://cr.yp.to/papers.html#multiquad] 55pp. Jens Bauch, Daniel J. Bernstein, Henry de Valence, Tanja Lange, Christine van Vredendaal. "Short generators without quantum computers: the case of multiquadratics". Pages 27–59 in Advances in cryptology—EUROCRYPT 2017—36th annual international conference on the theory and applications of cryptographic techniques, Paris, France, April 30–May 4, 2017, proceedings, part I, edited by Jean-Sébastien Coron, Jesper Buus Nielsen. Lecture Notes in Computer Science 10210, Springer, 2017. ISBN 978-3-319-56619-1. Date: 2017.05.01. This paper introduces a much faster subfield-logarithm attack in the case of multiquadratics.

[https://fangsong.info/files/pubs/BS_SODA16.pdf] 10pp. Jean-François Biasse, Fang Song. "Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields". Pages 893–902 in Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 2016. Date: 2016. Fast quantum attack breaking the cyclotomic case of the short-generator problem, and thus breaking the cyclotomic case of various cryptosystems, superseding the 2014.02.13 attack in the cyclotomic case.

[https://docbox.etsi.org/workshop/2014/201410_CRYPTO/S07_Systems_and_Attacks/S07_Groves_Annex.pdf] 9pp. Peter Campbell, Michael Groves, Dan Shepherd. "Soliloquy: a cautionary tale". Date: 2014.10. Claims to introduce a fast quantum attack breaking the cyclotomic case of the short-generator problem. The authors withdrew the quantum part of the attack in 2015, but the cyclotomic part of the attack was critical for subsequent cyclotomic attacks.

[https://blog.cr.yp.to/20140213-ideal.html] Daniel J. Bernstein. "A subfield-logarithm attack against ideal lattices". Date: 2014.02.13. This blog post introduced a "subfield-logarithm attack against ideal lattices", often outperforming other known attacks; said "it's clear that at this point there has not been adequate security evaluation of ideal lattices"; and as a defense recommended the number field Q[x]/(xp−x−1), a prime-degree extension of Q with a large Galois group.

[https://cr.yp.to/talks.html#2013.07.18] Daniel J. Bernstein. "Complexity news: discrete logarithms in multiplicative groups of small-characteristic finite fields—the algorithm of Barbulescu, Gaudry, Joux, Thomé". Date: 2013.07.18. Slide 2 mentioned the possibility of exploiting "subfields" and "small Galois groups" inside "NFS + CVP", and recommended that NTRU switch to "random prime-degree extensions with big Galois groups".

Version: This is version 2023.02.06 of the "Papers" web page.