Paper 2024/1649
Multiplying Polynomials without Powerful Multiplication Instructions (Long Paper)
Abstract
We improve the performance of lattice-based cryptosystems Dilithium on Cortex-M3 with expensive multiplications. Our contribution is two-fold: (i) We generalize Barrett multiplication and show that the resulting shape-independent modular multiplication performs comparably to long multiplication on some platforms without special hardware when precomputation is free. We call a modular multiplication “shape-independent” if its correctness and efficiency depend only on the magnitude of moduli and not the shapes of the moduli. This was unknown in the literature even though modular multiplication has been studied for more than 40 years. In the literature, shape-independent modular multiplications often perform several times slower than long multiplications even if we ignore the cost of the precomputation. (ii) We show that polynomial multiplications based on Nussbaumer fast Fourier transform and Toom–Cook over
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Published by the IACR in TCHES 2025
- Keywords
- Lattice-based cryptographyDilithiumSaberBarrett multiplicationMicrocontrollerNussbaumer FFTToom–Cook
- Contact author(s)
-
vincentvbh7 @ gmail com
darania @ kookmin ac kr
scseo @ kookmin ac kr - History
- 2024-10-14: approved
- 2024-10-13: received
- See all versions
- Short URL
- https://ia.cr/2024/1649
- License
-
CC0
BibTeX
@misc{cryptoeprint:2024/1649, author = {Vincent Hwang and YoungBeom Kim and Seog Chung Seo}, title = {Multiplying Polynomials without Powerful Multiplication Instructions (Long Paper)}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1649}, year = {2024}, url = {https://eprint.iacr.org/2024/1649} }