When NIST announced its post-quantum standardization plan, it explicitly committed to selecting at least one key encapsulation mechanism that did not rely on lattice mathematics. The reasoning was simple. If lattice cryptanalysis ever advanced unexpectedly, every lattice-based scheme would fall together. Diversity of mathematical foundations protects against that systemic risk.
In March 2025, NIST selected HQC as that backup KEM. HQC stands for Hamming Quasi-Cyclic. It is a code-based KEM whose security rests on the hardness of decoding random quasi-cyclic codes. HQC-128 is the smallest parameter set, targeting NIST Category 1, equivalent to AES-128 brute-force resistance. This post walks through what HQC-128 looks like in practice and why it occupies its specific niche.
Why NIST Picked Two KEM Families
NIST's primary KEM standard is ML-KEM, formerly Kyber, which uses Module-LWE lattices. ML-KEM is fast, has small keys and ciphertexts, and benefits from extensive cryptanalytic study of lattice problems.
If lattice cryptanalysis ever advances enough to break ML-KEM, the world needs a fallback. Code-based cryptography is the most mature post-quantum alternative. Code-based encryption schemes have been studied since the 1970s, starting with McEliece's original proposal.
McEliece's scheme uses Goppa codes, which produce dramatically large public keys (over 1 MB for some parameter sets). HQC uses quasi-cyclic codes, which keep public keys manageable. NIST selected HQC over alternatives because of its balance of security history, key size, and implementation simplicity.
The result is that NIST now standardizes two KEM families. ML-KEM as the primary, HQC as the backup. Most deployments will use ML-KEM. High-stakes deployments may use both in a hybrid scheme.
For more on KEM design, see ML-KEM Explained.
Key and Ciphertext Sizes
For HQC-128, the byte counts are as follows.
Public key is 2,249 bytes. Secret key is 2,305 bytes. Ciphertext is 4,481 bytes. Shared secret is 32 bytes.
Compare to ML-KEM-512, the smallest ML-KEM. Public key 800 bytes, secret key 1,632 bytes, ciphertext 768 bytes. HQC-128 has a public key roughly three times larger than ML-KEM-512 and a ciphertext roughly six times larger.
The size difference reflects the different mathematical structures. Code-based KEMs typically produce larger ciphertexts than lattice-based KEMs at the same security level. This is the price for foundation diversity.
How Code-Based KEMs Work
The high-level operation of a code-based KEM is conceptually similar to other KEMs. The receiver generates a public-secret key pair. The sender uses the public key to produce a ciphertext that encapsulates a shared secret. The receiver uses the secret key to decapsulate the ciphertext and recover the shared secret. Both parties then have the same shared secret, which is used to derive symmetric encryption keys.
The mathematics under the hood involves error-correcting codes. The public key encodes a generator matrix for a quasi-cyclic code. The secret key encodes the structure that lets the receiver efficiently decode noisy codewords.
When the sender encapsulates, they generate a random message, encode it with the public key's generator matrix, and add carefully designed noise. The result is the ciphertext. The receiver uses the secret key to remove the noise, recover the message, and derive the shared secret.
The security argument is that, without the secret key, recovering the message from a noisy codeword is the syndrome decoding problem. Syndrome decoding for random codes is NP-hard in the worst case and has resisted efficient algorithms for fifty years.
Why Quasi-Cyclic
Classical McEliece used Goppa codes, which have a specific algebraic structure that allows efficient decoding with the secret key. The downside is that Goppa codes require a large public key to encode the generator matrix.
Quasi-cyclic codes have a different structure. A quasi-cyclic code can be described compactly because of its repeating structure. This dramatically shrinks the public key compared to McEliece's Goppa codes.
The trade-off is that quasi-cyclic codes have less algebraic structure for efficient decoding. The HQC scheme handles this by carefully engineering the decoding procedure, which is faster than naive syndrome decoding but still slower than ML-KEM's polynomial arithmetic.
For more on the mathematical foundations, see Lattice-Based Cryptography Explained (which contrasts lattice-based and code-based approaches).
Performance Characteristics
HQC-128 on modern x86 hardware performs roughly as follows.
Key generation takes a few hundred microseconds. Encapsulation takes a few hundred microseconds. Decapsulation takes a few hundred microseconds.
Compared to ML-KEM-512, which performs all three operations in tens to low hundreds of microseconds, HQC-128 is roughly two to five times slower depending on operation. The exact ratio depends on hardware, compiler optimization, and implementation specifics.
For most applications, HQC-128 is fast enough. The performance difference compared to ML-KEM is usually invisible to users. The bandwidth and storage difference is more noticeable.
When HQC-128 Is the Right Pick
The strongest case for HQC-128 is hybrid encryption that combines a lattice KEM with a code-based KEM as defense in depth. The receiver runs both ML-KEM-512 and HQC-128. The shared secret is derived from both individually computed shared secrets, typically by hashing them together with KDF inputs.
If lattice cryptanalysis ever breaks ML-KEM, the hybrid scheme remains secure because of the HQC-128 component. If somehow code-based cryptanalysis improves enough to threaten HQC-128, the hybrid scheme remains secure because of ML-KEM-512.
This pattern matches NSA's CNSA 2.0 guidance for high-stakes applications. NIST has also acknowledged hybrid usage as a transitional approach during the migration to post-quantum cryptography.
For more on hybrid encryption, see Hybrid Encryption.
Comparison to Classic McEliece
Classic McEliece is also a code-based KEM that NIST considered. It uses Goppa codes with extensively studied parameters.
Classic McEliece public keys are dramatically large. The smallest parameter set has a public key over 250 KB. Some parameter sets exceed 1 MB. This is impractical for most deployments.
Classic McEliece ciphertexts are much smaller, typically under 200 bytes.
HQC-128 strikes a different balance. Public keys around 2 KB, ciphertexts around 4.5 KB. Larger ciphertexts than McEliece, dramatically smaller public keys.
NIST selected HQC over Classic McEliece for new deployments because the public key size of McEliece is too costly for most applications. McEliece remains a candidate for specific niche applications where the public key can be distributed once and the ciphertext travels often.
QNSQY Implementation
QNSQY's Business tier exposes HQC-128, HQC-192, and HQC-256. Free and Pro tiers offer ML-KEM only. The Business tier is the appropriate choice for users who want code-based KEM availability for hybrid encryption schemes or for defense in depth.
The QNSQY CLI accepts HQC-128 as a KEM choice on encryption operations. Internally, QNSQY uses the HQC reference implementation, which has been validated against NIST's published test vectors for HQC.
When a QNSQY user encrypts a file with HQC-128, the resulting QNSQY envelope contains the HQC ciphertext (4,481 bytes plus envelope metadata) and an AES-256-GCM-encrypted payload. The total overhead from HQC-128 versus ML-KEM-512 is roughly 3.7 KB per encrypted file.
For more on QNSQY's algorithm support, see HQC Explained.
Constant-Time Decoding
A subtle point in HQC implementation is that the decoding procedure must be constant-time to avoid side-channel leaks. Naive decoding implementations can leak information about the secret key through timing or cache behavior.
The reference HQC implementation includes constant-time decoding routines. Implementers building their own HQC must ensure they use the constant-time pathways throughout. This is similar to the constant-time requirements for other post-quantum schemes, but the decoding-specific aspects of HQC make it a particular concern.
QNSQY's HQC implementation uses the reference constant-time decoding. Auditors have validated the implementation against side-channel test vectors.
Failure Probability
Code-based KEMs have a small but non-zero probability that decapsulation fails to recover the message correctly. The failure occurs when the noise added during encapsulation pushes the ciphertext outside the decoding radius.
For HQC-128, the failure probability is bounded at roughly 2 to the negative 128. This is small enough to be ignorable for any practical purpose. Even at internet scale with billions of operations per day, the chance of any decapsulation failure is essentially zero.
When a failure does occur in theory, the receiver detects the failure through internal consistency checks and can request a retry. The receiver does not return an error to the encapsulator that would let the encapsulator distinguish failure from success, which is important for IND-CCA security.
Verification Against NIST KAT
NIST published Known Answer Tests for HQC as part of its standardization process. These tests provide deterministic input/output pairs that any compliant HQC implementation must reproduce exactly.
QNSQY's HQC implementation passes all NIST KAT tests. This validation confirms the implementation behaves correctly for the specific test vectors. Production users can be confident that the HQC implementation is interoperable with other compliant implementations.
For more on FIPS validation, see NIST FIPS Guide.
Side-Channel Hardening
HQC implementations require careful attention to side-channel resistance. The decoding procedure used during decapsulation involves operations that can leak information about the secret key through timing or cache behavior if implemented naively.
The reference HQC implementation includes constant-time decoding routines that QNSQY uses. Implementers building their own HQC must use constant-time pathways throughout. Side-channel testing should be part of any production HQC deployment validation.
Specific side-channel concerns for HQC include:
- Timing variance in the BCH decoder used during decapsulation
- Cache-based side channels in syndrome computation
- Power analysis vulnerabilities in noise sampling
The reference implementation addresses each of these concerns. Production deployments inherit this protection. Custom implementations must address each concern explicitly.
NIST Round 4 History
HQC was a Round 4 candidate in NIST's PQC standardization process. Round 4 began in July 2022 after the initial KEM selection that picked Kyber as the primary KEM. Four candidates entered Round 4: Classic McEliece, BIKE, HQC, and SIKE.
SIKE was broken in August 2022 by Castryck and Decru's attack on the supersingular isogeny problem. This eliminated SIKE from contention.
The remaining three Round 4 candidates underwent continued analysis. NIST announced HQC's selection as the standardized code-based KEM in March 2025. The decision reflected HQC's combination of practical key sizes, performance characteristics, and security analysis depth.
For more on the standardization process, see NIST FIPS Guide.
Defense in Depth Strategy
The most compelling reason to deploy HQC-128 is as part of a defense in depth strategy. Pair ML-KEM-512 with HQC-128 in a hybrid scheme. Both KEMs run independently. The final shared secret is derived from both individual shared secrets via a KDF.
The cost is approximately 5 KB additional ciphertext per encryption operation (ML-KEM-512 ciphertext plus HQC-128 ciphertext). For files larger than a few hundred KB, this is rounding error. For tiny messages, the overhead is more visible but usually still acceptable.
The benefit is that no single mathematical foundation can compromise the encryption. Lattice cryptanalysis breakthroughs do not affect the HQC component. Code-based cryptanalysis breakthroughs do not affect the ML-KEM component. Both would have to fail simultaneously for the hybrid scheme to be at risk.
This pattern is what NIST and NSA recommend for high-stakes deployments during the post-quantum migration period.
FAQ
Is HQC-128 secure against quantum computers?
Yes. The security of HQC rests on the hardness of decoding random quasi-cyclic codes, which has resisted both classical and quantum analysis for decades. NIST classifies HQC-128 at Category 1, equivalent to AES-128 brute-force resistance against quantum adversaries.
How does HQC-128 compare to McEliece in production deployments?
HQC-128 has dramatically smaller public keys (2.2 KB vs 250 KB for the smallest McEliece). HQC-128 has larger ciphertexts (4.5 KB vs 100-200 bytes for McEliece). For most deployments, HQC's compact public key wins.
Can HQC-128 replace ML-KEM-512 outright?
In principle yes. In practice, ML-KEM-512 remains the recommended primary KEM because of its smaller sizes and faster performance. HQC-128 is the recommended backup or hybrid component.
Does HQC-128 support batch encapsulation?
Yes. Batch operations process multiple encapsulations concurrently and amortize some setup costs. The performance gain is modest, in the 10-30 percent range depending on batch size.
What random number generator does HQC-128 require?
NIST recommends SP 800-90A approved generators. QNSQY uses the OS-provided cryptographic random number generator, which on modern systems is hardware-backed.
Sources
- NIST PQC Project: HQC Selection Announcement
- HQC Round 4 Specification, NIST PQC Project
- NIST FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard
- NIST PQC KAT Test Vectors
- IACR Cryptology ePrint Archive: HQC Cryptanalysis
Related Articles
Protect Your Data Before Q-Day Arrives
QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats.