Skip to content

Back to the catalog

Optimizing HQC with Enhanced Parallel Binary Polynomial Multiplication on GPUs
eprint.iacr.orgpaper

Optimizing HQC with Enhanced Parallel Binary Polynomial Multiplication on GPUs

This paper presents an end-to-end GPU implementation of the HQC code-based key encapsulation mechanism. It speeds up GF(2) polynomial multiplication with a parallel Frobenius additive FFT and a Toeplitz matrix-vector mapping onto INT1 tensor cores. On an RTX 4090 the multiplier reaches 3,828k polymul/s, about 2.9x the earlier HIGH implementation. Full KEM throughput is 1.56x, 1.55x and 2.03x higher for keygen, encaps and decaps. Five thread-to-KEM mapping variants are tested on RTX 3090 and Jetson AGX Orin.

TL;DR Builds a GPU-resident HQC KEM with FAFFT and INT1 tensor-core multipliers, reaching 254 µs single-shot latency and up to 2x the throughput of prior GPU work.
Open original ↗
Document

What it is

This is an ePrint paper (2026/2538, approved 20 October 2026) by DongCheon Kim, JunHyeok Choi, Wai Kong Lee and Seog Chung Seo. It is a minor revision of a TCHES 2027 paper. It describes a GPU implementation of the HQC KEM that keeps the whole KEM on the GPU and compares against the earlier GPU implementation, HIGH.

How it works

Binary polynomial multiplication over GF(2) is the dominant cost in HQC. The paper uses two multipliers:

  • A parallelized Frobenius additive FFT (FAFFT).
  • The cyclic product viewed as a Toeplitz matrix-vector product, mapped onto INT1 tensor cores.

The authors measured combinations of these multipliers directly on the GPU to pick the best one for each architecture.

Once multiplication is fast, the bottleneck moves to hashing, Reed-Muller/Reed-Solomon coding and fixed-weight sampling. The paper adds warp-level parallelization for those stages. Keeping the entire KEM GPU-resident reduces memory traffic.

What to do

The five variants differ in how KEM instances map to GPU threads, so choose by workload. The page names three of them:

VariantResult on RTX 4090
CG (Coarse-Grained)Maximizes batch throughput
BMMAw (tensor-core based)Single-shot latency as low as 254 µs
FGmw (warp-parallel)Latency of 354 µs without INT1 tensor cores

The abstract does not name the other two variants or give their numbers.

Use FGmw on GPUs without INT1 tensor-core support. The paper reports it still performs well there.

Throughput gains over HIGH on the RTX 4090 are 2.9x for standalone multiplication (3,828k polymul/s). End-to-end, CG is 1.56x for keygen, 1.55x for encaps and 2.03x for decaps.

Caveats

  • All five variants were also evaluated on an RTX 3090 and a Jetson AGX Orin to show portability. The abstract gives no numbers for those platforms.
  • The headline comparisons are against HIGH only, and only the abstract was available, so parameter sets, batch sizes and constant-time properties are not stated.
  • The abstract does not discuss side-channel resistance.

Organisations named here

  • Frobenius additive fast Fourier transform
  • HIGH
  • Reed-Muller/Reed-Solomon coding
  • TCHES
  • Toeplitz matrix-vector product

Technologies named here

  • NVIDIA RTX 4090
  • NVIDIA RTX 3090
  • NVIDIA Jetson AGX Orin
  • HQC
  • CUDA

Related in other