HQC (Hamming Quasi-Cyclic)

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. NIST included it 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. 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
• Python Implementation
• Limitations
• 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. It 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. That’s what keeps HQC’s keys compact, without 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. It’s 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 at n=7: public h, private low-weight x/y, the u/v ciphertext pair, and genuine noise cancellation. In place of HQC’s real Reed-Muller/Reed-Solomon decoder, it uses a simple repetition(7) code (majority-vote decoding, correcting up to 3 bit flips), 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.

Python Implementation

This mirrors the visualizer’s own toy parameters described above (n=7, weight-1 secret and randomness vectors, repetition(7) majority-vote decoding):

import random

n = 7

def cyclic_conv_gf2(a, b):
    """Multiplication in GF(2)[X]/(X^n - 1): cyclic convolution with XOR instead of addition."""
    result = [0] * n
    for i in range(n):
        if a[i]:
            for j in range(n):
                result[(i + j) % n] ^= b[j]
    return result

def xor_vec(a, b):
    return [x ^ y for x, y in zip(a, b)]

def weight_vector(weight):
    v = [0] * n
    for pos in random.sample(range(n), weight):
        v[pos] = 1
    return v

def encode_bit(bit):
    return [bit] * n  # repetition(7) code

def decode_bit(codeword):
    return 1 if sum(codeword) > n // 2 else 0  # majority vote

def keygen():
    h = [random.randint(0, 1) for _ in range(n)]
    x, y = weight_vector(1), weight_vector(1)
    s = xor_vec(x, cyclic_conv_gf2(h, y))
    return (h, s), (x, y)

def encrypt(public_key, bit):
    h, s = public_key
    r1, r2 = weight_vector(1), weight_vector(1)
    u = xor_vec(r1, cyclic_conv_gf2(h, r2))
    v = xor_vec(encode_bit(bit), cyclic_conv_gf2(s, r2))
    return u, v

def decrypt(private_key, ciphertext):
    x, y = private_key
    u, v = ciphertext
    noisy_codeword = xor_vec(v, cyclic_conv_gf2(u, y))
    return decode_bit(noisy_codeword)

if __name__ == "__main__":
    public_key, secret_key = keygen()
    bit = 1

    ciphertext = encrypt(public_key, bit)
    recovered = decrypt(secret_key, ciphertext)

    print(f"Original bit:  {bit}")
    print(f"Recovered bit: {recovered}")
    assert recovered == bit

Every run uses a fresh random h and fresh weight-1 vectors, so there’s no single fixed ciphertext to reproduce. I ran 2000 independent trials instead, matching the scale of the empirical check described above: every single one recovered its bit exactly, and checking the residual noise weight directly (before decoding) reproduced the same 0-or-2 pattern the Worked Example section describes, never higher.

Limitations

This mirrors the visualizer’s toy parameters exactly, not real HQC’s production-scale ones:

• n=7 instead of tens of thousands. At this scale, both the code and the underlying algebraic problem are trivially breakable; the code demonstrates the masking-cancellation mechanism, not anything resembling real security.
• Repetition(7) code instead of a concatenated Reed-Muller/Reed-Solomon code. As the FAQ below notes, real HQC needs a far more powerful code to correct the larger residual noise that appears at secure parameters; majority-vote decoding on 7 bits is only sufficient because the toy’s noise stays within weight 2.
• Single-bit messages. Real HQC encrypts many bits per operation using a larger code; this toy encrypts exactly one bit at a time, matching the worked example above.
• No extra security-tightening error term. As the Interactive Visualizer note above mentions, real HQC adds a small additional error term purely to tighten its security proof; this code omits it since the toy’s existing noise is already comfortably within the repetition code’s correction range.
• Uses Python’s random, not a CSPRNG. Real HQC needs cryptographically secure randomness for h and the low-weight vectors; random.sample here is for demonstration only.
• Never use this, or hand-rolled code-based cryptography of any kind, in production. Real applications should use a vetted library’s HQC implementation.

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, but with keys small enough for routine use. That gives NIST a genuinely different backup to Kyber, one 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. That trade-off buys 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. That’s 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. That’s 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.