Welcome to the resource topic for 2025/1791
Title:
High-Speed 16-Radix Polynomial Multiplication on ARM Cortex-M4 with Recursive Karatsuba Layers
Authors: Minjoo Sim, Hyunjun Kim, Minwoo Lee, Hwajeong Seo
Abstract:Polynomial multiplication over \mathbb{F}_2[x] is a fundamental building block in code-based and lattice-based cryptography, particularly on lightweight embedded devices where dedicated carry-less multiply instructions are unavailable. This paper presents a high-speed, constant-time implementation of radix-16 polynomial multiplication on the ARM Cortex-M4, combining zero-padding with recursive Karatsuba layers. Building on the radix-16 decomposition proposed by Chen et al. in TCHES’21, we replace the conventional schoolbook inner multiplier with a multi-level Karatsuba scheme. This optimization reduces cycle counts on the ARM Cortex-M4 while preserving constant-time execution. To further optimize efficiency, the design minimizes packing and unpacking overhead by operating at 128-bit granularity and employs a five-stage pipeline—Decomposition, Padding, Multiplication, Unpadding, and Reassembly—implemented entirely with data-independent shifts, XORs, and masks. Experimental results on the Cortex-M4 show that our optimized ct\_poly32\_mul\_64\_bit implementation achieves up to 31% improvement over the best existing constant-time baseline, demonstrating the efficiency and scalability of recursive Karatsuba for resource-constrained cryptographic applications.
ePrint: https://eprint.iacr.org/2025/1791
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .