Paper 2026/1588
Strided Frobenius Additive FFT and its Application to HQC
, Academia SinicaAbstract
Boolean polynomial multiplication is the primary computational bottleneck of the Hamming Quasi-Cyclic (HQC) key encapsulation mechanism. In this paper, we reframe the Frobenius Additive FFT (FAFFT) in ring-theoretic terms, via quotient-ring homomorphisms and the Chinese Remainder Theorem. This perspective shows that a complete decomposition into evaluation points is unnecessary for multiplication, and naturally yields the Strided FAFFT (SFAFFT), which operates over smaller finite fields with fewer butterfly stages and admits a much sparser CRT modulus for the non-power-of-two degrees in HQC. Our SFAFFT implementations outperform all previous FAFFT-based multiplications on every tested platform (x86 AVX2, GFNI, Apple M1, ARM Cortex-A72, and Cortex-M4), and set new overall speed records for HQC in nearly all settings except plain AVX2, where Toom-Cook-Karatsuba remains faster for the two smaller parameter sets.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint.
- Keywords
- HQCadditive FFTBoolean polynomial multiplicationImplementation
- Contact author(s)
-
mschen @ crypto tw
daniel0702chien @ gmail com
r12922085 @ csie ntu edu tw
cesarehuang @ icloud com
linhh @ cs nthu edu tw
PengTaiwan6517 @ gmail com
by @ crypto tw - History
- 2026-08-06: approved
- 2026-08-03: received
- See all versions
- Short URL
- https://ia.cr/2026/1588
- License
-
CC0
BibTeX
@misc{cryptoeprint:2026/1588,
author = {Ming-Shing Chen and Tun-You Chien and Chun-Ming Chiu and Cesare Huang and Han-Hsuan Lin and Chun-Tao Peng and Bo-Yin Yang},
title = {Strided Frobenius Additive {FFT} and its Application to {HQC}},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1588},
year = {2026},
url = {https://eprint.iacr.org/2026/1588}
}
