Paper 2023/1962

A Survey of Polynomial Multiplications for Lattice-Based Cryptosystems

Vincent Hwang, Max Planck Institute for Security and Privacy
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)
PDF
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
No rights reserved
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.