BIKE and HQC: Code-Based Post-Quantum Cryptography with Practical Key Sizes

What Problem Do BIKE and HQC Solve?

Classic McEliece has a 45-year security track record but requires 524,160-byte public keys for 128-bit security. ML-KEM-512 provides 128-bit security with 800-byte public keys. The gap is 655x. BIKE and HQC are code-based key encapsulation mechanisms that attempt to close this gap by using quasi-cyclic codes instead of random Goppa codes, at the cost of introducing algebraic structure that requires additional cryptanalysis.

Both schemes were submitted to NIST's post-quantum standardization process and advanced to Round 4 (announced March 2022) as backup candidates. They are not yet standardized. NIST is continuing evaluation to determine whether they will receive a formal standard, with publication expected in the 2025 to 2026 timeframe. They represent the most viable path to code-based post-quantum cryptography with practical key sizes.

For context on where these schemes sit in the broader standardization landscape, the NIST PQC standards overview covers the primary standards (ML-KEM, ML-DSA, SLH-DSA) and the relationship between primary and backup candidates.

BIKE: Bit Flipping Key Encapsulation

BIKE (Bit Flipping Key Encapsulation) is based on quasi-cyclic moderate density parity check (QC-MDPC) codes. QC-MDPC codes have a parity check matrix with a specific quasi-cyclic structure: the matrix consists of circulant blocks, where each block is a cyclic rotation of a single row. This structure allows the entire matrix to be described by one row per block, dramatically reducing the key size.

BIKE's security reduces to two problems: the decoding problem for QC-MDPC codes, and the syndrome decoding problem for quasi-cyclic codes. The quasi-cyclic structure is what enables small keys. It is also what introduces algebraic structure that might be exploitable.

BIKE uses a two-key construction: public and private keys each consist of two circulant polynomials. The public key is compact: for BIKE-L1 (128-bit security), the public key is 1,541 bytes. The ciphertext is 1,573 bytes. Compare this to McEliece-460896's 524,160-byte public key and 188-byte ciphertext. BIKE's total transmission cost (public key plus ciphertext) is 3,114 bytes vs McEliece's 524,348 bytes.

BIKE Parameter Sets and Security Levels

BIKE defines three security levels:

• BIKE-L1: NIST Level 1 (128-bit classical security). Public key: 1,541 bytes. Ciphertext: 1,573 bytes. Private key: 281 bytes.
• BIKE-L3: NIST Level 3 (192-bit classical security). Public key: 3,083 bytes. Ciphertext: 3,115 bytes. Private key: 417 bytes.
• BIKE-L5: NIST Level 5 (256-bit classical security). Public key: 5,122 bytes. Ciphertext: 5,154 bytes. Private key: 580 bytes.

BIKE uses a Black-Gray-Flip decoder for error correction. The decoder is probabilistic: it has a nonzero decryption failure rate (DFR) on the order of 2^-128 for the BIKE-L1 parameter set. This DFR must be accounted for in security proofs, and it creates a subtle security concern: an adversary who can trigger and observe decryption failures might extract information about the private key. BIKE's current submission addresses this through a transform that converts the scheme to IND-CCA2 security even in the presence of decryption failures.

HQC: Hamming Quasi-Cyclic

HQC (Hamming Quasi-Cyclic) is based on the hardness of decoding random quasi-cyclic codes in the Hamming metric. The Hamming metric measures code distance as the number of positions where two codewords differ, the standard metric in classical coding theory.

HQC's public key is a quasi-cyclic code description: two polynomials in the ring Z_2[x]/(x^n - 1) where n is chosen to be prime for the desired security level. Private key polynomials are sparse (low Hamming weight), which enables efficient decoding. Public key polynomials are random-looking, which prevents an attacker from recovering the sparse structure.

HQC parameter sets at Level 1:

• HQC-128: NIST Level 1 (128-bit security). Public key: 2,249 bytes. Ciphertext: 4,497 bytes. Private key: 40 bytes.
• HQC-192: NIST Level 3. Public key: 4,481 bytes. Ciphertext: 8,961 bytes. Private key: 40 bytes.
• HQC-256: NIST Level 5. Public key: 7,245 bytes. Ciphertext: 14,469 bytes. Private key: 40 bytes.

HQC has larger ciphertexts than BIKE and ML-KEM but has a cleaner security reduction to the quasi-cyclic syndrome decoding problem. It also achieves a negligible decryption failure rate by design, unlike BIKE which manages DFR through parameterization. The private key is remarkably small (40 bytes) because it is just two sparse polynomial seeds.

IND-CCA2 Security and Why It Matters

