EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A Survey of Polynomial Multiplications for Lattice-Based Cryptosystems

Vincent Hwang

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →