Information Security and Cryptography Research Group

Faster AVX2 optimized NTT multiplication for Ring-LWE lattice cryptography

Gregor Seiler

Cryptology ePrint Archive, 2018, Report 2018/039.

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.

BibTeX Citation

@misc{Seiler18,
    author       = {Gregor Seiler},
    title        = {Faster AVX2 optimized NTT multiplication for Ring-LWE lattice cryptography},
    series       = {Cryptology ePrint Archive},
    year         = 2018,
    note         = {Report 2018/039},
}

Files and Links