Paper 2023/1962
A Survey of Polynomial Multiplications for Lattice-Based Cryptosystems
Abstract
We survey various mathematical tools used in software works multiplying polynomials in \[ \frac{\mathbb{Z}_q[x]}{\left\langle {x^n - \alpha x - \beta} \right\rangle}. \] 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. For homomorphisms, we survey (a) various homomorphisms such as Cooley--Tukey FFT, Good--Thomas FFT, Bruun's FFT, Rader's FFT, Karatsuba, and Toom--Cook; (b) various algebraic techniques for adjoining nice properties to the coefficient rings, including localization, Schönhage's FFT, Nussbaumer's FFT, and coefficient ring switching; and (c) various algebraic techniques related to the polynomial moduli, including twisting, composed multiplication, evaluation at $\infty$, truncation, incomplete transformation, striding, and Toeplitz matrix-vector product. For vectorization, we survey the relations between homomorphisms and vector arithmetic. We then go through several case studies: We compare the implementations of modular multiplications used in Dilithium and Kyber, explain how the matrix-to-vector structure was exploited in Saber, and review the design choices of transformations for NTRU and NTRU Prime with vectorization. Finally, we outline several interesting implementation projects.
Note: More pointers to the sections. The table of contents is also added.
Metadata
- Available format(s)
- Category
- Implementation
- Publication info
- A minor revision of an IACR publication in CIC 2024
- Keywords
- Lattice-based cryptographyPolynomial multiplicationModular arithmeticHomomorphismVectorization
- Contact author(s)
- vincentvbh7 @ gmail com
- History
- 2024-06-19: last of 6 revisions
- 2023-12-26: received
- See all versions
- Short URL
- https://ia.cr/2023/1962
- License
-
CC0
BibTeX
@misc{cryptoeprint:2023/1962, author = {Vincent Hwang}, title = {A Survey of Polynomial Multiplications for Lattice-Based Cryptosystems}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1962}, year = {2023}, url = {https://eprint.iacr.org/2023/1962} }