HQC: Why NIST's Backup KEM Belongs in Your Crypto-Agility Plan Now

Brian Couzens

2 minutes ago

9 min read

HQC mathematical construction on dark navy, showing key generation, encryption and decryption for NIST backup KEM.

NIST selected HQC (Hamming Quasi-Cyclic) as the backup Key Encapsulation Mechanism for post-quantum cryptography. It is built on code-based cryptography, not lattice mathematics. The final IR 8547 names it by standard. This article examines what HQC is, why a backup KEM matters for key establishment, what it does and does not cover, and why controlled testing belongs in crypto-agility planning now, not after a lattice compromise forces the question.

NIST has already selected the backup

In March 2025 NIST announced the selection of HQC as the fifth post-quantum cryptographic algorithm. The four already standardised are ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism, FIPS 203), ML-DSA (Module-Lattice-Based Digital Signature Algorithm, FIPS 204), and SLH-DSA (Stateless Hash-Based Digital Signature Algorithm, FIPS 205). HQC was selected explicitly as a backup to ML-KEM for key establishment.

The final publication of NIST IR 8547, "Transition to Post-Quantum Cryptography Standards", makes that status formal. HQC is named as the backup Key Encapsulation Mechanism, with its own FIPS standard under development. That is not a research recommendation. It is a standards body stating that it has planned for the failure of its primary selection.

The distinction matters. A research recommendation asks organisations to watch. A selection tells them to plan.

Most PQC migration programmes written in 2024 and 2025 specify ML-KEM as the key-establishment mechanism and leave it at that. Some mention "crypto-agility" as a principle without naming what the programme would substitute if ML-KEM were withdrawn. Organisations whose PQC migration programmes specify ML-KEM as the sole key-establishment mechanism now have a standards body on record saying that a backup exists and belongs in the transition plan. The question for every programme owner is whether their plan accounts for it.

Why a backup KEM matters

ML-KEM is lattice-based. Its security rests on the Module Learning with Errors (MLWE) problem. ML-DSA, the primary post-quantum signature algorithm, is also lattice-based, relying on the same mathematical family.

That means a sufficiently broad advance in lattice cryptography could affect both the primary key-establishment mechanism and the primary signature algorithm at the same time. The concern is not a specific known attack. It is concentration risk: the same mathematical family underpinning two of the three primary standards.

Risk managers in financial services and critical infrastructure will recognise the pattern. Single-supplier risk, single-technology risk, single-point-of-failure risk. The same principle that drives dual-vendor procurement and geographic redundancy applies to the mathematical assumptions underpinning cryptographic protection. Betting the entire post-quantum transition on one family of hard problems is not conservative. It is concentrated.

The sovereign algorithms debate across national standards bodies reflects the same structural worry at policy level. Several jurisdictions are already evaluating whether to mandate algorithmic diversity in their own PQC transitions, precisely because lattice-only strategies leave no room for substitution.

HQC provides a different mathematical foundation for key establishment. It is built on code-based cryptography, a family of hard problems that is mathematically independent of lattices. If a lattice breakthrough were to compromise ML-KEM, it would not, by that fact alone, compromise HQC. Algorithmic diversity is a governance position, not a theoretical luxury. The ongoing research into lattice vulnerability reinforces this.

That does not make HQC a drop-in replacement. It is a backup from a different mathematical family, selected to provide exactly the algorithmic diversity that a single-family approach lacks. An organisation running a cryptographic modernisation programme that cannot substitute its primary KEM is not agile. It is locked in. The entire rationale for crypto-agility is that algorithm choices may need to change. A programme that treats its first choice as permanent has adopted a technology. It has not built a capability.

What HQC is

HQC is a key-encapsulation mechanism built on the Quasi-Cyclic Syndrome Decoding (QCSD) problem. Where ML-KEM works with structured lattices, HQC works with quasi-cyclic codes over a binary polynomial ring.

The algebraic structure is the ring R = F2[X]/(X^n - 1), where n is prime. Operations in this ring are polynomial multiplication and addition modulo 2, with the quasi-cyclic structure providing compact keys through algebraic regularity.

