PDF LaTeX source Comments

Chapter 23HQC

23.1Learning objectives#

After reading this chapter, you should be able to:

• explain how HQC differs from Classic McEliece (Chapter 22): McEliece hides the code, HQC hides the noise;

• state the hard problem HQC rests on – decoding a random quasi-cyclic code – and why the code itself is public;

• read the ring \(\mathbb{F}_2[x]/(x^n-1)\) as quasi-cyclic blocks, and multiplication in it as cyclic convolution over \(\mathbb{F}_2\);

• follow the KeyGen / Encapsulate / Decapsulate pipeline and verify the algebraic cancellation \(v - u\,y \approx mG\) by hand;

• explain why a publicly known, efficiently decodable code \(C\) removes the leftover low-weight error and recovers the message;

• place HQC among the schemes selected by NIST for standardization as a code-based complement to ML-KEM.

23.2Why this chapter matters#

The previous chapter built Classic McEliece, the oldest code-based scheme, whose security has survived since 1978. Its drawback is well known: the public key is enormous, hundreds of kilobytes to a megabyte. HQC (Hamming Quasi-Cyclic) is a much younger code-based KEM that attacks the same goal – post-quantum key encapsulation from coding theory – but from the opposite direction, and with far smaller keys.

The reason this matters beyond efficiency is diversity. Nearly all of the first published NIST post-quantum standards rest on lattice problems: ML-KEM and ML-DSA are lattice schemes. If a single unexpected advance were to weaken lattice assumptions, a backup built on a genuinely different hard problem would be valuable. In March 2025 NIST selected HQC [1] for standardization as an additional key-encapsulation mechanism, to complement ML-KEM with a scheme whose security rests on the hardness of decoding random codes rather than on lattices. At this standards snapshot, the final HQC FIPS has not yet been published; this chapter describes the current submission/specification rather than a final compliance interface.

23.3The key idea: hide the noise, not the code#

Both Classic McEliece and HQC are code-based, and both ultimately rely on the fact that decoding a random-looking linear code is hard. But they exploit that fact in opposite ways.

• Classic McEliece hides the code. The secret is a structured code (a binary Goppa code) that the owner knows how to decode efficiently. The public key is a scrambled generator matrix that looks like a random code with no usable structure. Security rests on the attacker being unable to tell the disguised structured code apart from a random one, and being unable to decode it. Because the public object is essentially a full random-looking generator matrix, it is large.

• HQC hides the noise. The decodable code \(C\) is public and fixed. Everyone – including the attacker – knows \(C\) and knows how to decode it. What is secret is a pair of low-weight vectors. Security rests on the attacker being unable to recover those low-weight secrets from the public data, which is exactly the problem of decoding a random quasi-cyclic code. Nothing structural is hidden, so there is no large disguised matrix to publish.

This is the same move that took us from LWE to Ring-LWE earlier in the book, transplanted into coding theory. Plain code-based cryptography, like plain LWE, needs a big unstructured matrix. Adding quasi-cyclic structure lets a single row (a single ring element) stand in for an entire circulant block, shrinking the key by a large factor – exactly as a circulant matrix is determined by its first row. HQC is to McEliece roughly as Ring-LWE is to LWE: it buys small keys by adding algebraic structure, at the cost of relying on a more structured assumption. The NTRU construction of Section 12.15 makes the same trade in the lattice world; HQC is its coding-theory cousin.

23.4The ring: quasi-cyclic blocks as ring elements#

Fix a length \(n\) (a prime, in the real scheme). The objects of HQC live in the ring \[R = \mathbb{F}_2[x]\big/(x^n-1).\] An element of \(R\) is a binary polynomial of degree less than \(n\), equivalently a binary vector of length \(n\). Two facts make this ring the right home for HQC.

Multiplication is cyclic convolution.#

Because \(x^n \equiv 1\), multiplying by \(x\) cyclically rotates the coefficient vector. Multiplying two ring elements \(h\) and \(y\) therefore convolves their coefficient vectors cyclically over \(\mathbb{F}_2\): \[(h\cdot y)_k \;=\; \bigoplus_{i+j\equiv k \ (\mathrm{mod}\ n)} h_i\, y_j .\] This uses the cyclic/circulant side of the convolution picture introduced in Chapter 5: the map \(y \mapsto h\cdot y\) is multiplication by the circulant matrix whose first row is \(h\). Storing the single vector \(h\) is enough to describe that entire \(n\times n\) circulant – this is the “quasi-cyclic” compression, and it is why HQC keys are small.

Weight is what stays secret.#

