HQC: Code-Based Post-Quantum Encryption Explained

What is HQC?

When two people want to communicate privately over the internet, they first need to agree on a shared secret key. This is the key that will actually encrypt and decrypt their messages. The problem is: how do you agree on a secret key when anyone might be listening to your conversation? You cannot just send the key in plain text.

This is the "key exchange" problem, and it is one of the foundational challenges in cryptography. For decades, we have solved it using algorithms like RSA and Diffie-Hellman, which rely on math problems that are easy to set up but extremely hard to reverse. Quantum computers will break both of these algorithms using Shor's algorithm.

HQC stands for Hamming Quasi-Cyclic. It is a key encapsulation mechanism (KEM), which is the modern version of key exchange. A KEM lets two parties establish a shared secret key over an insecure channel, even if an attacker is recording everything. HQC is designed to resist attacks from both classical computers and quantum computers.

On March 11, 2025, NIST announced that HQC had been selected as the fifth post-quantum algorithm for standardization, joining ML-KEM (FIPS 203), ML-DSA (FIPS 204), SLH-DSA (FIPS 205), and the forthcoming FN-DSA (FIPS 206 (draft)). HQC is the second KEM in NIST's post-quantum portfolio.

The critical fact about HQC: it is based on error-correcting codes, not lattices. ML-KEM, the first standardized post-quantum KEM, is lattice-based. HQC uses completely different mathematics. This is not a minor technical detail. It is the entire reason HQC exists in the standard.

Why Does the World Need Two KEMs?

ML-KEM was standardized in August 2024 as FIPS 203. It is fast, compact, and well-understood. It works well. So why did NIST spend years evaluating a second KEM?

The answer is a concept called algorithm diversity, and understanding it requires a brief detour into how cryptography actually works.

Every cryptographic algorithm is, at its core, a bet. You are betting that a specific mathematical problem is too hard for anyone to solve efficiently. ML-KEM bets on the Module Learning With Errors (MLWE) problem, which comes from the mathematics of lattices. HQC bets on the Quasi-Cyclic Syndrome Decoding (QCSD) problem, which comes from the mathematics of error-correcting codes.

These are completely independent bets. A mathematician who discovers a clever shortcut for solving lattice problems would break ML-KEM but would have no advantage whatsoever against HQC. Conversely, a breakthrough in decoding quasi-cyclic codes would break HQC but leave ML-KEM untouched. The two problems come from different branches of mathematics with different structures and different histories.

This matters because cryptographic breakthroughs have happened before. The MD5 hash function was widely trusted until 2004, when researchers demonstrated practical collision attacks. The RC4 stream cipher was used everywhere (including in TLS and WPA) until a series of attacks between 2001 and 2015 made it too dangerous to use. When an algorithm breaks, every system that depends on it becomes vulnerable at the same time.

If ML-KEM were the only post-quantum KEM and someone found a way to break it, the world would have no standardized quantum-safe replacement ready. It could take years to evaluate, test, and deploy an alternative. During that time, every encrypted communication would be at risk.

By standardizing HQC alongside ML-KEM, NIST ensures that if lattice-based cryptography is ever compromised, the world has a ready-made backup built on completely different mathematics. This is not paranoia; it is engineering prudence.

Error-Correcting Codes: An Everyday Analogy

Before explaining how HQC works, it helps to understand error-correcting codes, because they are the foundation of HQC's security.

Imagine you are reading a text message from a friend, but your phone has a bad connection and some letters arrive corrupted. The message reads: "Meet me at th3 cof&ee sh*p at 5pm." Even with three corrupted characters, you can easily read this. Your brain automatically corrects "th3" to "the," "cof&ee" to "coffee," and "sh*p" to "shop." You can do this because English has built-in redundancy: there are only so many words that fit the context, and a few corrupted letters do not destroy the meaning.

Error-correcting codes do the same thing, but with math instead of language intuition. They add structured redundancy to data so that even if some bits get flipped during transmission (by noise, interference, or hardware glitches), the original message can be perfectly recovered.