The construction has its roots in coding theory research dating to the 1970s. The McEliece cryptosystem, proposed in 1978, established the principle that decoding a random linear code is computationally hard. HQC builds on that foundation with a different construction that produces smaller keys than the original McEliece approach while retaining the core property: security rests on a coding-theory problem, not a lattice problem. That gives HQC a longer history of cryptanalytic scrutiny than the lattice-based schemes, and mathematical independence from them.

Key generation

A key pair is generated by sampling two sparse secret vectors (x, y) of fixed Hamming weight w from the ring R, then sampling a uniform random element h from R. The public key is the pair (h, s), where s = x + h * y. The private key is (x, y).

Encryption

To encrypt a message m, the sender samples three fresh sparse vectors (r1, r2, e) from R and computes two ciphertext components. The first is u = r1 + h r2. The second is v = C.Encode(m) + pi(s r2 + e), where C is a concatenated error-correcting code and pi is a fixed public mapping.

The code C is a concatenation of Reed-Solomon and duplicated Reed-Muller codes, designed to tolerate the noise introduced during encryption.

Decryption and noise cancellation

Decryption recovers the message as m' = C.Decode(v - pi(u y)). The algebraic cancellation is the mechanism that makes this work. In the commutative ring R, the terms h y r2 and h r2 * y are equal, so the dominant noise cancels. What remains is a sparse noise term that the concatenated code is designed to correct.

The security assumption is that an attacker who sees (h, s) cannot recover the sparse secret vectors (x, y). That is the QCSD problem: given a quasi-cyclic parity check matrix and a syndrome, find a low-weight error vector. The key sizes involved are larger than ML-KEM. At the 128-bit security level, HQC public keys are approximately 2,249 bytes and ciphertexts approximately 4,497 bytes, compared to ML-KEM-768's 1,184-byte public key and 1,088-byte ciphertext. That size difference is a practical consideration for bandwidth-constrained environments, and one reason why controlled testing matters before any production deployment.

What HQC does not cover

HQC is a key-encapsulation mechanism. It addresses key establishment: the problem of two parties agreeing a shared secret over an untrusted channel. It does not provide digital signatures.

The lattice concentration risk in signatures has its own mitigation. SLH-DSA (FIPS 205) is a hash-based signature algorithm, already standardised, that is independent of both lattice and code-based assumptions. It relies on hash function security. An organisation concerned about lattice risk in signatures already has a standardised option.

But HQC and SLH-DSA cover different jobs. A crypto-agility plan that includes HQC for key establishment but assumes ML-DSA for signatures without a stated fallback has addressed only half the concentration risk. Signature contingency requires its own plan.

The TLS 1.3 hybrid handshake illustrates this split clearly. Post-quantum key exchange, using the hybrid X25519MLKEM768 mechanism, is already deployed in current browsers. Post-quantum authentication, the certificate and handshake signature, is a separate and slower migration. HQC would sit on the key-exchange side of that divide, as a backup to ML-KEM, not as a replacement for the signature algorithms.

The FIPS development timeline

HQC's FIPS standard is still under development. NIST has selected the algorithm but has not yet published the draft standard. That means HQC is not ready for production deployment in environments that require FIPS-validated modules.

For organisations operating under FIPS 140-3 requirements, this creates a sequencing constraint. ML-KEM already has a FIPS standard (FIPS 203) and modules are working through validation. HQC does not yet have a standard to validate against. Including HQC in a production environment before the standard is published introduces an algorithm that has no validation pathway.

That constraint does not mean HQC should be ignored until the standard lands. It means the work that can be done now is different from production deployment. This is discovery, inventory, and controlled testing, not rollout. The organisation that waits for the FIPS standard before examining HQC at all will then face simultaneous pressure to learn the algorithm, test it, validate it, and deploy it. That is the compressed timeline pattern that has driven cost overruns and governance failures in every previous cryptographic transition.

Why controlled testing belongs in the plan now

The argument for including HQC in crypto-agility planning now rests on a straightforward operational principle. If substitution is needed urgently, the organisation that has already mapped HQC's deployment points, tested it in controlled conditions and documented its behaviour will substitute faster than one that begins discovery under pressure.

Cryptographic agility is not a theoretical property of a system. It is an operational capability that can be tested. A programme that specifies ML-KEM but has never tested what happens when a different KEM is substituted has not demonstrated agility. It has demonstrated adoption.

