PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2608.18145v1cs.ARcs.CR

TL;DR

Polynomial multiplication and sampling contribute substantially to HQC performance, but on Cortex-M4 instruction costs include register-transfer overhead beyond XOR counts. The paper combines FAFFT-CRT multiplication optimizations with register-aware scheduling, predicated support expansion, and optional caching; its implementation reduces all three KEM operations, with additional gains from caching under a reused key.

  • Problem

    On Cortex-M4, polynomial multiplication and sampling are important performance costs, and reducing XOR count alone may not reduce total instruction cost because VMOV transfers increase under GP-register pressure.

    Source: §1 · p. 2

  • Method

    The implementation combines FAFFT-CRT multiplication optimizations and VMOV-aware register allocation and XOR reordering with predicated, unrolled support expansion and optional reuse of public-key transforms and hash.

    Source: §1.1 · p. 2, §5.2 · p. 17

  • Results

    22.0–34.6% lower cycle counts across all three KEM operations than the state of the art, with caching further reducing encapsulation and decapsulation by up to 32.7% and 18.9% under a reused key.

    Source: §7 · p. 20

  • Takeaways & Limitations

    Caching is relevant to deployments that repeatedly decapsulate under a fixed key, where the public-key-dependent transforms and hash recur.

    Source: §5.2 · p. 17, §7 · p. 21

    Optional caching benefits only deployments that repeatedly decapsulate under a fixed key and keeps its transform cache permanently resident in RAM.

    Source: §7 · p. 21

Abstract

from arXiv · show

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.

1 Introduction

HQC performance on Cortex-M4 is shaped by polynomial multiplication, sampling, and hashing, while the paper targets multiplication and fixed-weight support expansion with implementation-level optimizations. It combines prior FAFFT-CRT approaches with new register and sampling optimizations and reports faster KEM operations than prior implementations.

1 Introduction

  • HQC polynomial multiplication and sampling, alongside hashing, largely determine performance; the paper targets multiplication and fixed-weight sampling for optimization.HQC was selected by NIST as an additional post-quantum KEM standard, providing algorithmic diversity beyond lattice-based ML-KEM.Source: §1 · pp. 1–2

1.2 Related Work

  • Prior Cortex-M4 work reduced transform size and XOR counts with FAFFT-CRT, but instruction cost can also rise from VMOV transfers under GP-register pressure.The paper builds on the FAFFT-CRT implementations of Jang et al. and Chen et al..Source: §1 · p. 2, §1.2 · p. 3

1.1 Our Contributions

  • 40.6%, 48.1%, and 37.6% fewer VMOV instructions for HQC-1, HQC-3, and HQC-5, respectively, while preserving the butterfly EOR count.The approach combines dirty-aware register allocation with XOR reordering because reducing XOR count alone can increase total instruction cost.Source: §1.1 · p. 2
  • 22 to 6 cycles per word for the constant-time support-expansion inner loop, using predicated conditional OR operations and 4-way outer-loop unrolling.The support expansion converts sampled indices into a dense bit vector.Source: §1.1 · p. 2
  • 27.7–33.1%, 27.6–34.6%, and 22.0–29.8% lower cycle counts for key generation, encapsulation, and decapsulation, respectively, than the faster prior implementation.The comparison is against Chen et al. and Jang et al. on the NUCLEO-L4R5ZI board.Source: §1.1 · pp. 2–3

2 Preliminaries

The preliminaries establish HQC's algebraic setting and its main computational components, then outline FAFFT and the Cortex-M4 features that shape the implementation. The paper focuses on polynomial multiplication and sampling, two operations that dominate performance together with hashing.

2.1 Notation

  • A length-n vector over F2 is identified with a polynomial in R = F2[X]/(X^n − 1), and Trun keeps the low n′ bits of a vector.The notation also uses ω(·) for Hamming weight and R_ω for ring elements of weight ω.Source: §2.1 · pp. 3–4

2.2 Hamming Quasi-Cyclic (HQC)

  • HQC is an IND-CCA2 KEM based on syndrome decoding for quasi-cyclic codes, built by applying the Fujisaki–Okamoto transform with implicit rejection to an IND-CPA-secure public-key encryption scheme.Its error-correction code serially combines Reed-Muller and Reed-Solomon codes.Source: §2.2 · p. 4

