Optimizing Polynomial Multiplication and Fixed-Weight Sampling for HQC on ARM Cortex-M4

arXiv:2608.18145 · cs.AR, cs.CR · Submitted 2026-08-10 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: Today's paper: "Optimizing Polynomial Multiplication and Fixed-Weight Sampling for HQC on ARM Cortex-M4".

Elias: This research presents significant optimizations for implementing Hamming QuasiCyclic (HQC) on resource-constrained ARM Cortex-M4 processors, addressing performance bottlenecks in polynomial multiplication and fixed-weight sampling.

Nadia: First, who's behind it and why it matters.

Title and authors: Nadia: Let's look at the title and authors of "Optimizing Polynomial Multiplication and Fixed-Weight Sampling for HQC on ARM Cortex-M4." It’s clear they aren't just tinkering with the math; they are specifically targeting performance on a particular piece of hardware, the ARM Cortex-M4.

Elias: The authors are Jang, Shin, Kim, Hong, and Kwon from Korea University and other institutions in South Korea. Their background suggests a strong foundation in both number theory and low-level systems programming required for embedded cryptography.

Priya: It’s interesting that the focus is so narrow on the hardware; I wonder if these optimizations are transferable to more generalized AI inference chips or if they're really tied to this specific architecture.

Nadia: That’s a valid question, Priya; we need to see how much generality there is in their work. They're suggesting a way to make HQC efficient on this specific chip, which hints at techniques applicable elsewhere if the underlying logic is sound.

Elias: The paper points out that polynomial multiplication and sampling are what largely determine the overall performance of HQC on the Cortex-M4, which is a key point because it tells us exactly where to focus our efforts.

The paper's summary: Nadia: So, summarizing the core of "Optimizing Polynomial Multiplication and Fixed-Weight Sampling for HQC on ARM Cortex-M4," the authors are presenting an optimized implementation of Hamming QuasiCyclic on the ARM Cortex-M4 by focusing on three main areas: polynomial multiplication, support expansion in fixed-weight sampling, and proposing an optional caching strategy.

Elias: That summary highlights the three main pillars they built their optimization around: speeding up the multiplication using FAFFT methods, making fixed-weight sampling more efficient via ARM predicated instructions, and adding a caching layer to reuse expensive computations.

Priya: The idea of precomputing the public transforms and hashes once for repeated sessions is fascinating; from a privacy perspective, it means less work on every single message exchange, which could translate to better throughput without compromising the security of the key itself.

Nadia: Right, and that caching strategy is significant because it directly addresses the cost incurred during encapsulation and decapsulation steps. We've seen how much time those parts of the process take in prior implementations when you reuse a public key repeatedly.

Elias: They quantify this effect quite clearly, showing that with this optional caching technique, they can reduce encapsulation and decapsulation times by up to thirty-two point seven percent and eighteen point nine percent compared to the non-cached case when the same public key is reused.

The paper's improvements: Nadia: Moving into the specific improvements suggested by this paper, we see they are making several technical adjustments to get that speedup. For polynomial multiplication, they integrate truncated basis conversion and share the forward transform of one operand into the FAFFT-CRT implementation.

Elias: That points toward minimizing overhead in those transforms; specifically, finding a "thirty-four percent sparser FAFFT modulus that lowers the CRT reconstruction cost" for HQC-one which significantly reduces its Hamming weight from one hundred sixty-five down to one hundred nine.

Priya: Reducing the Hamming weight of the polynomial by that much sounds like a direct win for efficiency, but I wonder if there's any trade-off in terms of security parameters or if this just affects computational overhead.

Nadia: The paper addresses that directly; they also propose a "dirty-aware register-allocation policy and an XOR-operation reordering" which cuts the VMOV count by up to forty-eight point one percent while leaving the XOR count unchanged, showing they focused on instruction movement efficiency, not just minimizing the XOR operations themselves.

Elias: That VMOV reduction is crucial because they point out that VMOV instructions account for nearly half of all instructions in bit-sliced butterfly assembly; so optimizing those data transfers is key to lowering the total instruction cost.

Conclusion: Nadia: So, wrapping up our discussion on "Optimizing Polynomial Multiplication and Fixed-Weight Sampling for HQC on ARM Cortex-M4," the paper shows a combination of techniques—the sparser modulus, the dirty-aware register allocation, and the predicated expansion—that leads to substantial reductions in key generation, encapsulation, and decapsulation times.

Elias: They report that these combined algorithmic optimizations result in performance gains of twenty-seven point seven–thirty-three point one percent for key generation, twenty-seven point six–thirty-four point six percent for encapsulation, and twenty-two point zero–twenty-nine point eight percent for decapsulation relative to prior state-of-the-art implementations on the NUCLEO-L4R5ZI board.

Priya: What this means practically is that we can expect much faster cryptographic operations when deploying HQC on these kinds of embedded systems, which is important for any scenario where latency matters.

Nadia: Exactly; and if you factor in the optional caching strategy for repeated key reuse, those gains are even more pronounced, reaching up to thirty-two point seven percent for encapsulation and eighteen point nine percent for decapsulation in that specific scenario.

