A Survey of Polynomial Multiplications for Lattice-Based Cryptosystems
IACR Communications in Cryptology · 08.07.2024
DOI: 10.62056/a0ivr-10k ↗Kurz gefasst
Fachartikel in der Zeitschrift IACR Communications in Cryptology, online erschienen am 08.07.2024. Verfasst von Vincent Hwang. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 126 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
We survey various mathematical tools used in software works multiplying polynomials in ℤ 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. 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 ∞ , 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.
Zitieren
APA
Hwang, V. (2024). A Survey of Polynomial Multiplications for Lattice-Based Cryptosystems. IACR Communications in Cryptology. https://doi.org/10.62056/a0ivr-10k
Vancouver
Hwang V. A Survey of Polynomial Multiplications for Lattice-Based Cryptosystems. IACR Communications in Cryptology. 2024. doi:10.62056/a0ivr-10k
BibTeX
@article{Hwang2024,
author = {Hwang, Vincent},
title = {A Survey of Polynomial Multiplications for Lattice-Based Cryptosystems},
journal = {IACR Communications in Cryptology},
year = {2024},
doi = {10.62056/a0ivr-10k}
}
EUVIMED