IND-CCA2 (Indistinguishability under Chosen Ciphertext Attack 2) is the standard security model for key encapsulation mechanisms. An IND-CCA2 secure KEM remains secure even if an adversary can submit arbitrary ciphertexts for decryption and observe the results, subject to not submitting the challenge ciphertext itself.

This security level is necessary for any KEM used in practice. An IND-CPA secure scheme (secure against passive adversaries only) is not sufficient for TLS or any protocol where an active adversary can trigger decryption operations. Both BIKE and HQC claim IND-CCA2 security via the Fujisaki-Okamoto transform, which converts IND-CPA secure schemes to IND-CCA2 by adding a hash check on the decrypted message.

For BIKE, the FO transform requires that the decryption failure rate be negligible to avoid known attacks. The 2020 paper by Guo, Johansson, and Nilsson demonstrated that non-negligible DFR in BIKE allows key recovery attacks. The current BIKE specification uses parameters where the DFR is below 2^-128, which makes the attack infeasible but required parameter increases from earlier rounds.

Why BIKE and HQC Are Backup Candidates, Not Primary Standards

NIST's rationale for keeping BIKE and HQC as backup candidates rather than advancing them to primary standards in the first wave is explicitly stated in the Round 4 announcement: "the security of these systems is somewhat less well understood than the lattice-based schemes."

Lattice-based schemes (ML-KEM, ML-DSA) have security reductions to worst-case lattice problems that have been studied since the 1980s. The Module-LWE problem underlying ML-KEM has been analyzed by hundreds of researchers over more than a decade. The algebraic structure of quasi-cyclic codes in BIKE and HQC has been analyzed for a shorter period, and the attack surface introduced by that structure is less thoroughly mapped.

Additionally, BIKE's DFR-related attack history and the requirement to bound the failure rate carefully add complexity to security arguments that ML-KEM does not have. ML-KEM has a negligible decryption failure rate by construction, not by parameterization.

For the same reasons that Classic McEliece was not selected as a primary standard (practical constraints), BIKE and HQC are retained as backups to provide algorithmic diversity if lattice problems are weakened.

Comparing BIKE, HQC, and ML-KEM Side by Side

For a concrete comparison at NIST Level 1 (128-bit security):

• ML-KEM-512: Public key 800 bytes, ciphertext 768 bytes, total 1,568 bytes. Primary standard. Mature security analysis.
• BIKE-L1: Public key 1,541 bytes, ciphertext 1,573 bytes, total 3,114 bytes. Round 4 backup. Code-based. DFR management required.
• HQC-128: Public key 2,249 bytes, ciphertext 4,497 bytes, total 6,746 bytes. Round 4 backup. Code-based. Larger ciphertext than BIKE or ML-KEM.
• Classic McEliece-460896: Public key 524,160 bytes, ciphertext 188 bytes. Not advanced as backup (key sizes). 45-year security track record.

ML-KEM wins on key size and ciphertext size at comparable security levels. BIKE and HQC win on key size compared to Classic McEliece. The value proposition for BIKE and HQC is algorithmic diversity: a deployment that runs ML-KEM-512 for performance and BIKE-L1 as a backup layer has defense in depth against lattice breakthroughs.

Relevance for Blockchain and Post-Quantum Migration

BIKE and HQC are not yet standardized, so production blockchain deployments should use ML-KEM for key encapsulation and ML-DSA for transaction signing today. However, a cryptographically agile blockchain architecture should design its key management layer to accommodate future code-based KEMs if NIST standardizes BIKE or HQC.

Concretely, this means: key registration transactions should include a version byte that identifies the KEM algorithm, so nodes can begin advertising BIKE-L1 or HQC-128 public keys alongside ML-KEM-768 keys when those standards finalize. Transport-layer encryption should use negotiated algorithm identifiers so peers can use the best mutually supported scheme.

For on-chain signing (transaction authorization), ML-DSA remains the correct choice regardless of what happens with code-based KEMs, because BIKE and HQC are key encapsulation mechanisms, not signature schemes. The distinction between signing and key exchange is discussed in detail in the ML-KEM explainer. Designing for cryptographic agility now avoids hard migrations later when the standardization landscape evolves.

Summary

BIKE and HQC are NIST Round 4 backup candidates for post-quantum key encapsulation, based on quasi-cyclic code decoding hardness. BIKE-L1 achieves 1,541-byte public keys (vs McEliece's 524KB) by using QC-MDPC codes. HQC-128 uses 2,249-byte public keys with a cleaner decryption failure rate profile. Neither is yet standardized. Both are smaller than McEliece but larger than ML-KEM-512 (800 bytes). Their role is to provide algorithmic diversity beyond lattice-based schemes. Production deployments should use ML-KEM today and design for BIKE or HQC as a future backup layer when NIST completes standardization.