Elias: It really shows how addressing the instruction movement overhead through register allocation policies can yield significant results even when minimizing a different instruction type like XOR operations.

Priya: I just want to emphasize that while the speed is improved, we still need to keep an eye on whether these optimizations introduce any new vulnerabilities or if they change the security assumptions of HQC itself.

Nadia: That's a fair point, Priya; we have to ensure that every performance gain doesn't come with an unexpected security cost before we look at deploying this in a production environment.

Elias: Before we move on to our next topic, it’s clear that the work in "Optimizing Polynomial Multiplication and Fixed-Weight Sampling for HQC on ARM Cortex-M4" provides a solid blueprint for optimizing cryptographic primitives on resource-constrained embedded systems.

Jihoon Jang, Hanbeom Shin, Suhri Kim, Seokhie Hong, *Donggeun Kwon

Korea University · Sungshin Womens University · SmartM2M

cs.AR, cs.CR

Submitted: 2026-08-10

Updated: 2026-08-10

Comments: 22 pages, 1 figure, 11 tables

Code: https://github.com/mupq/pqm4

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 90/100

The gist: This research presents significant optimizations for implementing Hamming QuasiCyclic (HQC) on resource-constrained ARM Cortex-M4 processors, addressing performance bottlenecks in polynomial

Key concepts

Frobenius Additive FFT (FAFFT): This is an algorithm used to perform binary polynomial multiplication efficiently. The authors optimized it by using a sparser modulus, which reduced the cost of reconstructing the result after the transform, making the core multiplication step much faster on the processor.
VMOV Instructions: These are instructions that move data from memory into registers. The paper found that minimizing these moves is crucial because they account for nearly half of all instructions in their specific multiplication method. Reducing VMOV count significantly lowered the total instruction cost without changing the number of XOR operations.
ARM Predicated Instructions: These are special ARM instructions that allow conditional operations (like OR) to be performed based on a condition, even without using a separate mask. This technique was used during fixed-weight sampling to ensure constant-time execution while speeding up the process by replacing costly masking operations.

Terminology

Elias — 9× in this paper · explained in 2 episodes
Nadia — 9× in this paper · explained in 2 episodes
Core — 7× in this paper · explained in 2 episodes
ARM Predicated Instructions — 4× in this paper · explained in 1 episode
Hamming Quasi-Cyclic — 4× in this paper
Spill-Penalized Dirty-Aware Farthest-First — 3× in this paper
Benchmarking — 2× in this paper · explained in 3 episodes
Chinese Remainder Theorem — 2× in this paper
Benchmark — 1× in this paper · explained in 2 episodes
Computational overhead — 1× in this paper · explained in 2 episodes
Decode — 1× in this paper · explained in 2 episodes
Extended Euclidean Algorithm — 1× in this paper
Mask Generation — 1× in this paper · explained in 2 episodes
Objective Function — 1× in this paper · explained in 2 episodes

Summary

This research presents significant optimizations for implementing Hamming QuasiCyclic (HQC) on resource-constrained ARM Cortex-M4 processors, addressing performance bottlenecks in polynomial multiplication and fixed-weight sampling. The work is crucial because HQC has been selected as an additional post-quantum KEM standard by NIST, and its efficiency directly impacts the practical deployment of this cryptographic primitive. By optimizing these core operations—polynomial multiplication, support expansion in fixed-weight sampling, and introducing optional caching—the authors achieve substantial reductions in key generation, encapsulation, and decapsulation times.

Optimizing Polynomial Multiplication

The dominant operation in HQC is binary polynomial multiplication over the ring F2[x]/(x n - 1). The authors combine algorithm-level optimizations of Frobenius Additive FFT (FAFFT) with register-level optimizations for bit-sliced butterfly assembly. Key improvements include:

Integrating truncated basis conversion and the sharing of the forward transform of the common operand r2 into the FAFFT-CRT implementation.
Finding a 34% sparser FAFFT modulus that lowers the CRT reconstruction cost for HQC-1, reducing its Hamming weight from 165 to 109.
Proposing a dirty-aware register-allocation policy and an XOR-operation reordering that reduce the VMOV count by up to 48.1% while leaving the XOR count unchanged. This addresses the fact that VMOV instructions account for nearly half of all instructions in bit-sliced butterfly assembly, showing that minimizing only the XOR count can increase total instruction cost.

Optimizing Support Expansion in Fixed-Weight Sampling

Fixed-weight sampling requires expanding a support into a dense bit vector, which is costly. The authors propose rewriting the inner loop of the function to expand the support generated by HQC sampling into a dense bit vector, using ARM predicated instructions. Specifically:

They use ARM predicated instructions and the Cortex-M4 IT block and ORREQ instructions to directly perform the conditional OR operation, allowing for constant-time execution without a mask.
This approach, combined with 4-way outer-loop unrolling, reduces the per-word cost of the inner loop from approximately 22 cycles to 6 cycles while remaining constant-time.

Improved HQC Performance and Caching

The combined algorithmic optimizations lead to significant performance gains on the NUCLEO-L4R5ZI board:

