HQC and BIKE: Quasi-Cyclic Codes, the Backup-KEM Decision, and Decoding-Failure Trade-offs

The conservatism of Classic McEliece comes with a megabyte public key, which rules it out for most everyday use. The schemes in this article — HQC and BIKE — recover practicality by giving their codes quasi-cyclic structure, shrinking the key from hundreds of kilobytes to a few kilobytes while keeping the security rooted in the hardness of decoding. That structure introduces a new subtlety, the decoding-failure rate, which behaves much like the lattice decapsulation failure and opens a reaction-attack surface. How each scheme handles that failure rate is exactly what decided the 2025 selection of a non-lattice backup key mechanism, and it is the thread of this article.

Quasi-cyclic codes shrink the key

The reason Classic McEliece's key is enormous is that a random-looking matrix over its dimensions is simply large, and it declines to add structure that could be attacked. Quasi-cyclic codes take the opposite bet: they build the matrix from cyclic blocks — circulants — each of which is completely determined by its first row, so the whole matrix can be described by a handful of rows rather than stored in full. A circulant block is a polynomial, and operations on it are polynomial arithmetic, compact to represent and fast to compute.

This compression is dramatic: keys drop from hundreds of kilobytes to a few kilobytes, bringing code-based cryptography into the size range where it can plausibly be used per connection rather than only for provisioned static keys. The security still rests on decoding hardness, but now on the hardness of decoding quasi-cyclic codes specifically, a more structured and therefore somewhat less conservative assumption than decoding fully random codes. It is the same trade the ring and module lattices made against plain lattices: structure for size, at some cost in generality.

The quasi-cyclic assumption is still believed hard and has been studied substantially, but it is younger and more structured than the McEliece assumption, so these schemes sit between Classic McEliece's maximal conservatism and the lattice schemes' efficiency. They are the practical face of code-based cryptography, and their viability turns on managing the decoding-failure subtlety that the structure and their specific decoders introduce.

HQC: a public decoder and a clean failure story

HQC — Hamming Quasi-Cyclic — is designed so that its decoder is public and fixed, which is the key to its clean security analysis. Unlike McEliece, where the decoder is the secret and must be hidden, HQC uses a publicly known error-correcting code purely to recover from a controlled amount of noise, and derives its hardness entirely from a quasi-cyclic syndrome-decoding assumption layered on top. Because the decoder is public and its behavior fully understood, the probability that decoding fails can be computed and driven provably below any target — there is no hidden, hard-to-analyze decoder whose failure behavior is uncertain.

This provable, negligible decoding-failure rate is HQC's decisive virtue. The scheme is an actively secure key-encapsulation mechanism built with the same kind of transform that hardens the lattice mechanism, and the security proof, like that one, has a term proportional to the decoding-failure probability; because HQC can make that probability provably tiny, the proof is tight and the reaction-attack surface is closed by design. The price is that HQC's keys and ciphertexts, while kilobytes rather than megabytes, are somewhat larger than the most aggressive quasi-cyclic alternative.

The design philosophy is to keep everything that affects security analyzable. By making the decoder public and the failure rate computable, HQC trades a little size for a great deal of analytic confidence, which is exactly what a backup meant to be trusted as an independent hedge should prioritize. Its structure is more than McEliece's but its failure story is cleaner than its quasi-cyclic sibling's, as the next section shows.

BIKE and the decoding-failure-rate problem

BIKE — Bit Flipping Key Encapsulation — takes the more aggressive size route. Its secret is a sparse quasi-cyclic parity-check matrix, and it decodes using an iterative bit-flipping algorithm that is fast and enables even smaller keys than HQC. The catch is that the bit-flipping decoder's failure behavior is not fully characterized: unlike HQC's public decoder, this secret-dependent iterative decoder has a decoding-failure rate that is genuinely difficult to compute exactly, and that depends on the secret in ways an attacker can exploit.

