FORGE: FAFFT-Optimized Ring Arithmetic for GPU Execution of HQC and BIKE
Recommended citation: FORGE: FAFFT-Optimized Ring Arithmetic for GPU Execution of HQC and BIKE. Yijing Ning, Jiankuo Dong, Tian Zhou, Fangyu Zheng, Guang Fan, Mingzhe Zhang, Jingqiang Lin. 33rd IEEE International Symposium on High-Performance Computer Architecture. HPCA 2027.
Abstract
HQC and BIKE are prominent quasi-cyclic code-based key encapsulation mechanisms (KEMs) that broaden the algorithmic diversity of post-quantum key establishment. However, their performance is dominated by arithmetic over long binary cyclic rings. GPUs provide substantial parallelism for these operations, yet existing implementations largely retain recursive Karatsuba dataflows that poorly match warp-level execution. Frobenius additive fast Fourier transform (FAFFT) provides more regular parallelism, but its power-of-two primitives do not match the irregular ring lengths of HQC and BIKE; moreover, accelerating ring multiplication alone leaves cross-operation reuse and surrounding KEM bottlenecks unaddressed.
To this end, we present FORGE, a unified GPU execution framework for HQC and BIKE. FORGE first implements a warp-cooperative FAFFT engine with GPU-native carry-less arithmetic over \(\mathbb{F}_{2^{64}}\), mapping each power-of-two product to regular warp-level execution. A parameter-aware ring backend then combines these primitives through block-level decomposition and selects compact or segmented execution according to transform work, exposed parallelism, intermediate staging, and resource demand. FORGE further integrates the ring backend with complete KEM dataflows. For HQC, it reuses common-operand transforms, directly forms the representations required by ciphertext generation, decoding, and verification, and partitions stages according to their on-chip state. For BIKE, it replaces iterative Euclidean inversion with a fixed-schedule Itoh/FAFFT graph using permutation-based squaring and restructures the decoder around packed bit-sliced counters. Warp-cooperative Keccak completes KeyGen, Encaps, and Decaps for both schemes at security levels 1, 3, and 5. On an RTX 4090 at a batch size of 8192, FORGE sustains 2285.1/1722.7/1079.5 Kops/s for HQC-128 and 800.2/3154.9/609.5 Kops/s for BIKE-128 in KeyGen/Encaps/Decaps, respectively. Compared with prior state-of-the-art GPU implementations on the same platform, FORGE achieves 2.49×–2.94× higher throughput for HQC-128 and 11.36×–80.64× higher throughput for BIKE-128.
