HQC (Hamming Quasi-Cyclic)

Introduction

On March 11, 2025, NIST announced HQC as its fifth post-quantum standard — a backup key encapsulation mechanism (KEM) alongside CRYSTALS-Kyber, included specifically so that a structural break in lattice cryptography wouldn’t leave the world without a second, mathematically independent option. Like McEliece, HQC is code-based — its hardness rests on decoding a linear error-correcting code, a problem believed to resist quantum attacks entirely. But where McEliece hides its trapdoor by physically scrambling a fast-decodable code until it looks random, HQC takes a completely different approach: it publishes an unscrambled, publicly-known code and instead buries the message in noise generated through pure ring algebra. Same family of hard problem, structurally unrelated trapdoor.

Table of Contents

• Two Ways to Hide a Code
• The Quasi-Cyclic Ring
• Key Generation
• Encryption and Decryption
• A Worked Example
• Why the Masking Terms Cancel
• HQC vs. McEliece
• FAQ
• References

Two Ways to Hide a Code

Both HQC and McEliece rely on the same underlying fact: decoding a generic, unstructured linear code is intractable, while decoding a code with known structure (once you know that structure) is fast. The two schemes disagree entirely on what to hide. McEliece hides the code’s structure itself, disguising a fast Goppa-code decoder behind random scrambling matrices so it looks like an arbitrary code to anyone without the key. HQC instead keeps its error-correcting code completely public and undisguised — anyone can see exactly which code is in use — and hides the message behind an algebraically generated noise term that only the private key can cancel out. It’s the difference between hiding how you’d correct errors, versus hiding which errors you’d need to correct.

The Quasi-Cyclic Ring

HQC works in the ring R = 𝔽₂[X]/(Xⁿ−1) — binary vectors of length n, multiplied via cyclic convolution (the same wraparound-multiplication idea used by NTRU, just over the field with two elements instead of larger integers). “Quasi-cyclic” describes the resulting code family: because ring elements shift cleanly under multiplication, a single length-n vector can efficiently generate an entire structured code, which is what keeps HQC’s keys compact despite not needing McEliece’s large scrambled generator matrix.

Key Generation

1. Choose a public, fixed, well-known error-correcting code (real HQC uses a concatenation of a Reed-Muller code and a Reed-Solomon code, correcting many errors at once).
2. Sample a uniformly random public ring element h.
3. Sample two low-weight (mostly-zero) secret vectors x and y — these are the private key.
4. Compute the public key: s = x ⊕ (h·y), where · is cyclic convolution and ⊕ is XOR.

Encryption and Decryption

To encrypt a message bit m (real HQC encrypts many bits per operation using a larger code; the mechanism is identical):

1. Encode m into a codeword using the public code.
2. Sample two fresh low-weight vectors r1, r2 (the encryptor’s randomness).
3. Compute u = r1 ⊕ (h·r2).
4. Compute v = codeword ⊕ (s·r2).
5. The ciphertext is (u, v).

To decrypt, the recipient (holding x, y) computes:

v ⊕ (u·y)

which works out — after the algebra below cancels — to codeword ⊕ (x·r2) ⊕ (r1·y): the original codeword XORed with a small amount of residual noise. Since x, y, r1, r2 are all low-weight, that noise is low-weight too — small enough for the public code’s decoder to correct, recovering the codeword and then the message bit exactly.

Interactive Visualizer

Real HQC uses n in the tens of thousands and a sophisticated concatenated code correcting dozens of errors at once. The visualizer above runs the identical ring-convolution structure — public h, private low-weight x/y, the u/v ciphertext pair, and genuine noise cancellation — at n=7, using a simple repetition(7) code (majority-vote decoding, correcting up to 3 bit flips) in place of HQC’s real Reed-Muller/Reed-Solomon decoder, small enough to read every bit directly. It also omits the small extra error term real HQC adds purely to tighten its security proof — the toy’s noise (from x·r2 and r1·y alone) is already well within the repetition code’s correction range.

