Paper 2023/604
Pushing the Limit of Vectorized Polynomial Multiplication for NTRU Prime
Abstract
We conduct a systematic examination of vector arithmetic for polynomial multiplications in software. Vector instruction sets and extensions typically specify a fixed number of registers, each holding a power-of-two number of bits, and support a wide variety of vector arithmetic on registers. Programmers then try to align mathematical computations with the vector arithmetic supported by the designated instruction set or extension. We delve into the intricacies of this process for polynomial multiplications. In particular, we introduce “vectorization- friendliness” and “permutation-friendliness”, and review “Toeplitz matrix- vector product” to systematically identify suitable mappings from homo- morphisms to vectorized implementations.
To illustrate how the formalization works, we detail the vectorization of polynomial multiplication in
Note: Update the paper to the final version.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Published elsewhere. Australasian Conference on Information Security and Privacy 2024
- Keywords
- VectorizationPolynomial MultiplicationFast Fourier TransformNTRU Prime
- Contact author(s)
- vincentvbh7 @ gmail com
- History
- 2024-04-18: last of 8 revisions
- 2023-04-27: received
- See all versions
- Short URL
- https://ia.cr/2023/604
- License
-
CC0
BibTeX
@misc{cryptoeprint:2023/604, author = {Vincent Hwang}, title = {Pushing the Limit of Vectorized Polynomial Multiplication for {NTRU} Prime}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/604}, year = {2023}, url = {https://eprint.iacr.org/2023/604} }