You rely on error-correcting codes constantly. Every time you stream a video, the data passes through error-correcting codes to fix bits corrupted during transmission. Every time you read from a hard drive or SSD, error-correcting codes fix the inevitable bit-flips that occur in physical storage. Every QR code you scan uses Reed-Solomon error correction, which is why QR codes still work even when they are partially obscured or damaged. Every satellite communication, every Bluetooth connection, every cellular phone call uses error-correcting codes.

The key insight for cryptography: while it is easy to add errors to a coded message, it is extremely hard to remove those errors unless you know the specific code structure that was used. This asymmetry, easy to corrupt, hard to fix without the secret, is what makes code-based cryptography possible.

How HQC Uses Codes for Encryption

In 1978, Robert McEliece proposed using error-correcting codes for encryption. The core idea is clever:

1. The receiver creates a secret error-correcting code with a known, efficient decoding algorithm. They know exactly how to fix errors added to messages encoded with this code.
2. The receiver publishes a disguised version of this code as their public key. The disguise hides the code's structure so that it looks like a random matrix to outsiders.
3. The sender encodes a message using the public key and deliberately adds random errors. The result is a noisy ciphertext.
4. The receiver uses their secret knowledge of the code's structure to efficiently strip away the errors and recover the original message.
5. An attacker who intercepts the ciphertext sees only a disguised code and a noisy message. Without knowing the hidden code structure, they face the generic problem of decoding a random linear code, which is computationally intractable.

HQC refines this approach using a specific type of code called quasi-cyclic codes. "Quasi-cyclic" refers to a structural property of the code: certain patterns repeat in a cyclical fashion, which makes the code efficient to work with while maintaining security. Think of it like a combination lock where the mechanism has a specific repeating structure, but knowing that a structure exists does not help you find the combination.

The underlying hard problem is Quasi-Cyclic Syndrome Decoding (QCSD). Given a random quasi-cyclic matrix and a value called a "syndrome," find a low-weight error vector that produced that syndrome. "Low-weight" means a vector with mostly zeros and only a few ones. This is a well-studied problem in coding theory, and no efficient algorithm is known for solving it, either classical or quantum.

The March 2025 Selection

NIST's selection of HQC on March 11, 2025 was the result of years of careful evaluation. HQC was one of the candidates in NIST's fourth round of post-quantum evaluation, which focused specifically on selecting a non-lattice-based KEM to complement ML-KEM.

HQC was chosen over other fourth-round candidates (BIKE and Classic McEliece) based on a combination of factors. Its security proofs are well-understood and rooted in a problem with decades of analysis. Its performance is acceptable for most applications. And its design is relatively clean, reducing the risk of subtle implementation bugs.

NIST's announcement specifically emphasized the algorithm diversity rationale: HQC provides a backup to ML-KEM based on different mathematical assumptions. This is not about replacing ML-KEM. ML-KEM remains the primary recommendation for general-purpose post-quantum key encapsulation. HQC is the safety net.

HQC vs BIKE vs Classic McEliece: Why HQC Won

NIST's fourth round evaluated three code-based KEM candidates alongside HQC: BIKE (Bit Flipping Key Encapsulation) and Classic McEliece. Each had distinct strengths and weaknesses, and understanding why HQC was chosen illuminates what NIST values in a cryptographic standard.

Classic McEliece has the longest pedigree, descending directly from McEliece's 1978 proposal. It has the strongest security arguments and the most conservative design. The problem? Its public keys are enormous. A Classic McEliece public key at the 128-bit security level is approximately 261 KB. For comparison, an HQC-128 public key is 2.2 KB, and an ML-KEM-512 public key is 800 bytes. Classic McEliece's key sizes make it impractical for most real-world protocols where public keys need to be stored, transmitted, or embedded in certificates.