The difference between deploying PQC and proving it works applies equally to backup planning. A handshake log showing one successful HQC exchange in a laboratory is not evidence of readiness. Evidence means a documented substitution path, tested at each point where TLS terminates, with the results independently recorded. That is what cryptographic assurance means in practice: not a claim about what can be done, but a record of what has been done.

The practical test is direct. Scan the PQC transition plans circulating across financial services, critical infrastructure and government programmes. Count how many mention HQC by name. Count how many have mapped where it would deploy if ML-KEM were withdrawn. Count how many have tested a single handshake with it. The PQC Baker's Dozen documents the common failure to plan for algorithm substitution. Organisations that assume the first algorithm choice is permanent are building fragility into their modernisation programmes. The point of selecting a backup is that the backup might be needed. Planning for its use is not pessimism. It is due diligence.

The harvest now, decrypt later threat model already drives urgency for ML-KEM deployment. If the lattice foundation of ML-KEM were compromised, the same urgency would apply to substitution. An organisation that has never tested its backup KEM would face simultaneous pressure to deploy an untested algorithm while decommissioning a compromised one. That is not a resilience posture. It is a gap waiting for a trigger.

What to do now

First, name HQC in the programme. If the PQC migration plan or cryptographic modernisation programme does not mention HQC, it does not have a substitution plan for its primary KEM. Add it. The governance-first approach to PQC transformation requires that every primary algorithm has a documented contingency.

Second, map the substitution points. Identify every point in the estate where ML-KEM is deployed or planned, and document what would change if HQC were substituted. That means TLS termination points, VPN gateways, key management systems, HSM firmware, and any protocol that negotiates a shared secret. The exercise is the same discovery discipline that should already be running for the primary migration. If that discipline is not running, a PQC readiness assessment establishes where the programme stands before controlled testing begins.

Third, test in controlled conditions. Stand up a non-production environment and run HQC handshakes through the same path that production traffic follows. Log which libraries support it, which devices and middleboxes pass or fail, and what the key size differences do to latency and throughput. HQC ciphertexts at the 128-bit security level are approximately four times the size of ML-KEM-768 ciphertexts. That difference matters for constrained environments, high-frequency trading links, and any path with tight MTU constraints. A hybrid pilot that tests HQC produces evidence, not just experience. That evidence is what an auditor, regulator or acquirer can examine.

Fourth, track the FIPS timeline. When NIST publishes the draft HQC standard, the validation clock starts. Organisations that have already tested HQC's behaviour will move to validated modules faster. Those that start testing after the standard is published will find themselves on the same compressed timeline that every late adopter faces. The ML-KEM validation queue already demonstrates how long FIPS module validation takes. Adding an untested algorithm to that queue, under time pressure, compounds delay with unfamiliarity.

Fifth, address signatures separately. HQC covers key establishment. For signature diversity, evaluate SLH-DSA. Do not treat HQC as addressing the full lattice concentration risk when it covers only half of it.

Sixth, check interoperability before assuming it. Middleboxes, inspection appliances and TLS-terminating load balancers that handle ML-KEM handshakes today may not pass HQC handshakes. The experience with ML-KEM deployment has already shown that middlebox ossification breaks handshakes that exceed expected sizes. HQC's larger ciphertexts will surface the same class of failure. The only way to know where is to test. Record the results, because that record is the operational evidence that turns a plan into a capability.

The case in one line

NIST has selected a backup to ML-KEM, built on different mathematics, for a reason. An organisation whose PQC migration plan specifies ML-KEM but cannot explain how it would replace it has an adoption plan. It has not yet demonstrated cryptographic resilience.

The board question is direct: if ML-KEM were compromised tomorrow, how long would it take this organisation to substitute a backup KEM across its estate? If the answer is "we have not tested that", then the programme that reports completion is reporting adoption, not agility. That gap is tested independently by the Quantum Cryptographic Assurance Standard. Include HQC in crypto-agility planning and controlled testing now, while the cost of preparation is low and the cost of unpreparedness has not yet been set by events.

About the author

Brian Couzens is CEO of SITG-Consulting, an independent advisory firm working on post-quantum cryptography governance, cryptographic risk and board-level assurance across financial services, critical infrastructure and government. SITG-Consulting is vendor-independent and holds no product vendor partnerships. Services include Cryptographic Agility Services and Quantum Trust PQC Assurance.

SITG-CONSULTING