2.3 Frobenius Additive FFT (FAFFT)

  • FAFFT evaluates fewer points by using Frobenius-related values, then multiplies the transformed operands pointwise and applies the inverse transform.In the Cortex-M4 bit-sliced implementation, butterfly additions are XORs between bit planes, and fixed-constant multiplications are straight-line XOR sequences.Source: §2.3 · p. 5

2.4 ARM Cortex-M4

  • The Cortex-M4 supports predicated execution through IT blocks, but transfers between GP and floating-point registers require VMOV instructions.Its available GP registers are limited, making VMOV cost a key overhead in the bit-sliced FAFFT butterfly.Source: §2.4 · p. 6

3 Polynomial Multiplication Optimization

The polynomial-multiplication optimizations build on FAFFT-CRT, further reduce the HQC-1 modulus weight, and minimize butterfly VMOV overhead through register allocation and XOR reordering.

3 Polynomial Multiplication Optimization

  • The section combines FAFFT-CRT optimizations, lowers the FAFFT modulus weight for HQC-1, and reduces bit-sliced butterfly VMOV overhead through register allocation and XOR reordering.It builds on Jang et al., incorporates optimizations from Chen et al., and reports multiplication cycles in Section 3.3.Source: §3 · p. 6

3.1 Combining FAFFT-CRT Multiplication Techniques

The multiplication path combines FAFFT with CRT for parameters that admit a residue-ring split, while HQC-5 uses a pure double-size FAFFT. The section also reduces the HQC-1 FAFFT modulus weight to lower reconstruction cost.

3.1 Combining FAFFT-CRT Multiplication Techniques

  • For HQC-1 and HQC-3, the method combines FAFFT with CRT and radix-16 residue multiplication, incorporating truncated basis conversion and sharing the forward transform of r2.The residue multiplication choice differs by parameter: Chen et al. is faster for HQC-1, while Jang et al. is faster for HQC-3; HQC-5 uses no residue ring.Source: §3.1 · pp. 6–7

3.1.1 A Low-Weight FAFFT Modulus

  • 109 is the HQC-1 FAFFT modulus weight, down from Chen et al.'s 165, a 34% reduction that directly lowers reconstruction cost.The HQC-3 weight of 199 was already minimal and is retained; the modulus-weight optimization does not apply to HQC-5.Source: §3.1.1 · p. 7

3.2 VMOV Minimization via Register Allocation and XOR Reordering

This section reframes FAFFT butterfly optimization around GP–VFP data movement as well as XOR count, then combines dirty-aware register allocation with semantics-preserving XOR reordering to reduce VMOVs. The methods target register pressure, which can make movement instructions nearly as costly as the XOR operations themselves.

3.2.1 Motivation

  • 47–51% of instructions for each fixed-constant multiplication are VMOVs; five shorter-XOR variants still increase total instruction counts.Across Jang et al.'s 12 butterfly assemblies, there are 2,034 EOR instructions and 1,992 VMOV instructions; the five variants reduce EORs by 1–3 each but add 14–36 VMOVs.Source: §3.2.1 · p. 8

3.2.2 XOR Sequences and the Implementation Cost Model

  • An XOR sequence fixes the EOR count, but register allocation determines VMOV loads and dirty-variable spills, so total cost is EOR plus VMOV.A clean variable can be evicted without a spill, whereas evicting a dirty variable requires writing its updated value back to a VFP register.Source: §3.2.2 · p. 9

3.2.3 Reducing VMOV Costs via Register Allocation

  • 1,804 VMOVs at p = 11 is SPF's minimum across the twelve HQC-5 butterflies; its dirty-variable penalty trades fewer spills against additional clean reloads.SPF adjusts farthest-first victim selection for dirty status, and the penalty p controls how much next-use distance it will sacrifice to avoid a dirty spill.Source: §3.2.3 · pp. 10–11, Figure 1 · p. 11

3.2.4 Reducing VMOV Costs via XOR Reordering

  • Simulated annealing searches commuting-operation reorderings that preserve M, using local swaps and bounded relocations while accepting some cost increases to escape local minima.Only operations that commute may change relative order, preserving the resulting matrix M.Source: §3.2.4 · pp. 12–13
  • 40.6% (from 1,866 to 1,109) for HQC-1, 48.1% (from 2,396 to 1,243) for HQC-3, and 37.6% (from 1,992 to 1,244) for HQC-5 were the VMOV-count reductions.The comparisons keep XOR sequences fixed; HQC-1 uses the same sequence allocated with farthest-first as its reference.Source: Table 5 · p. 13, §3.2.4 · p. 13