BIKE offers good performance and compact parameters, but its security analysis was considered less mature than HQC's at the time of selection. BIKE's decoding failure rate (the small probability that a valid ciphertext fails to decrypt correctly) required careful analysis, and the community had less confidence in the tightness of its security reductions.

HQC struck the best balance. Its public keys and ciphertexts are larger than ML-KEM's (the price of code-based crypto) but far smaller than Classic McEliece's. Its security reduction to the QCSD problem is well-understood. Its decoding is based on concatenated codes (a Reed-Muller inner code with a Reed-Solomon-like outer code), which provides clean error correction with well-characterized failure rates. The algorithm is straightforward to implement correctly, reducing the risk of security-critical bugs.

HQC vs ML-KEM: Size and Speed Comparison

HQC's security comes with a practical tradeoff: larger keys and ciphertexts than ML-KEM. Here is a direct comparison across all three security levels:

Property	HQC-128	ML-KEM-512	HQC-192	ML-KEM-768	HQC-256	ML-KEM-1024
NIST Level	1	1	3	3	5	5
Public Key	2,249 bytes	800 bytes	4,522 bytes	1,184 bytes	7,245 bytes	1,568 bytes
Ciphertext	4,497 bytes	768 bytes	9,042 bytes	1,088 bytes	14,485 bytes	1,568 bytes
Shared Secret	64 bytes	32 bytes	64 bytes	32 bytes	64 bytes	32 bytes

The numbers tell a clear story. HQC public keys are roughly 3-5x larger than ML-KEM at the same security level. HQC ciphertexts are 6-9x larger. At the highest security level (Level 5), HQC-256 produces a ciphertext of about 14.5 KB, compared to ML-KEM-1024's 1.5 KB.

Does this matter? It depends entirely on the application. For data encryption (where the file itself might be megabytes or gigabytes), an extra 14 KB of overhead per key exchange is negligible. For email encryption, VPN tunnels, or database record encryption, the extra size is easily absorbed. For high-frequency TLS connections on a busy web server, or for tiny IoT devices on cellular connections, ML-KEM's compactness makes it the better default.

The tradeoff is explicit and intentional. HQC is larger because it is built on fundamentally different mathematics. That mathematical independence from ML-KEM is the entire reason HQC was selected. The size overhead is the price of algorithm diversity.

What This Means for the PQC Ecosystem

HQC's selection completes NIST's initial post-quantum cryptography portfolio with five algorithms spanning three distinct mathematical families:

• Lattice-based: ML-KEM (FIPS 203), ML-DSA (FIPS 204), FN-DSA (FIPS 206 (draft) draft)
• Hash-based: SLH-DSA (FIPS 205)
• Code-based: HQC (standard forthcoming)

This diversity means that even a dramatic breakthrough against one mathematical family would not compromise the entire post-quantum infrastructure. If lattices fall, SLH-DSA and HQC survive. If code-based problems fall, the lattice and hash-based algorithms survive. No single point of failure.

For organizations building long-term security strategies, HQC's standardization is a signal to start planning for algorithm agility. Systems should be designed so that the KEM algorithm can be swapped without redesigning the entire protocol. If you use ML-KEM today and need to switch to HQC tomorrow, the transition should be a configuration change, not an architecture overhaul.

The Practical Impact of Larger Keys

HQC's larger keys and ciphertexts deserve a concrete analysis, because "3-5x larger" can mean very different things depending on context. An HQC-256 ciphertext is about 14.5 KB. That sounds large, but consider what you are actually doing with it.

If you are encrypting a 10 MB file, the 14.5 KB ciphertext adds 0.14% overhead. For a 1 GB file, the overhead is 0.0014%. In data encryption, the ciphertext is generated once per file and stored alongside the encrypted data. The overhead is negligible for any file larger than a few kilobytes.

If you are establishing a VPN tunnel, the key exchange happens once at the beginning of the session. The 14.5 KB overhead is incurred once, then all subsequent data flows through the established symmetric key (AES-256-GCM or similar) with zero additional KEM overhead. For a VPN session that transfers gigabytes of data, the one-time 14.5 KB cost is invisible.

