### Faster AVX2 optimized NTT multiplication for Ring-LWE lattice cryptography

Gregor Seiler

##### Abstract

Constant-time polynomial multiplication is one of the most time-consuming operations in many lattice-based cryptographic constructions. For schemes based on the hardness of Ring-LWE in power-of-two cyclotomic fields with completely splitting primes, the AVX2 optimized implementation of the Number-Theoretic Transform (NTT) from the NewHope key-exchange scheme is the state of the art for fast multiplication. It uses floating point vector instructions. We show that by using a modification of the Montgomery reduction algorithm that enables a fast approach with integer instructions, we can improve on the polynomial multiplication speeds of NewHope and Kyber by a factor of $4.2$ and $6.3$ on Skylake, respectively.

Available format(s)
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
lattice cryptographyNTTimplementationAVX
Contact author(s)
gseiler @ inf ethz ch
History
Short URL
https://ia.cr/2018/039

CC BY

BibTeX

@misc{cryptoeprint:2018/039,
author = {Gregor Seiler},
title = {Faster AVX2 optimized NTT multiplication for Ring-LWE lattice cryptography},
howpublished = {Cryptology ePrint Archive, Paper 2018/039},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/039}},
url = {https://eprint.iacr.org/2018/039}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.