Paper 2018/229

Optimizing polynomial convolution for NTRUEncrypt

Wei Dai, William Whyte, and Zhenfei Zhang

Abstract

NTRUEncrypt is one of the most promising candidates for quantum-safe cryptography. In this paper, we focus on the NTRU743 paramter set. We give a report on all known attacks against this parameter set and show that it delivers 256 bits of security against classical attackers and 128 bits of security against quantum attackers. We then present a parameter-dependent optimization using a tailored hierarchy of multipli- cation algorithms as well as the Intel AVX2 instructions, and show that this optimization is constant-time. Our implementation is two to three times faster than the reference implementation of NTRUEncrypt.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Major revision. IEEE Trans. on Computers: Special Section on Cryptographic Engineering in a Post-Quantum World
Keywords
Quantum-safe cryptographyNTRUEncryptsecurity estimationconstant-time implementationAVX2.
Contact author(s)
zzhang @ onboardsecurity com
History
2018-03-01: received
Short URL
https://ia.cr/2018/229
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/229,
      author = {Wei Dai and William Whyte and Zhenfei Zhang},
      title = {Optimizing polynomial convolution for NTRUEncrypt},
      howpublished = {Cryptology ePrint Archive, Paper 2018/229},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/229}},
      url = {https://eprint.iacr.org/2018/229}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.