International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

NTTRU: Truly Fast NTRU Using NTT

Authors:
Vadim Lyubashevsky , IBM Research – Zurich
Gregor Seiler , IBM Research – Zurich
Download:
DOI: 10.13154/tches.v2019.i3.180-201
URL: https://tches.iacr.org/index.php/TCHES/article/view/8293
Search ePrint
Search Google
Presentation: Slides
Abstract: We present NTTRU – an IND-CCA2 secure NTRU-based key encapsulation scheme that uses the number theoretic transform (NTT) over the cyclotomic ring Z7681[X]/(X768−X384+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.4K, 6.1K, and 7.9K, 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 as well as the KEMs based on elliptic curve Diffie-Hellman. We additionally 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.
Video from TCHES 2019
BibTeX
@article{tches-2019-29323,
  title={NTTRU: Truly Fast NTRU Using NTT},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2019, Issue 3},
  pages={180-201},
  url={https://tches.iacr.org/index.php/TCHES/article/view/8293},
  doi={10.13154/tches.v2019.i3.180-201},
  author={Vadim Lyubashevsky and Gregor Seiler},
  year=2019
}