The situations where HQC's size becomes genuinely problematic are high-frequency short-lived connections (thousands of TLS handshakes per second on a busy web server) and severely constrained devices (sensors with kilobit-per-second cellular connections). For these use cases, ML-KEM is the better choice. For most other use cases, HQC's size is a non-issue.

When to Choose HQC Over ML-KEM

For the vast majority of applications, ML-KEM is the correct default. It is faster, more compact, and already standardized as FIPS 203. Choose HQC when:

• Regulatory compliance requires algorithm diversity. Some compliance frameworks (particularly in government and defense) require using algorithms from at least two distinct mathematical families. HQC satisfies the non-lattice requirement.
• You are protecting data with a 30+ year confidentiality requirement. If you are encrypting records that must remain secret for decades (medical records, legal documents, intelligence data), using both ML-KEM and HQC for different data sets ensures that a breakthrough against either family does not expose everything.
• Your threat model explicitly considers lattice breakthroughs. If your security team has assessed the risk of future advances in lattice cryptanalysis and decided to hedge against it, HQC is the standard-track alternative.
• Defense-in-depth strategy. Some organizations encrypt the most sensitive data with HQC and everything else with ML-KEM, so that even a worst-case scenario only exposes a portion of their data.

HQC is not a replacement for ML-KEM. It is a complement. The two algorithms serve the same function (key encapsulation) but derive their security from independent mathematical problems. That independence is the entire value proposition.

How QNSQY Uses HQC

HQC is available in the QNSQY Business tier. It follows the same hybrid pattern used for all post-quantum algorithms in QNSQY. The HQC shared secret is combined with an X25519 shared secret, so that an attacker must break both HQC and X25519 to compromise the key exchange. This provides defense-in-depth during the transition to post-quantum cryptography.

Generate an HQC keypair:

qnsqy keygen-enc -o mykey -n "My Encryption Key" --algorithm hqc128

Encrypt a file with HQC:

qnsqy encrypt -i document.pdf -k mykey.pub --kem hqc128

Three parameter sets are supported, matching NIST security levels:

• hqc128: NIST Level 1 (equivalent to AES-128 security)
• hqc192: NIST Level 3 (equivalent to AES-192 security)
• hqc256: NIST Level 5 (equivalent to AES-256 security)

Encryption and decryption commands work identically to ML-KEM workflows. You change the algorithm flag; everything else stays the same. Key files, hybrid wrapping, and recipient management are handled the same way.

Sources

1. NIST News: NIST Selects HQC as a Fifth Algorithm for Post-Quantum Encryption Standard, March 11, 2025
2. NIST FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard (ML-KEM), August 2024
3. NIST IR 8413: Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process, September 2022
4. HQC Project Homepage (original submission)
5. NIST Post-Quantum Cryptography Project Page

Questions people ask

What is HQC?

HQC (Hamming Quasi-Cyclic) is a code-based key-encapsulation mechanism that NIST selected in March 2025 as its fifth post-quantum algorithm. Its security rests on error-correcting-code problems rather than lattices, giving the ecosystem a mathematically independent fallback to ML-KEM.

Why did NIST select HQC in addition to ML-KEM?

Algorithm diversity. ML-KEM and most standardized schemes are lattice-based; if lattice cryptanalysis ever advances dramatically, a code-based alternative survives. HQC plays the same insurance role for key establishment that hash-based SLH-DSA plays for signatures.

Is HQC standardized yet?

Not yet. NIST announced the selection in March 2025 and the formal standard is expected in the 2026-2027 window. QNSQY already ships HQC-128, HQC-192, and HQC-256 hybridized with X25519 on the Business tier, tracking the draft specification.

Related Articles

• ML-KEM: Future of Key Encapsulation
• NIST Post-Quantum Cryptography Timeline: 2016-2026
• Classical vs Quantum-Safe Encryption Compared