3.3 Multiplication Performance

The proposed multiplication is benchmarked in isolation on the NUCLEO-L4R5ZI at 20 MHz, combining the multiplication construction and VMOV minimization. It uses fewer cycles than both prior implementations across all three HQC parameter sets.

3.3 Multiplication Performance

  • The isolated multiplication benchmark ran on the NUCLEO-L4R5ZI at 20 MHz against implementations by Chen et al. and Jang et al.The comparison captures the joint effect of the multiplication construction and VMOV minimization.Source: §3.3 · p. 13
  • Relative to the faster of the two prior implementations, multiplication cycles drop by 10.2% for HQC-1, 10.3% for HQC-3, and 1.1% for HQC-5.Source: §3.3 · p. 14
  • The largest reduction was 10.3% for HQC-3, where truncated basis conversion removes most forward-transform overhead; the smallest was 1.1% for HQC-5, a pure double-size FAFFT without a residue ring.The HQC-5 construction therefore benefits least from the proposed multiplication construction.Source: §3.3 · p. 14

4 Fixed-Weight Sampling Optimization

The section speeds up constant-time expansion of HQC’s sampled fixed-weight supports into dense bit vectors. Predicated scatter and four-way unrolling reduce expansion cycles while preserving input-independent execution time.

4 Fixed-Weight Sampling Optimization

  • The WSV step expands sampled support indices into a length-n bit vector and runs repeatedly during key generation, encapsulation, and decapsulation.It is called twice during key generation, three times during encapsulation, and four times during decapsulation.Source: §4 · p. 14, §4.1 · p. 14

4.1 Constant-Time Support Expansion

  • Directly indexing support positions creates secret-dependent memory access; the prior constant-time method scans every output word against every support element, concentrating cost in an n64 × ω loop.For HQC-1, the loop performs 277 × 75 conditional accumulations per expansion.Source: §4.1 · pp. 14–15

4.2 Optimization Method

  • Predicated OR instructions replace mask generation, while four-way unrolling reuses each loaded support element across four output words; a dedicated assembly loop handles register pressure.The loop bounds and sequential memory accesses are public and fixed, so execution time is independent of the input support; up to three remaining words use a scalar tail loop.Source: §4.2 · pp. 15–16

4.3 Results

  • About 73.5%–73.7% fewer expansion cycles than the prior implementation; for HQC-1, key generation fell from 859,628 to 227,379 cycles.HQC-1 encapsulation fell from 1,461,071 to 384,121 cycles and decapsulation from 1,889,926 to 496,851 cycles; the inner loop drops from about 22 to 6 cycles per word.Source: §4.3 · p. 16, Table 8 · p. 16

5 Caching Strategies

The optional cache stores public-key-derived values to avoid recomputing them across operations under a repeated key. Its benefit depends on repeated use of the same key, especially for decapsulation, and trades local RAM for speed.

5 Caching Strategies

  • The cache resides entirely in local RAM, leaves transmitted public-key size unchanged, and reuses externally public values rather than secret-dependent data.The paper states that this caching does not compromise security; the tradeoff is memory for speed.Source: §5 · p. 17, §5.2 · p. 18

5.1 Applicability and Scenarios

  • Caching helps when operations repeat under the same key; that condition is structurally guaranteed for decapsulation with a device’s fixed public key, but is less likely for session-based encapsulation.Key generation is a one-time operation and is unaffected; the measurements assume steady-state reuse of one public key.Source: §5.1 · p. 17

5.2 Caching Targets and Mechanism

  • The cache reuses the public-key hash and forward transforms of h and s, which recur identically because they depend only on the fixed public key.These values are needed in encapsulation and decapsulation, including decapsulation’s FO re-encryption.Source: §5.2 · p. 17
  • A constant-time full-key comparison in hash_h identifies cache hits; on a miss, the new key and hash are stored and the transforms are regenerated at the next multiplication.Once populated, the stored transforms are used directly by multiplication.Source: §5.2 · p. 18

