Researchers Introduce Dynamic Programming Approach to Optimize Cryptographic Multiplication Across Diverse Hardware Architectures

A team of security researchers and computer scientists has released a new study detailing an automated method for optimizing polynomial multiplication over finite fields, a fundamental operation in both classical and post-quantum cryptography. The paper, titled "DP-Guided Schedule Selection for $mathbbF_2[x]$ Multiplication across ISAs," was authored by Junyu Zhou, Xiao Lan, and Hao Ren from Sichuan University; Jing Wang from the Huazhong University of Science and Technology; Weiran Liu; and Si Gao from the Institute of Software at the Chinese Academy of Sciences.

The research addresses a persistent challenge in cryptographic software engineering: achieving peak arithmetic performance across a rapidly fragmenting hardware landscape. As architectures such as ARM and RISC-V gain prominence in open-source cryptographic libraries like OpenSSL and liboqs, developers face the arduous task of retuning core arithmetic kernels for a widening array of Instruction Set Architectures, or ISAs.

At the heart of many cryptographic systems lies efficient multiplication over the finite field extension $mathbbF_2[x]$, often referred to as carry-less multiplication. This operation serves as a core primitive required by numerous encryption schemes, particularly those designed to resist quantum computing threats. To maximize performance, high-performance arithmetic libraries rely heavily on recursive decomposition strategies, famously exemplified by Karatsuba and Toom-style multiplication rules.

These strategies work by recursively splitting large operands into smaller subproblems, performing fundamental calculations, and subsequently recombining the resulting products. The sequence of choices made from the top-level multiplication down to the base hardware kernels forms what researchers call a decomposition schedule. Finding the optimal schedule for a given operand size is critical for minimizing instruction counts, memory overhead, and latency.

However, the authors point out that traditional approaches to this problem suffer from significant limitations. Hand-tuned schedules, while common, frequently fail to identify superior decompositions when dealing with large operand sizes. Furthermore, because different hardware architectures impose vastly different costs on primitive operations such as base multiplications, exclusive-or (XOR) gates, memory traffic, and recursive overhead, cross-platform retuning has traditionally required tedious, measurement-driven empirical searches for every single input size.

To overcome these hurdles, the research team formulated recursive $mathbbF_2[x]$ multiplication as an advanced schedule-selection problem. They discovered that the recursive rule space exhibits optimal substructure, a mathematical property that makes it exceptionally well-suited for dynamic programming, commonly known as DP. By leveraging dynamic programming over a compact ISA profile, the system can systematically evaluate the costs associated with base operations, memory movements, and structural overhead without needing to compile and benchmark countless candidate implementations during the search phase.

The resulting optimized schedules can be materialized efficiently as dispatch tables or fixed-size kernels tailored directly to the underlying hardware. To validate their theoretical framework, the researchers conducted extensive evaluations across four distinct computing platforms: x86-64, ARM64, RISC-V64, and the resource-constrained RP2040 microcontroller.

The empirical results demonstrate 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 scheme achieved geometric mean speedups ranging from $1.04$ to $1.18$ times over gf2x, a widely used software library for polynomial arithmetic in $mathbbF_2[x]$.

Beyond isolated microbenchmarks, the team integrated their optimized multiplication schedules into larger, post-quantum cryptographic schemes, specifically focusing on HQC and BIKE. On the three tested 64-bit platforms, the integration yielded end-to-end speedups ranging from $1.06$ to $1.21$ times for HQC, and between $1.01$ and $1.70$ times for BIKE, when compared against the respective platform baselines. The researchers also evaluated the performance impact on Classic McEliece, further demonstrating the broad applicability of their methodology.

A notable practical advantage of the new technique lies in its efficiency during the optimization phase itself. With pre-prepared hardware profiles already in place, the schedule selection process for complex algorithms like HQC and BIKE takes a mere $0.075$ to $0.762$ seconds. This eliminates the traditional bottleneck of having to compile and benchmark numerous candidate algorithms in real time during the search process.

Ultimately, the research provides a systematic, automated alternative to manual code tuning and exhaustive empirical measurement. By streamlining the process of porting and retuning carry-less multiplication kernels, the DP-guided approach significantly lowers the engineering effort required to maintain high-performance, quantum-resistant cryptography across diverse and evolving hardware platforms.