Multiplying Polynomials without Powerful Multiplication Instructions

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 Z2k perform the best when modular multiplications are expensive and k is not v.... https://ojs.ub.rub.de/index.php/TCHES/article/view/11926

Show object

• Location: Deutsche Nationalbibliothek Frankfurt am Main
• Extent: Online-Ressource
• Language: Englisch

References and Relationships

• Bibliographic citation: Multiplying Polynomials without Powerful Multiplication Instructions ; volume:2025 ; number:1 ; year:2024 ; IACR transactions on cryptographic hardware and embedded systems ; 2025, Heft 1 (2024)

Contributors, Places and Time

• Creator: Hwang, Vincent ; Kim, YoungBeom ; Seo, Seog Chung

Further information

• DOI: 10.46586/tches.v2025.i1.160-202
• URN: urn:nbn:de:101:1-2412181755298.878329727021
• Rights: Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.