** Key Generation, Encapsulation, and Decapsulation are reduced by up to 33.1%, 34.6%, and 29.8% over prior state-of-the-art implementations.**

Additionally, the paper proposes an optional caching strategy for environments handling many sessions under the same public key:

This strategy precomputes the regenerated polynomial, its FAFFT forward transform, and the public-key hash once and reuses the stored results instead of recomputing them on every encapsulation and decapsulation.
In a reused key scenario, this caching yields a further reduction of up to 32.7% for encapsulation and 18.9% for decapsulation compared to the case without caching.

Evaluation Results

Benchmarking on the NUCLEO-L4R5ZI demonstrates the effectiveness of these optimizations:

** The proposed method reduces key generation, encapsulation, and decapsulation by 27.7–33.1%, 27.6–34.6%, and 22.0–29.8% relative to the lower cycle count of the two prior state-of-the-art implementations for each operation.**

** The optional caching yields a further reduction of up to 32.7% and 18.9% for encapsulation and decapsulation under a reused key.**

Memory Trade-offs

The authors analyze the memory impact, noting that while caching increases RAM usage by approximately 10,792 bytes for HQC-1, the peak stack requirement decreases by 10,824 bytes. Caching trades this speedup for additional static memory as it keeps public values resident in RAM rather than building them on the stack at every call.

Conclusion

The paper concludes that the combination of optimizations—including a 34% sparser FAFFT modulus, VMOV minimization via a Spill-Penalized Dirty-Aware Farthest-First policy, and predicated 4-way expansion—significantly accelerates HQC on the ARM Cortex-M4, achieving reductions of 22.0–34.6% across KEM operations, with caching offering further gains in steady states under repeated key reuse. The VMOV optimizations are presented as a general framework applicable to other XOR-count-minimized implementations in post-processing steps.

Improvements for AI systems

As a fastidious researcher, I have analyzed the provided paper, Optimizing Polynomial Multiplication and Fixed-Weight Sampling for HQC on ARM Cortex-M4. This research focuses on accelerating a post-quantum cryptographic primitive called Hamming QuasiCyclic (HQC) on resource-constrained embedded systems (ARM Cortex-M4).

While the paper's primary contribution is in cryptography, its underlying optimizations—polynomial multiplication, fixed-weight sampling, and caching strategies—represent powerful algorithmic techniques applicable to various domains requiring high-speed computation over finite fields or binary vector spaces.

Here are the specific improvements derived from this research that can be applied to AI systems:

)

(1) Multiply polynomials over finite fields (like GF(2)) using optimized FFT-based methods combined with Chinese Remainder Theorem (CRT). This involves decomposing large polynomial multiplications into smaller, faster computations.

(2) Implement constant-time operations for fixed-weight sampling of vectors or data structures. This ensures that the execution time does not depend on the secret data being sampled, which is critical for security and side-channel resistance in sensitive AI models.

(3) Develop a dirty-aware register allocation and XOR reordering framework for polynomial arithmetic kernels. This addresses the performance bottleneck caused by moving data between general-purpose registers (GP) and vector floating-point registers (VFP), ensuring that instruction scheduling minimizes costly data movement overhead, regardless of the specific XOR count optimization used.

(4) Utilize predicated execution techniques in inner loops for bitwise operations. This replaces branch-heavy or masked conditional logic with fixed instruction flow, guaranteeing constant-time execution for data processing steps that depend on secret inputs (e.g., activation functions or attention mechanisms).

(5) Implement advanced caching strategies for frequently reused public keys, transform results (like FFTs), and hash computations in SIMD/embedded environments. This trades static memory for significant speedup during repeated operations, allowing inference or decryption processes to run much faster when the same key/model is used multiple times.

)

Abstract

In this paper, we present an optimized implementation of Hamming Quasi-Cyclic (HQC) on the ARM Cortex-M4. We optimize (i) the polynomial multiplication and (ii) the support expansion in fixed-weight sampling, and (iii) propose an optional caching strategy that reuses the public transforms and hash recomputed under a fixed key. For the polynomial multiplication, the fixed-constant multiplications in the Frobenius additive FFT (FAFFT) butterfly spend nearly half of their instructions on VMOV data movements between general-purpose and floating-point registers rather than arithmetic. Because minimizing the XOR count alone can increase the total instruction count, we propose a dirty-aware register-allocation policy and an XOR-operation reordering that reduce the VMOV count by up to 48.1% while leaving the XOR count unchanged. We apply these to a multiplication that combines prior FAFFT-CRT methods, and for HQC-1 we further find a 34% sparser FAFFT modulus that lowers the CRT reconstruction cost. For fixed-weight sampling, we rewrite the support expansion with predicated execution and 4-way unrolling, lowering the per-word cost of its inner loop from 22 to 6 cycles while remaining constant-time. On the NUCLEO-L4R5ZI board, our implementation reduces key generation, encapsulation, and decapsulation by up to 33.1%, 34.6%, and 29.8% over the faster of the two prior state-of-the-art implementations, and the optional caching yields a further reduction of up to 32.7% and 18.9% for encapsulation and decapsulation.