The Hamming weight of a ring element is the number of nonzero coefficients. A low-weight element has only a handful of ones among its \(n\) coordinates. HQC’s secrets are low-weight elements; a uniformly random \(h\) is not. The whole security argument turns on the gap between “low weight” and “random.” (For scale, HQC-128 uses \(n = 17669\) with secret weight \(w = 66\): sixty-six ones hidden among more than seventeen thousand coordinates.)

23.5The scheme#

HQC has the same algebraic silhouette as the toy ML-KEM pipeline (Figure 14.2): a public “syndrome” built from a secret, a ciphertext that reuses the public key against fresh randomness, and a decryption that cancels the shared term and decodes a small leftover error. Only the arithmetic changes – integers modulo \(q\) become bits, and “small” means low Hamming weight rather than small magnitude.

23.5.1Key generation#

Sample a uniformly random \(h \in R\) and two low-weight secrets \(x, y \in R\) (each of weight \(w\)). Publish \[s \;=\; x + h\cdot y .\] The public key is \((h, s)\) and the secret key is \((x, y)\).

The pair \((h, s)\) is exactly a quasi-cyclic syndrome: \(s\) is a random-looking ring element, and recovering the low-weight \((x, y)\) from \((h, s)\) is the Quasi-Cyclic Syndrome Decoding problem, believed hard even for a quantum computer. Note that \(h\) and \(s\) together are just two length-\(n\) vectors – there is no large matrix to store.

23.5.2Encapsulation#

Encapsulation encrypts a message \(m\) under the public code \(C\), then derives the shared key by hashing \(m\). Let \(G\) be the public generator matrix of \(C\), so that \(mG \in R\) is the codeword carrying the \(k\)-bit message \(m\). Sample fresh low-weight randomness \(r_1, r_2, e\) and compute \[u \;=\; r_1 + h\cdot r_2, \qquad v \;=\; mG + s\cdot r_2 + e .\] The ciphertext is \((u, v)\) and the shared key is \(K = H(m)\) for a hash function \(H\).

The two halves mirror KeyGen: \(u\) reuses the public \(h\) against the fresh secret \(r_2\) (just as \(s\) used \(h\) against \(y\)), and \(v\) hides the codeword \(mG\) under the public \(s\) times \(r_2\) plus a little extra noise \(e\). Every one of \(r_1, r_2, e\) is low weight – that is what makes decapsulation’s leftover small.

23.5.3Decapsulation#

The holder of \((x, y)\) computes \(v - u\cdot y\) and decodes the result with the public code \(C\). The point of the algebra is that the term shared between \(s\) and \(u\) cancels, leaving a codeword plus a low-weight error: \[\begin{aligned} v - u\cdot y &= \big(mG + s\,r_2 + e\big) - \big(r_1 + h\,r_2\big)\,y \\[2pt] &= mG + (x + h\,y)\,r_2 + e - r_1\,y - h\,r_2\,y \\[2pt] &= mG + x\,r_2 + \underbrace{h\,y\,r_2 - h\,r_2\,y}_{=\,0} + e - r_1\,y \\[2pt] &= mG + \big(x\,r_2 - y\,r_1 + e\big). \end{aligned}\] The two copies of \(h\,y\,r_2\) cancel because \(R\) is commutative. (Over \(\mathbb{F}_2\) subtraction is the same as addition, so the leftover is really \(x r_2 + y r_1 + e\); we keep the minus signs only to mirror the cancellation.) The leftover \[e' \;=\; x\,r_2 - y\,r_1 + e\] is a sum of products of low-weight vectors: \(x\,r_2\) has weight at most \(w\cdot w_r\), and likewise \(y\,r_1\), so \(e'\) has small, bounded weight. It is precisely a low-weight error added to the genuine codeword \(mG\). Because \(C\) is a known, efficiently decodable code chosen so that its decoder corrects up to that many errors, running the public decoder on \(v - u\,y\) removes \(e'\) and returns \(m\).

Decapsulation succeeds whenever the weight of \(e'\) stays within the decoding radius of \(C\). As in ML-KEM, the parameters \(n\), \(w\), \(w_r\), \(w_e\) and the code \(C\) are tuned so that this fails only with negligible probability.

23.5.4The pipeline at a glance#

23.6The public code \(C\)#

Everything hinges on \(C\) being a fixed, public code that is efficiently decodable up to the weight of \(e'\). This is the exact opposite of McEliece, where the ability to decode is the closely guarded secret. In HQC there is nothing to hide about \(C\): the attacker gains no advantage from knowing how to decode it, because decoding \(v - u\,y\) requires first computing \(u\,y\), which needs the secret \(y\).

The current HQC specification uses a concatenated code for \(C\): an outer Reed–Solomon code composed with an inner duplicated Reed–Muller code. The concatenation is chosen for decoding performance – a large, reliable error-correction radius at a good rate – since \(C\) contributes nothing to security. For this chapter the only property that matters is the interface: \(C\) has a public generator \(G\) (so \(mG\) is a codeword) and a public decoder \(\text{D}{\small\text{ECODE}}_C\) that corrects any error of weight up to its radius.

23.7From CPA to CCA: the FO transform#

Algorithms 33–35 describe the passively secure core: they resist an eavesdropper, but not an attacker who submits chosen ciphertexts and watches how decapsulation responds. As with ML-KEM, HQC upgrades this core to chosen-ciphertext (CCA) security with a Fujisaki–Okamoto (FO) transform [2], explained in full in Section 16.13.

At a high level, the FO transform makes encapsulation deterministic in the message: the randomness \(r_1, r_2, e\) is not sampled freshly but derived by hashing \(m\). Decapsulation then recovers \(m'\), re-runs encapsulation with that same \(m'\), and checks that the resulting ciphertext matches the one received. If it does, the ciphertext was honestly formed and the key \(K = H(m')\) is returned; if it does not, decapsulation returns a pseudorandom key derived from a secret seed instead of signalling an error. This “re-encrypt and compare” step is what defeats chosen-ciphertext attacks, and it is the same mechanism used throughout the lattice KEMs. The teaching algorithms above deliberately omit it to keep the algebra in focus.

23.8Where HQC sits#

The following table places HQC between its code-based ancestor and the lattice KEM it backs up. The column what is hidden accounts for the differences in key size.

23.9Pitfalls#

Pitfall 1: thinking the code is the secret.#

In McEliece the secret is the ability to decode; in HQC the code \(C\) and its decoder are fully public. Confusing the two inverts the whole security argument. In HQC what protects the message is the secret low-weight pair \((x,y)\), without which one cannot even form \(u\,y\), let alone decode.

Pitfall 2: reading “low weight” as “small numbers.”#

Everything is over \(\mathbb{F}_2\), so coefficients are only \(0\) or \(1\). “Small” here means few ones – low Hamming weight – not small magnitude. The security gap is between a weight-\(w\) vector and a uniformly random one, which is roughly half weight.

Pitfall 3: forgetting that the leftover error must fit the decoder.#

Decapsulation only works if \(e' = x r_2 - y r_1 + e\) stays within the decoding radius of \(C\). Raising the secret weights \(w, w_r, w_e\) strengthens the assumption but enlarges \(e'\); if it exceeds the radius, decoding fails. This is HQC’s analogue of ML-KEM’s decryption-failure budget, and the parameters are tuned to make failure negligible.

Pitfall 4: assuming quasi-cyclic structure is free.#

Adding quasi-cyclic structure is what shrinks the key from McEliece’s hundreds of kilobytes to a few, but it also narrows the assumption: HQC relies on decoding random quasi-cyclic codes, a more structured problem than decoding fully random codes. This is the same efficiency-versus-structure trade seen with Ring-LWE and NTRU (Section 12.15), and it is a conscious design choice, not an oversight.

Pitfall 5: using the passive core directly.#

The teaching algorithms here are only CPA-secure. A deployable HQC wraps them in the FO transform’s re-encrypt-and-compare check; skipping it exposes the scheme to chosen-ciphertext attacks.

23.10Summary#

• HQC hides the noise, not the code. The decodable code \(C\) is public and fixed; the secret is a pair of low-weight vectors \((x,y)\).

• Security is quasi-cyclic syndrome decoding. Recovering \((x,y)\) from \((h,\,s=x+hy)\) is decoding a random quasi-cyclic code – believed hard classically and quantumly.

• The algebra mirrors ML-KEM. KeyGen publishes a syndrome \(s\); encapsulation builds \(u = r_1 + h r_2\) and \(v = mG + s r_2 + e\); decapsulation cancels the shared \(h y r_2\) term so that \(v - u y = mG + e'\) with \(e'\) low weight, and the public decoder of \(C\) removes \(e'\).

• Quasi-cyclic structure buys small keys. A single ring element stands in for an entire circulant block, replacing McEliece’s huge matrix with a few kilobytes – at the cost of a more structured assumption, the coding-theory analogue of the LWE-to-Ring-LWE step.

• HQC is NIST’s code-based backup. Selected in March 2025 as an additional KEM, it complements the lattice-based ML-KEM with a scheme resting on an independent hard problem, so that a single advance against lattices would not break everything at once. It becomes an approved key-establishment scheme once its FIPS is published, and NIST has no current plans to select further KEMs [3].

References