SoK: Polynomial Multiplications for Lattice-Based Cryptosystems

ePrint Report: SoK: Polynomial Multiplications for Lattice-Based Cryptosystems

Vincent Hwang

We survey various mathematical tools used in software works multiplying polynomials in $\mathbb{Z}_q [x] / ⟨x^n −αx−β⟩$. In particular, we survey implementation works targeting polynomial multiplications in lattice-based cryptosystems Dilithium, Kyber, NTRU, NTRU Prime, and Saber with instruction set architectures/extensions Armv7-M, Armv7E-M, Armv8-A, and AVX2.


There are three emphases in this paper: (i) modular arithmetic, (ii) homomorphisms, and (iii) vectorization. For modular arithmetic, we survey Montgomery, Barrett, and Plantard multiplications. …

architectures eprint report extensions implementation ntru prime prime report software survey targeting tools