Paper 2016/461

NTRU Prime: reducing attack surface at low cost

Daniel J. Bernstein, Chitchanok Chuengsatiansup, Tanja Lange, and Christine van Vredendaal

Abstract

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. This paper (1) proposes NTRU Prime, which tweaks NTRU to use rings without these structures; (2) proposes Streamlined NTRU Prime, a public-key cryptosystem optimized from an implementation perspective, subject to the standard design goal of IND-CCA2 security; (3) finds high-security post-quantum parameters for Streamlined NTRU Prime; and (4) optimizes a constant-time implementation of those parameters. The resulting sizes and speeds show that reducing the attack surface has very low cost.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision.SAC 2017, to appear
Keywords
post-quantum cryptographypublic-key encryptionlattice-based cryptographyideal latticesNTRURing-LWEsecuritySoliloquyKaratsubasoftware implementationvectorizationfast sorting
Contact author(s)
authorcontact-ntruprime @ box cr yp to
History
2017-08-17: revised
2016-05-13: received
See all versions
Short URL
https://ia.cr/2016/461
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/461,
      author = {Daniel J.  Bernstein and Chitchanok Chuengsatiansup and Tanja Lange and Christine van Vredendaal},
      title = {NTRU Prime: reducing attack surface at low cost},
      howpublished = {Cryptology ePrint Archive, Paper 2016/461},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/461}},
      url = {https://eprint.iacr.org/2016/461}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.