NTTRU: Truly Fast NTRU Using NTT

Vadim Lyubashevsky; Gregor Seiler

Paper 2019/040

NTTRU: Truly Fast NTRU Using NTT

Vadim Lyubashevsky and Gregor Seiler

Abstract

We present NTTRU -- an IND-CCA2 secure NTRU-based key encapsulation scheme that uses the number theoretic transform (NTT) over the cyclotomic ring $Z_{7681} [X] / (X^{768} - X^{384} + 1)$ and produces public keys and ciphertexts of approximately $1.25$ KB at the $128$ -bit security level. The number of cycles on a Skylake CPU of our constant-time AVX2 implementation of the scheme for key generation, encapsulation and decapsulation is approximately $6.4$ K, $6.1$ K, and $7.9$ K, which is more than 30X, 5X, and 8X faster than these respective procedures in the NTRU schemes that were submitted to the NIST post-quantum standardization process. These running times are also, by a large margin, smaller than those for all the other schemes in the NIST process. We also give a simple transformation that allows one to provably deal with small decryption errors in OW-CPA encryption schemes (such as NTRU) when using them to construct an IND-CCA2 key encapsulation.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published by the IACR in TCHES 2019
Keywords: NTRU Lattice Cryptography AVX2 NTT
Contact author(s): vadim lyubash @ gmail com
gseiler @ inf ethz ch
History: 2020-02-09: last of 4 revisions; 2019-01-17: received; See all versions
Short URL: https://ia.cr/2019/040
License: CC BY

BibTeX

@misc{cryptoeprint:2019/040,
      author = {Vadim Lyubashevsky and Gregor Seiler},
      title = {{NTTRU}: Truly Fast {NTRU} Using {NTT}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/040},
      year = {2019},
      url = {https://eprint.iacr.org/2019/040}
}