By Asep Darmawan 
A multi-institutional team of researchers has released a new study detailing an automated, dynamic programming-guided framework for optimizing polynomial multiplication over the finite field $mathbbF_2[x]$ across a wide range of Instruction Set Architectures (ISAs). The paper, designated as Paper 2026/2371 on the Cryptology ePrint Archive, addresses a fundamental bottleneck in both classical and post-quantum cryptographic software by replacing traditional hand-tuning and empirical search methods with a systematic, model-driven schedule-selection strategy.
The research was conducted by a collaborative team consisting of 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. Their findings offer a streamlined alternative for developers seeking to port and optimize carry-less multiplication kernels to emerging hardware landscapes without resorting to exhaustive, platform-specific compilation and benchmarking cycles.
At the heart of the research is the critical role that efficient multiplication over $mathbbF_2[x]$—commonly known as binary polynomial or carry-less multiplication—plays in modern cryptography. This mathematical operation serves as a core primitive for numerous cryptographic schemes, including lightweight algorithms, error-correcting codes, and post-quantum standards. As dominant hardware ecosystems expand beyond traditional x86-64 processors to include ARM and RISC-V architectures in open-source cryptographic libraries like OpenSSL and liboqs, the demand for highly optimized arithmetic kernels has grown increasingly urgent. Developers can no longer rely solely on legacy x86 optimizations; instead, they must retune cryptographic arithmetic across a diverse and fragmented spectrum of ISAs, each possessing distinct hardware characteristics and instruction costs.
To achieve high performance, modern arithmetic libraries routinely rely on recursive divide-and-conquer strategies, most notably Karatsuba- and Toom-Cook-style decomposition rules. These algorithms work by splitting large operands into smaller subproblems, performing recursive operations, and subsequently recombining the resulting products. The sequence of choices made from the top-level multiplication down to the base hardware kernels forms what the authors define as a decomposition schedule.
However, creating optimal schedules presents a significant challenge for software engineers. Hand-tuned schedules often fail to discover superior decompositions when handling larger operand sizes, where the complexity of the recursive tree escalates rapidly. Furthermore, the varying primitive costs associated with different ISAs—such as the availability of specific vector instructions, native XOR speeds, memory traffic latencies, and recursive overhead—vastly complicate the cross-platform retuning process. Traditional approaches have typically relied on measurement-driven per-size empirical searches or tedious manual adjustments, both of which demand substantial engineering effort and time.
To resolve these difficulties, the researchers formulated recursive $mathbbF_2[x]$ multiplication as an optimization problem centered on schedule selection. They demonstrated that the recursive rule space exhibits optimal substructure, a mathematical property that makes it ideally suited for dynamic programming. By constructing a compact ISA profile that comprehensively accounts for base multiplication performance, XOR operations, memory traffic, and recursive overhead, the dynamic programming algorithm can efficiently evaluate and determine the most advantageous decomposition schedule. Once calculated, these optimal schedules can be materialized either as flexible dispatch tables or as fixed-size kernels tailored to specific operational boundaries.
The research team evaluated their dynamic programming framework across a comprehensive suite of hardware platforms, encompassing x86-64, ARM64, RISC-V64, and the microcontroller-class RP2040 processor. Their empirical evaluations revealed that the dynamic programming cost models accurately track runtime performance trends across varying input sizes. When utilizing the full set of recursive rules, the proposed framework achieved consistent geomean speedups ranging from $1.04$ to $1.18$ times over gf2x, a widely recognized software library for polynomial arithmetic over $mathbbF_2[x]$.
Beyond isolated arithmetic benchmarks, the team integrated their optimized multiplication schedules into real-world post-quantum cryptographic primitives, specifically focusing on HQC (Hamming Quasi-Cyclic) and BIKE (Bit Flipping Key Encapsulation), alongside evaluations of Classic McEliece. Tested across the three designated 64-bit platforms, the HQC integrations yielded end-to-end speedups ranging from $1.06$ to $1.21$ times compared to their respective platform baselines. The BIKE integrations demonstrated even more pronounced performance enhancements, achieving end-to-end speedups between $1.01$ and $1.70$ times against baseline implementations.
A notable practical advantage of the proposed dynamic programming approach lies in its computational efficiency during the development and deployment phases. The researchers noted that once platform profiles have been prepared in advance, executing the schedule selection for complex schemes like HQC and BIKE takes between $0.075$ and $0.762$ seconds. This rapid execution completely eliminates the need for candidate compilation and iterative benchmarking during the search phase, which has historically bogged down automated tuning tools.
By replacing heuristic hand-tuning and measurement-driven empirical searches with a rigorous algorithmic model, the study provides a systematic alternative for cryptographic engineers. The framework significantly reduces the human and computational effort required to port, adapt, and retune carry-less multiplication kernels as cryptographic software continues to evolve across an increasingly diverse hardware ecosystem.
Lina Hope 
Sagoh 
Neng Nana