A team of researchers has released a new study detailing a systematic method for optimizing polynomial multiplication over $mathbbF_2[x]$, a fundamental mathematical operation critical to both classical and post-quantum cryptography. Titled "DP-Guided Schedule Selection for $mathbbF_2[x]$ Multiplication across ISAs," Paper 2026/2371 was authored by Junyu Zhou, Xiao Lan, and Hao Ren from Sichuan University; Jing Wang from the Huazhong University of Science and Technology; independent researcher Weiran Liu; and Si Gao from the Institute of Software at the Chinese Academy of Sciences. The work addresses the growing complexity of tuning cryptographic software across a widening array of hardware platforms, offering a computational alternative to traditional hand-tuning and empirical benchmarking.
At the heart of modern cryptographic software libraries—such as OpenSSL and liboqs—efficient polynomial multiplication serves as a foundational building block. As the computing landscape diversifies beyond traditional x86 architectures, open-source libraries are increasingly deployed across ARM and RISC-V platforms. This shift requires arithmetic kernels to be carefully retuned for a wide variety of Instruction Set Architectures, each with distinct performance characteristics, register constraints, and instruction latencies.
To achieve high performance, modern arithmetic libraries recursively apply advanced decomposition rules, notably those derived from Karatsuba and Toom-Cook algorithms. These techniques function by splitting large operands into smaller subproblems, computing the products independently, and then recombining the results through a series of algebraic operations, primarily exclusive-or (XOR) gates. The sequence of these recursive choices, stretching from the top-level multiplication down to the foundational base kernels, forms what researchers call a decomposition schedule.
However, designing optimal schedules for varying operand sizes presents a significant engineering challenge. Hand-tuned schedules frequently fail to identify the most efficient decomposition strategies when dealing with very large operand sizes. Furthermore, because different ISAs impose varying costs on primitive operations—such as base multiplication, memory traffic, XOR execution, and recursive overhead—retuning software across multiple platforms manually demands substantial development effort and continuous optimization.
To overcome these hurdles, the research team formulated recursive $mathbbF_2[x]$ multiplication as a formal schedule-selection problem. Their analysis revealed that the recursive rule space possesses a crucial mathematical property known as optimal substructure. This property allows the researchers to apply dynamic programming (DP) techniques over a compact ISA profile. Rather than relying on trial-and-error measurements for every conceivable operand size, the dynamic programming model accounts for the specific costs associated with base multiplication, memory bandwidth, XOR operations, and recursive function call overheads on a given hardware target.
The resulting schedules generated by the dynamic programming framework are materialized directly as dispatch tables or fixed-size, highly optimized kernels. To validate their approach, the researchers conducted extensive evaluations across a diverse set of hardware platforms, encompassing x86-64, ARM64, RISC-V64, and the microcontroller-class RP2040 architecture. Their findings demonstrate that the dynamic programming cost estimates closely track runtime performance trends across varying input sizes. Across the tested environments, the full rule set achieved geometric mean speedups ranging from $1.04$ to $1.18$ times over gf2x, a widely used software library for arithmetic over GF(2)[x].
The practical impact of this work extends deeply into post-quantum cryptography, where standardized post-quantum schemes often rely heavily on binary polynomial arithmetic. The researchers integrated their optimized multiplication schedules into implementations of HQC and BIKE, two prominent code-based post-quantum cryptography candidates, across the three tested 64-bit platforms.
For HQC integrations, the dynamic programming approach yielded end-to-end speedups ranging from $1.06$ to $1.21$ times compared to standard platform baselines. The performance gains were even more pronounced in BIKE integrations, which achieved end-to-end speedups between $1.01$ and $1.70$ times over their respective platform baselines. In addition to HQC and BIKE, the researchers also evaluated the performance implications for Classic McEliece, demonstrating the broad applicability of the schedule-selection framework to multiple post-quantum cryptographic schemes.
A notable advantage of the proposed methodology lies in its computational efficiency during the development and deployment phases. With pre-prepared hardware profiles in place, the schedule-selection process for HQC and BIKE requires a mere 0.75 to 0.762 seconds. This streamlined workflow entirely eliminates the need for exhaustive candidate compilation and empirical benchmarking during the search phase, saving both time and computational resources.
Ultimately, the research provides a systematic, automated alternative to traditional hand-tuning and measurement-driven empirical searches that rely on testing every individual input size. By shifting from ad-hoc optimization to a dynamic programming framework, the scheme substantially reduces the engineering effort required to port, optimize, and retune carry-less multiplication kernels across emerging and established instruction set architectures alike.
