Interpretation of the HQC Algorithm in Post-Quantum Cryptography

On March 11, 2025, the National Institute of Standards and Technology (NIST) published the Status Report on the Fourth Round of the NIST Post-Quantum Cryptography Standardization Process (NIST IR 8545). This report announced the selection of the HQC algorithm as a new post-quantum cryptography standard. The HQC algorithm is an asymmetric key encapsulation mechanism (KEM) based on coding theory. Earlier, on August 13, 2024, NIST had already published the FIPS 203 standard for post-quantum KEM based on lattice theory. Unlike FIPS 203, the HQC algorithm is not based on lattice theory but on a different hard problem. As a KEM, the HQC algorithm serves as both a complement and an alternative to FIPS 203, effectively addressing potential vulnerabilities in FIPS 203.

Public-Key Cryptography Based on Coding Theory

Coding theory is a field dedicated to researching method of efficient transmission and storage of digital information. Its primary objective is to design efficient, reliable, and error-correcting codes to ensure accurate recovery of original data during transmission or storage. Public-key schemes based on coding theory date back to the 1970s with the McEliece cipher proposed by Robert McEliece. The confidence in McEliece encryption stems from a simple yet powerful fact: no effective attack algorithm has been able to break it over more than 50 years. This historical record further solidifies the importance of code-based cryptography in the post-quantum era.

Principles of the HQC Algorithm

HQC stands for Hamming Quasi-Cyclic, indicating its use of codes based on Hamming distance—specifically, a combination of truncated Reed-Solomon codes and repeated Reed-Muller codes. Although the underlying hard problems differ from those used in FIPS 203, there are similarities in the algorithmic approach.

1. Noise Utilization: Both algorithms employ noise. During the encryption step, random noise is generated and mixed into the message encoding using the public key to produce ciphertext. During the decryption step, the private key and decoding algorithm restore the message.
2. FO Transformation: Both algorithms use the Fujisaki-Okamoto (FO) transformation to convert an IND-CPA secure public-key encryption (PKE) mechanism into an IND-CCA2 secure key encapsulation mechanism (KEM).

Advantages and Disadvantages of the HQC Algorithm

According to the NIST report, the HQC algorithm offers the following advantages:

1. Reliable Security: HQC is considered more reliable due to its lower decryption failure rate (DFR). NIST places greater trust in HQC’s security compared to BIKE, which requires modifications to achieve similar DFR levels.
2. Superior Performance: HQC outperforms BIKE and McEliece ciphers significantly in key generation and decryption speeds. BIKE is 6-10 times slower than HQC in key generation, 5-7 times slower than HQC in decapsulation. Key generation in McEliece is an outlier, being three orders of magnitude more costly than HQC’s.
3. Compact Decryption Keys: This feature is particularly beneficial for resource-constrained environments like IoT devices.

Table 1 Performances of BIKE/HQC/McEliece in thousands of cycles on x86_64

However, the HQC algorithm also has some drawbacks:

1. Large Key and Ciphertext size: Compared to BIKE, HQC’s encapsulation keys sizes are larger, which can increase communication overhead. The encapsulation keys of HQC are about 41-47 % larger than those of BIKE. The ciphertexts of HQC are about three times larger than those of BIKE.
2. Network Sensitivity: Generally, when network conditions (e.g., transmission rates and packet loss) are ignored or sufficiently good, HQC results in faster handshakes. In contrast, when network conditions are sufficiently bad, BIKE outperforms HQC

Table 2 BIKE/HQC/McEliece key and ciphertext sizes in bytes

Application Scenarios for the HQC Algorithm

As a key encapsulation mechanism, HQC is suitable for establishing shared secrets over insecure channels, with applications in email encryption, network protocols, IoT devices, and online payment systems. Its robust security features make it a promising candidate for future cryptographic standards in various industries.

As a seasoned expert in data security with 30 years of extensive industry experience, Watchdata focuses on core technologies including cryptographic algorithms, digital security protection, and secure chip operating systems. Continuously monitoring the updates of NIST standard, we are particularly focused on the cutting-edge progress of post-quantum algorithms, actively positioning ourselves for technological evolution. We are dedicated to providing clients with comprehensive and powerful digital security solutions, using technology to empower the steady development of the industry.