6 Evaluation

The Cortex-M4 evaluation reports cycle reductions for the proposed uncached method against the fastest prior implementation, then measures caching under repeated public-key use. It also compares RAM and Flash costs, including caching’s shift of transform storage from stack to permanently resident RAM.

6 Evaluation

  • Measurements used an STM32 NUCLEO-L4R5ZI Cortex-M4 board at 20 MHz with zero wait states, arm-none-eabi-gcc 10.3.1, and -O3.The pqm4 benchmarking framework was used for comparison with the prior implementations.Source: §6 · p. 18

6.1 Speed Performance

  • 27.7%–33.1% for Keypair, 27.6%–34.6% for Encaps, and 22.0%–29.8% for Decaps: cycle reductions versus the fastest prior implementation.The proposed method combines the FFT butterfly register-scheduling optimization and 4-way-unrolled support expansion; caching is assessed separately.Source: §6.1 · p. 18, Table 9 · p. 19

6.2 Evaluation of the Caching Strategy

  • 30.3%, 26.0%, and 32.7% for HQC-1, HQC-3, and HQC-5 encapsulation, and 16.7%, 15.3%, and 18.9% for decapsulation: cycle reductions with caching versus without.In steady state with the same public key reused, caching avoids regenerating and transforming public values and recomputing the public-key hash; key generation is not compared.Source: §6.2 · pp. 18–19, Table 10 · p. 19

6.3 Memory Usage

  • 33,736, 35,168, and 162,912 bytes more Flash than for HQC-1, HQC-3, and HQC-5; the implementations fit the target board and stack usage is similar to prior implementations.The increase comes from the adopted RS/RM decoder, whose unrolled matrix–vector products enlarge code size; HQC-5 has the largest increase because it uses a larger RS code.Source: §6.3 · pp. 19–20
  • Caching adds 10,792, 21,704, and 40,040 bytes of static RAM for HQC-1, HQC-3, and HQC-5 while reducing peak stack by 10,824, 21,660, and 29,944 bytes.It moves transforms from per-call stack storage to a static buffer that remains resident between operations; total static RAM plus peak stack is nearly unchanged for HQC-1 and HQC-3 and slightly higher for HQC-5.Source: §6.3 · p. 20, Table 11 · p. 20
  • 14,344 bytes for HQC-1 and 37,504 bytes for HQC-3 are larger than but equal to or below; all three implementations use 2,824 bytes for HQC-5.The RAM differences reflect CRT residue-multiplication choices; the proposed method shares its FAFFT–CRT path with.Source: §6.3 · p. 19, Table 11 · p. 20

7 Conclusion and Future Work

The paper combines FAFFT-CRT and bit-sliced butterfly optimizations with predicated fixed-weight support expansion to accelerate HQC on Cortex-M4. The resulting implementation improves all three KEM operations over prior state of the art, while caching offers additional gains in repeated fixed-key settings at a permanent RAM cost.

Contributions

  • On ARM Cortex-M4, optimizations yield a 34% sparser HQC-1 FAFFT modulus, reduce butterfly VMOV counts 37.6–48.1% at unchanged EOR count, and make constant-time support writes cost 6 rather than 22 cycles per word.Together, these reduce all three KEM operations by 22.0–34.6% over the state of the art.Source: §7 · p. 20

Results

  • 22.0%–34.6% cycle reductions across the three KEM operations over the state of the art, with caching further reducing encapsulation and decapsulation by up to 32.7% and 18.9%.The implementation also reports 37.6%–48.1% fewer butterfly VMOVs at unchanged EOR count and reduces support expansion from 22 to 6 cycles per word while remaining constant-time.Source: §7 · p. 20

Broader applicability

  • VMOV reduction can follow XOR-count minimization as a post-processing step for other XOR-count-minimized implementations, including AES MixColumns.The paper notes that small in-order cores incur explicit moves for spills that XOR count alone does not capture.Source: §7 · pp. 20–21

Limitations and future work

  • Fixing the XOR sequence can miss globally cheaper code; jointly searching the sequence and register allocation remains future work.Caching benefits only repeated decapsulation under a fixed key and keeps its transform cache permanently resident in RAM.Source: §7 · p. 21
Loading 2608.18145v1…