Paper 2025/2003

A Sparse Polynomial Multiplier for HQC Integrating Parallelism and Power-Based Side-Channel Countermeasures

Abstract

The Hamming Quasi-Cyclic (HQC) scheme has recently been standardized as a post-quantum key encapsulation mechanism (KEM), emphasizing the importance of efficient and secure hardware realizations on embedded platforms. However, HQC relies heavily on sparse–dense polynomial multiplications, where conventional shift-and-add architectures remain both performance- and security-critical. In FPGA implementations, these multiplications dominate execution time—occupying 59.5%, 56.1%, and 58.3% of the total latency for KeyGen, Encap, and Decap, respectively—and are further vulnerable to correlation power analysis (CPA) due to deterministic, index-driven memory access patterns. As countermeasures, parallelization improves performance at the cost of additional area. Dummy insertion with random shuffling mitigates leakage but incurs extra cycle overhead. To address this, we propose a co-designed dummy-inserted parallel shift-and-add multiplier for HQC. The design integrates dummy insertion and two-index parallelism in a complementary manner, achieving reduced cycles with area efficiency while providing intrinsic resistance to CPA. Implemented on a Xilinx Artix-7 FPGA, the proposed architecture achieves up to a 1.25× speedup over the baseline sequential multiplier while maintaining near–state-of-the-art area–time efficiency—incurring only a 1.16× AT overhead to simultaneously deliver accelerated performance and CPA resistance. Test Vector Leakage Assessment (TVLA) measurements and theoretical analysis confirm that the parallel architecture effectively suppresses power-based side-channel leakage and provides inherent resistance against CPA—reducing significant leakage points from 4.29% to 0.09%. This work demonstrates that performance and side-channel resistance can be jointly optimized through synergistic hardware–algorithm co-design, offering a practical and scalable HQC accelerator for post-quantum embedded systems.