NTRU Prime

This is not a comprehensive list. See these papers and "NTRU Prime: round 3" for further references to related literature.

[https://eprint.iacr.org/2021/718] Prasanna Ravi, Martianus Frederic Ezerman, Shivam Bhasin, Anupam Chattopadhyay, Sujoy Sinha Roy. "Generic side-channel assisted chosen-ciphertext attacks on Streamlined NTRU Prime". Date: 2021.05. Reports electromagnetic analysis of a non-masked implementation of Streamlined NTRU Prime.

[https://eprint.iacr.org/2020/1216] 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". CHES 2021, to appear. Date: 2020.10.03. 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/1067] Adrian Marotzke. "A constant time full hardware implementation of Streamlined NTRU Prime". CARDIS 2020, to appear. 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] 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] Wei-Lun Huang, Jiun-Peng Chen, Bo-Yin Yang. "Power analysis on NTRU Prime". IACR Transactions on Cryptographic Hardware and Embedded Systems 2020 (2020), 123–151. Date: 2019.10.15. Reports power analysis of non-masked implementations of NTRU Prime.

[https://cr.yp.to/papers.html#latticeproofs] 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] Andrea Lesavourey, Thomas Plantard, Willy Susilo. "On ideal lattices in multicubic fields". Journal of Mathematical Cryptology, to appear. 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] 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] Daniel J. Bernstein, Bo-Yin Yang. "Fast constant-time gcd computation and modular inversion". IACR Transactions on Cryptographic Hardware and Embedded Systems 2019 (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] 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] 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 2021.05.31 of the "Papers" web page.