Paper 2016/461
NTRU Prime
Daniel J. Bernstein and Chitchanok Chuengsatiansup and 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 proposes NTRU Prime, which tweaks NTRU to use rings without these structures; proposes Streamlined NTRU Prime, which optimizes NTRU Prime from an implementation perspective; finds high-security post-quantum parameters for Streamlined NTRU Prime; and optimizes a constant-time implementation of those parameters. The performance results are surprisingly competitive with the best previous speeds for lattice-based cryptography.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- post-quantum cryptographypublic-key encryptionlattice-based cryptographyideal latticesNTRURing-LWEsecuritySoliloquyKaratsubaToomsoftware implementationvectorization
- 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
-
CC BY