A Worked Example

Using the visualizer’s toy parameters:

1. A random 7-bit h and weight-1 secret vectors x, y produce the public key s = x ⊕ h·y.
2. To send a bit, the sender picks weight-1 r1, r2, encodes the bit as seven repeated copies (0000000 or 1111111), and computes u = r1 ⊕ h·r2, v = codeword ⊕ s·r2.
3. The recipient computes v ⊕ u·y — the h-dependent terms cancel algebraically, leaving the codeword XORed with noise of weight 0 or 2 (empirically, out of 2000 trials: 277 came back weight 0, 1723 came back weight 2, never higher).
4. Majority-vote decoding easily corrects weight-2 noise in a 7-bit repetition code (which tolerates up to 3 flips), recovering the bit exactly every time.

Why the Masking Terms Cancel

Expanding v ⊕ (u·y) with s = x ⊕ (h·y) and u = r1 ⊕ (h·r2):

v ⊕ u·y = codeword ⊕ (s·r2) ⊕ (u·y) = codeword ⊕ (x·r2) ⊕ (h·y·r2) ⊕ (r1·y) ⊕ (h·r2·y)

Since ring multiplication is commutative, h·y·r2 = h·r2·y — the same term appears twice, and XORing something with itself cancels it (A ⊕ A = 0). What’s left is codeword ⊕ (x·r2) ⊕ (r1·y) — the public random element h has vanished entirely, and only the small, low-weight secret-dependent noise remains. This is exactly the same “public masking term self-cancels, leaving only the small stuff” pattern that makes every LWE-family scheme in this series work — HQC just runs it over a binary ring with XOR instead of over integers mod q with subtraction.

HQC vs. McEliece

HQC’s compact keys make it far more practical for everyday protocols than McEliece’s enormous ones — the trade-off is a small, carefully-bounded chance of decryption failure that McEliece’s deterministic decoder doesn’t have.

FAQ

Why does NIST want a second code-based KEM if McEliece already exists?

McEliece’s huge keys make it impractical for most real protocols despite its long unbroken track record; HQC offers the same code-based (non-lattice) hardness assumption with keys small enough for routine use, giving NIST a genuinely different backup to Kyber that isn’t itself a lattice scheme.

Is HQC’s small decryption failure rate a security problem?

No — it’s a standard, carefully analyzed engineering trade-off (also present in Kyber, FrodoKEM, and SABER in this series). Real HQC’s parameters are chosen so the failure probability is astronomically small (far below any level an attacker could exploit), not zero, in exchange for much smaller keys than a zero-failure code would need.

What does “quasi-cyclic” actually buy HQC?

Efficiency and compactness: because a quasi-cyclic code’s structure repeats under cyclic shifts, the entire code (and the fast arithmetic needed to use it) can be generated from a single length-n vector rather than a full matrix, which is exactly why HQC’s public keys are kilobytes instead of McEliece’s hundreds of kilobytes to megabytes.

Does HQC use the same repetition code shown in the visualizer?

No — real HQC concatenates a Reed-Muller code with a Reed-Solomon code to correct far more errors at a much larger block length, which is necessary at secure parameters. The visualizer’s repetition(7) code preserves the same “public code corrects small residual noise” mechanism at a size simple enough to read by eye.

References

1. Aguilar Melchor, C., Aragon, N., Bettaieb, S., et al. “HQC: Hamming Quasi-Cyclic.” NIST PQC submission. Available at: https://pqc-hqc.org/

2. NIST. “NIST Selects HQC as Fifth Algorithm for Post-Quantum Encryption.” March 2025.

3. NIST. “Post-Quantum Cryptography Standardization.” Available at: https://csrc.nist.gov/projects/post-quantum-cryptography

4. Aragon, N., Barreto, P., Bettaieb, S., et al. “Hamming Quasi-Cyclic (HQC).” Cryptology ePrint Archive.