# Code-Based Post-Quantum Cryptography: Future Beyond HQC **Source**: https://quantumsequrity.com/blog/code-based-pqc-future **Category**: Future Research --- [← Back to Blog](../../blog.html) Future Research # Code-Based Post-Quantum Cryptography: Future Beyond HQC 11 min read Code-based cryptography has the longest cryptanalytic record in post-quantum cryptography. Classic McEliece, the foundational scheme, was proposed in 1978 and has resisted nearly 50 years of analysis with no fundamental break. NIST selected HQC for FIPS standardisation in March 2025 (NIST IR 8528), giving the family its first standard general-purpose KEM. But the code-based research community has more in the pipeline. New code families, new attacks, new constructions are all in flight. This article walks through the state of code-based cryptography after the HQC selection and where the field is heading. ## What Code-Based Cryptography Does The family is built on error-correcting codes. The basic idea: take a structured code that is easy to decode if you know its structure, and disguise it so that decoding looks random to anyone who does not know the structure. Encryption hides a message in random-looking codewords. Decryption uses the secret structure to recover the message. The original McEliece scheme uses Goppa codes. Subsequent variants use different code families: - **Goppa codes**: McEliece original. Strong security record, large public keys (1 MB). - **Reed-Solomon codes**: Niederreiter variants. Most have been broken. - **Reed-Muller codes**: McEliece variant. Broken. - **Algebraic geometry codes**: Various proposals. Some broken, some standing. - **Quasi-cyclic codes**: BIKE, HQC, RQC. Smaller keys, more complex security analysis. - **Quasi-dyadic codes**: Reduced key size variants of Goppa McEliece. Some broken. - **Rank metric codes**: Different distance metric than Hamming. Active research area. The trade-off is consistent: more structure means smaller keys but easier-to-attack constructions. Goppa McEliece has the most conservative parameters but huge keys. Quasi-cyclic schemes have small keys but more complex security. For background on what NIST selected, see [NIST Round 4 Status](nist-round-4-status.html) and [HQC Explained](hqc-explained.html). ## Why HQC Was Selected and What That Means NIST IR 8528 (March 2025) selected HQC for standardisation as a non-lattice KEM. The selection rationale: - **No decoding failure issues** like BIKE. - **Easier to implement constant-time** than BIKE or Classic McEliece. - **Reasonable parameters**: Public keys around 7 KB, ciphertexts around 14 KB. Workable for most deployment scenarios. - **Code-based diversity**: NIST gets a non-lattice KEM in the standard portfolio. The selection does not end code-based research. NIST kept Classic McEliece in a "conservative deployment" category for niche applications. BIKE remains a viable research scheme. The community continues to study new code families and parameters. ## Active Research Areas Several lines of code-based research continue post-HQC: **Rank metric codes**: Use a different distance measure (rank rather than Hamming). RQC was an early Round 1 candidate. Newer schemes (RYDE, MIRA) submitted to the signature on-ramp use rank-metric problems. The hardness of rank-metric decoding is conjectured to be different from Hamming-metric decoding, providing additional diversity. **LDPC and MDPC code variants**: BIKE uses MDPC (Moderate Density Parity-Check) codes. LDPC (Low Density) variants have been studied for smaller keys. The trade-off is decoding failure rate versus key size. **Goppa code optimisations**: Although Classic McEliece's keys are large, optimised parameter selection and key compression techniques (variations on quasi-cyclic Goppa) could reduce key sizes by 2x to 5x. Some research proposals exist but face cryptanalytic concerns about the added structure. **Code-based signatures**: The signature on-ramp included several code-based candidates: CROSS, LESS, MEDS. Each uses a different code-based hard problem. None has been standardised yet, but they advanced to Round 2 of the on-ramp evaluation. See [NIST Signature On-Ramp](nist-signature-onramp.html). **MPC-in-the-Head signatures**: A general technique that can be applied to code-based assumptions. SDitH and FAEST submissions use this approach for signatures, with security reducing to syndrome decoding. ## Quasi-Cyclic Code Attacks: The GJS Family A persistent concern in quasi-cyclic code-based schemes (BIKE, HQC) is the GJS attack family, named after Guo-Johansson-Stankovski. The attack exploits decoding failures: if the decoder can be made to fail in a way that reveals information about the private key, an attacker who can observe decoding failures (via timing, error messages, or other side channels) can statistically reconstruct the secret. The defence is to set parameters so the Decoding Failure Rate (DFR) is astronomically low, on the order of 2^-128 or 2^-256. BIKE and HQC both target very low DFR. HQC, by design, avoids the failure mode entirely (its construction does not have the same structural weakness as BIKE's bit-flipping decoder). Active research continues on: - Refining DFR estimates for various code families. - Detecting GJS-style attacks early in protocol design. - Constructing schemes that are immune to the entire class of attacks. ## Information Set Decoding: The Attack Bound The classical algorithm for breaking code-based crypto is Information Set Decoding (ISD). The basic ISD algorithm has been refined over decades: - **Prange's algorithm (1962)**: Original. - **Lee-Brickell (1988)**: Improved on Prange. - **Stern's algorithm (1989)**: Better complexity. - **Becker-Joux-May-Meurer (BJMM, 2012)**: Current best practical attack. - **May-Meurer-Thomae (MMT, 2011)**: Variant of BJMM. Each refinement reduces the time complexity of ISD against code-based schemes. Modern parameter selection accounts for the latest ISD variants. Notably, the quantum version of ISD (Bernstein 2010, others) gives a square-root speedup in some regimes, similar to Grover. This is factored into post-quantum parameter selection. The community continues to refine ISD bounds. A surprise breakthrough (a sub-square-root quantum algorithm, or a non-trivial classical improvement) would force re-evaluation of all code-based parameters. Researchers have been searching for such breakthroughs without success for decades, which is why code-based crypto has the longest record. For lattice comparison, see [Lattice-Based Cryptography Explained](lattice-based-cryptography-explained.html). ## Future Directions Looking forward, several research directions are promising: **Sub-cyclic codes**: Codes that are quasi-cyclic with finer block structure, potentially allowing smaller keys without exposing the GJS attack surface. **Hybrid lattice-code schemes**: Constructions that combine lattice and code-based primitives in one scheme, with security relying on either family. None has been standardised, but several research proposals exist. **Post-quantum FE and IBE from codes**: As covered in [PQ Functional Encryption](pq-functional-encryption.html), code-based constructions for advanced primitives are an open area. Most existing constructions are lattice-based, but code-based alternatives could provide diversity. **Smaller signature schemes**: The signature on-ramp candidates CROSS, LESS, MEDS, SDitH are all code-based and aim for niche signature use cases. If standardised, they would join SLH-DSA as the alternative-to-lattice options for signatures. ## Reduction to Hard Problems A common question about code-based crypto is: can the security be reduced to a well-studied hard problem? The answer differs by scheme: **Goppa McEliece**: The security reduces to the hardness of decoding random Goppa codes plus the indistinguishability of Goppa codes from random codes. The first reduces to the Syndrome Decoding Problem (SDP), a well-studied NP-hard problem. The second is a structural assumption that has held for nearly 50 years but is not as rigorously studied. **HQC**: Reduces to the Quasi-Cyclic Syndrome Decoding (QCSD) problem. QCSD is studied less thoroughly than generic SDP because of its structure. NIST evaluators concluded the structural assumption is acceptable for FIPS standardisation. **BIKE**: Reduces to QC-MDPC decoding plus an assumption about the decoding failure rate. The DFR assumption is the harder part and was a focus of NIST's analysis. **Rank metric schemes**: Reduce to rank metric decoding, a less mature hardness assumption. For users evaluating code-based crypto in deployment, the bottom line: Goppa McEliece has the strongest reduction but the largest keys. HQC has acceptable reduction with practical keys. BIKE has acceptable reduction but more complex security analysis. Rank metric schemes are research-grade. ## Implementation Considerations Beyond mathematical security, code-based schemes have implementation considerations that affect deployment: **Constant-time decoding**: HQC's deterministic decoder is straightforward to make constant-time. BIKE's bit-flipping decoder has data-dependent timing in subtle places, making constant-time implementation harder. Classic McEliece's Goppa decoding is straightforward but slow. **Memory usage**: Classic McEliece's 1 MB public key requires careful memory management on constrained devices. HQC and BIKE fit comfortably in standard memory budgets. **Hardware implementations**: Several FPGA implementations of HQC exist with throughput in the tens of thousands of encapsulations per second. ASIC implementations are in early research. **Side-channel resistance**: HQC has been the focus of side-channel analysis since the NIST selection. Several power-analysis and electromagnetic-emission attacks have been published, with corresponding countermeasures (masking, shuffling). For high-assurance deployments, side-channel-resistant implementations are essential. For deployment guidance, see [NIST FIPS Guide](nist-fips-guide.html). ## What QNSQY Provides QNSQY ships ML-KEM (lattice) across all tiers and HQC (code-based) in the Business tier. Classic McEliece is not shipped because of its 1 MB key size, and BIKE is not shipped because it is not on the NIST FIPS track. For users who want maximum diversity, QNSQY's hybrid encryption combines ML-KEM with X25519, and Business tier users can also use HQC. The hybrid envelope format is extensible, so future code-based schemes (if standardised) can be added. See [Hybrid Encryption](hybrid-encryption.html) for the design and [HQC Explained](hqc-explained.html) for the HQC variant. The strategic value of code-based crypto for QNSQY is the diversity argument: if a future attack on lattices materialises, HQC provides a fallback layer in the hybrid envelope. The mathematical hardness assumptions of code-based and lattice-based crypto are different, so a break in one family does not automatically threaten the other. This is why NIST kept code-based crypto alive in Round 4 despite the lattice-based wins in Rounds 1 to 3. For more on the broader migration picture, see [NIST PQC Standards Timeline](nist-pqc-standards-timeline.html). ## Frequently Asked Questions ### Why has code-based crypto lasted so long without being broken? The structural properties of decoding random codes are fundamentally hard, with no known reduction to easier problems. McEliece has been studied since 1978, and despite many attempts, no fundamental break has been found. Other PQC families (lattices, isogenies) are younger and have had more attacks (RAINBOW, SIKE). ### What is the difference between BIKE and HQC? BIKE uses Quasi-Cyclic Moderate Density Parity-Check codes with a probabilistic bit-flipping decoder. HQC uses Hamming Quasi-Cyclic codes with a deterministic decoder. HQC was selected by NIST because its decoding failure analysis is simpler and side-channel resistance is easier. BIKE is still considered secure but is not on the FIPS track. ### Will Classic McEliece ever be standardised? It is not on the FIPS track for general-purpose use because of its 1 MB public key. NIST classified it in the "conservative deployment" category for niche applications where the key size is acceptable (long-term archive, server-side static keys). It may receive a separate niche standard but is not part of FIPS 209 (HQC) or FIPS 203 (ML-KEM). ### Is rank-metric code crypto secure? Active research, but the hardness of rank-metric decoding is less studied than Hamming-metric decoding. A few early proposals (ROLLO, RQC) had attacks discovered during the NIST process. Newer schemes in the signature on-ramp (RYDE, MIRA) use rank-metric problems. Cryptanalytic confidence is growing but not yet at the level of Goppa codes. ### Does code-based crypto have signature schemes? Several research signature schemes use code-based assumptions: CROSS, LESS, MEDS, SDitH. They are not standardised but advanced to NIST signature on-ramp Round 2 in 2024. If standardised, they would provide non-lattice signature options alongside SLH-DSA. ### How are HQC parameters chosen for each security level? HQC parameters are tuned to give specific NIST security levels (Level 1, 3, or 5, roughly equivalent to AES-128, AES-192, or AES-256 quantum strength). The submission specification (HQC Round 4 specification, April 2023) defines parameter sets HQC-128, HQC-192, and HQC-256. Each set picks a code length n, a code dimension k, the number of error positions w, and modulus q. The parameters are chosen so that the best known classical attack (Information Set Decoding) takes at least 2^128, 2^192, or 2^256 operations respectively. Quantum versions of ISD provide a square-root speedup, which is factored in. ### What about LDPC codes for KEMs? Low-Density Parity-Check (LDPC) codes have been studied as alternatives to MDPC codes used in BIKE. LDPC codes offer smaller parity-check matrices and faster decoding, but the security analysis is more challenging because LDPC's iterative decoder behaviour is closely linked to the Decoding Failure Rate. As of 2026, no LDPC-based scheme is on a NIST standardisation track. Research continues, particularly on whether LDPC variants can achieve smaller keys without compromising security. ## Sources 1. NIST. "Status Report on the Fourth Round of the NIST Post-Quantum Cryptography Standardization Process." NIST IR 8528, March 2025. https://csrc.nist.gov/pubs/ir/8528/final 2. McEliece, R.J. "A Public-Key Cryptosystem Based on Algebraic Coding Theory." JPL DSN Progress Report, 1978. (Original paper, no online copy due to era.) 3. Aguilar-Melchor, C., Aragon, N., Bettaieb, S., et al. "HQC: Hamming Quasi-Cyclic, Round 4 Specification." 2023. https://pqc-hqc.org/doc/hqc-specification_2023-04-30.pdf 4. Becker, A., Joux, A., May, A., Meurer, A. "Decoding Random Binary Linear Codes in 2^(n/20)." EUROCRYPT 2012. https://eprint.iacr.org/2012/026 5. Guo, Q., Johansson, T., Stankovski, P. "A Key Recovery Attack on MDPC with CCA Security Using Decoding Errors." ASIACRYPT 2016. https://eprint.iacr.org/2016/858 6. Sendrier, N. "Code-Based Cryptography: State of the Art and Perspectives." IEEE Security and Privacy, 2017. https://ieeexplore.ieee.org/document/8002485 7. Misoczki, R., Tillich, J.-P., Sendrier, N., Barreto, P. "MDPC-McEliece: New McEliece variants from Moderate Density Parity-Check codes." 2013. https://eprint.iacr.org/2012/409 8. NIST. "Post-Quantum Cryptography Project." https://csrc.nist.gov/projects/post-quantum-cryptography ## Related Articles - [HQC Explained](hqc-explained.html) - [BIKE Explained](bike-explained.html) - [Classic McEliece Deep Dive](classic-mceliece-deep-dive.html) - [NIST Round 4 Status](nist-round-4-status.html) - [What Is Post-Quantum Cryptography?](what-is-post-quantum-cryptography.html) --- ### Protect Your Data Before Q-Day Arrives QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats. [Try QNSQY](../../pricing.html)