HQC Post-Quantum Cryptography Decryption with Generalized Minimum-Distance Reed-Solomon Decoder
2026-03-20 • Cryptography and Security
Cryptography and SecurityInformation Theory
AI summaryⓘ
The authors studied a part of the HQC cryptography system that checks for errors when decoding messages. They found that using a better type of decoder called the generalized minimum-distance (GMD) decoder improves error correction compared to older methods. This allows them to make the code shorter and faster while still being reliable. They also designed hardware that runs this decoding efficiently, reducing time and space needed by 20% and 15%, respectively. Their work focuses on improving the performance of HQC-128, a specific security level in the HQC system.
Hamming Quasi-Cyclic (HQC)Reed-Muller (RM) codesReed-Solomon (RS) codessoft-decision decodinggeneralized minimum-distance (GMD) decoderpost-quantum cryptographyAgrawal-Vardy bounderror-correcting codeshardware architecturedecryption latency
Authors
Jiaxuan Cai, Xinmiao Zhang
Abstract
Hamming Quasi-Cyclic (HQC) was chosen for the latest post-quantum cryptography standardization. A concatenated Reed-Muller (RM) and Reed-Solomon (RS) code is decoded during the HQC decryption. Soft-decision RS decoders achieve better error-correcting performance than hard-decision decoders and accordingly shorten the required codeword and key lengths. However, the only soft-decision decoder for HQC in prior works is an erasure-only decoder, which has limited coding gain. This paper analyzes other hardware-friendly soft-decision RS decoders and discovers that the generalized minimum-distance (GMD) decoder can better utilize the soft information available in HQC. Extending the Agrawal-Vardy bound for the scenario of HQC, it was found that the RS codeword length for HQC-128 can be reduced from 46 to 36. This paper also proposes efficient GMD decoder hardware architectures optimized for the short and low-rate RS codes used in HQC. The HQC-128 decryption utilizing the proposed GMD decoder achieves 20% and 15% reductions on the latency and area, respectively, compared to the decryption with hard-decision decoders.