This matters because the decoding-failure rate is a security surface, not merely a reliability nuisance. It is the code-based analogue of the lattice decapsulation failure: a failure is correlated with the secret key, so an attacker who can provoke and observe failures learns information about the secret, and enough observed failures reconstruct it — a reaction attack directly parallel to the failure-boosting attacks on lattice schemes. Because a failure leaks the secret, the failure rate for an actively secure scheme must be driven provably far below any feasible number of queries, and static keys that let failures accumulate are especially dangerous while ephemeral keys mitigate the risk.

The difficulty with BIKE is precisely that bounding its failure rate rigorously is hard. The iterative decoder resists exact analysis, so establishing that its failure rate is negligibly small enough for active security, across all secrets, has been a persistent challenge. The scheme is attractive for its size, but the uncertainty in its failure analysis is a real liability for a scheme that must be trusted as a conservative backup, and it is the crux of the comparison with HQC.

The 2025 backup-KEM decision

When the standardization process selected a non-lattice backup key mechanism in 2025, it chose HQC over BIKE, and the decoding-failure story was central to the decision. HQC's public decoder and provably negligible failure rate give it a tight security proof and a closed reaction surface, whereas BIKE's harder-to-bound failure rate left more analytic uncertainty. Faced with choosing the scheme that would serve as the trusted independent hedge against a lattice break, the process favored the one whose security could be established most cleanly, even at the cost of somewhat larger keys and ciphertexts.

The table lays out the trade. Classic McEliece has the most conservative assumption but an impractical key; HQC has kilobyte-scale keys, a more structured but studied assumption, and a provable failure bound; BIKE has the smallest keys but the least settled failure analysis. The selection of HQC reflects a preference, for a backup, of analyzable security over minimal size — the same conservatism that runs through the whole code-based family, applied to the choice between two quasi-cyclic options.

For autonomous AI systems the practical consequence is that there is now a standardized non-lattice key mechanism whose size makes it usable, unlike Classic McEliece, in per-connection settings. HQC's kilobyte keys and ciphertexts, while larger than the lattice mechanism's, are within reach for agent and model channels that want assumption diversity, and its provable failure bound means it can be deployed with ephemeral keys under the same active-security discipline as the lattice scheme. The guidance is that where diversity is wanted for durable or high-stakes key establishment, HQC is the standardized independent hedge to reach for, deployed with the ephemeral-key and failure-aware discipline this article's analysis implies — while Classic McEliece remains the choice only where its extreme conservatism justifies its extreme key size.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

non_lattice_backup_kem:
  selected: hqc               # 2025 backup, provable failure bound
  decoder: public_analyzable
  decoding_failure_rate: provably_negligible
  key_mode: ephemeral
  reaction_surface: closed_by_bound
alternatives:
  bike: smaller_but_failure_harder_to_bound
  classic_mceliece: extreme_conservatism_large_key

Glossary

Quasi-cyclic code

A code whose matrix is built from cyclic blocks (circulants), each determined by one row, giving compact keys at the cost of more structure.

HQC (Hamming Quasi-Cyclic)

A code-based KEM using a public fixed decoder and a quasi-cyclic hardness assumption, with a provably negligible decoding-failure rate; selected as the 2025 non-lattice backup.

BIKE (Bit Flipping KEM)

A quasi-cyclic scheme with a sparse secret and an iterative bit-flipping decoder giving small keys but a hard-to-bound failure rate.

Decoding-failure rate (DFR)

The probability that decoding fails; a secret-correlated security surface enabling reaction attacks, which must be driven provably negligible.

Reaction attack

Provoking and observing decoding failures to learn the secret, the code-based analogue of lattice failure-boosting.

Public versus secret decoder

HQC's decoder is public and analyzable; BIKE's is secret and iterative, which is why their failure analyses differ so sharply.

References

1. NIST IR 8545, Status Report on the Fourth Round of the NIST PQC Standardization Process (2025)
2. HQC submission specification
3. BIKE submission specification
4. Berlekamp, McEliece & van Tilborg, On the Inherent Intractability of Certain Coding Problems (IEEE Trans. Information Theory, 1978)
5. NIST FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard (2024)