HQC: key encapsulation based on codes

17 Nov 2025

Introduction

In 2022, the third round conclusion of the NIST standardization process on post-quantum cryptography selected a key encapsulation mechanism (CRYSTALS-Kyber/ML-KEM), three digital signature schemes (CRYSTALS-Dilithium/ML-DSA, Falcon/FN-DSA and SPHINCS+/SLH-DSA) and opened a fourth round devoted to evaluating an additional key encapsulation mechanism as an alternative to ML-KEM. Although the cryptographic community has strong confidence in the security guarantees provided by ML-KEM, its mathematical foundations are still relatively recent, and it cannot be ruled out that further research in cryptanalysis could affect its effectiveness. Therefore, while ML-KEM remains the primary solution, NIST decided to identify an alternative that could easily replace it if needed and that relies on different security assumptions from those of lattice-based cryptography. In this context, the fourth round analyzed three code-based schemes (Classic McEliece, HQC, and BIKE) and one isogeny-based scheme (SIKE). After SIKE’s break, the process was restricted to the former three candidates and concluded on March 5th, 2025, with the NIST selection of the Hamming Quasi-Cyclic (HQC) scheme.

Hamming Quasi-Cyclic

This article describes the HQC scheme, including its underlying mathematical structures and the security assumptions that define it [1]. The mathematical objects involved in the scheme belong to $\mathcal{R}=\mathbb{F}_2[X]/(X^n-1)$ , i.e., the set of binary polynomials in $X$ under the relation $X^n=1$ . Given two polynomials $\mathbf{p},\mathbf{q}\in\mathcal{R}$ , their product $\mathbf{p}\cdot \mathbf{q}$ can be represented as the product between a circulant matrix, denoted by $\mathbf{rot}(\mathbf{p})$ , and a vector:

$\mathbf{p} \cdot \mathbf{q} \Leftrightarrow \mathbf{rot}(\mathbf{p})\begin{pmatrix} q_0 \\ q_1 \\ \vdots \\ q_{n-1} \end{pmatrix}=\begin{pmatrix} p_0 & p_{n-1} & \cdots & p_1 \\ p_1 & p_0 & \cdots & p_2 \\ \vdots & \vdots & \ddots & \vdots \\ p_{n-1} & p_{n-2} & \cdots & p_0 \end{pmatrix} \begin{pmatrix} q_0 \\ q_1 \\ \vdots \\ q_{n-1} \end{pmatrix},$

where $p_i$ (resp. $q_i$ ) is the binary coefficient of $X^i$ in $\mathbf{p}$ (resp. $\mathbf{q}$ ).

Security assumption

HQC security relies on the hardness of the Decisional Quasi-Cyclic Syndrome Decoding (DQCSD) problem. Let $\omega(\cdot)$ be the Hamming weight function [2] and let $\mathcal{R}_{\omega}$ denote the subset of $\mathcal{R}$ collecting elements of Hamming weight [3] $\omega$ . The DQCSD problem consists in distinguishing between the following two probability distributions:

QSCD Distribution: uniformly sample $\mathbf{h}\in\mathcal{R}$ and $\mathbf{x}=(\mathbf{x_0},\mathbf{x_1})\in\mathcal{R}_{\omega}^2$ (i.e., $\mathbf{h}\leftarrow\mathcal{R}$ , $\mathbf{x}\leftarrow \mathcal{R}_{\omega}^2$ ) and output the pair $\left(\mathbf{h},(\mathbf{1}_n\,\,\mathbf{rot}(\mathbf{h}))\begin{pmatrix}\mathbf{x_0}\\\mathbf{x_1} \end{pmatrix}=\mathbf{x_0}+\mathbf{h}\cdot\mathbf{x_1}\right)\in \mathcal{R}\times\mathbb{F}_2^n$ ;
Uniform Distribution: uniformly sample and output a pair $(\mathbf{h},\mathbf{y})\in\mathcal{R}\times\mathbb{F}_2^n$ .

This is a specific case [4] of the more general Syndrome Decoding (SD) problem, where the parity-check matrix is $H=(\mathbf{1}_n\,\,\mathbf{rot}(\mathbf{h}))$ . This structure enables a smaller public key size without significantly affecting resistance to known attacks.

HQC Public Key Encryption (PKE)

Following the same principles as ML-KEM, the HQC key encapsulation design starts from a public key encryption scheme and applies the Fujisaki–Okamoto transform [5]. Similar to other public key encryption schemes, HQC PKE is built through three algorithms: key generation, encryption and decryption.

Key generation: the secret key $sk$ consists of $\mathbf{x}$ and $\mathbf{y}$ , uniformly sampled among all polynomials in $\mathcal{R}$ with Hamming weight $\omega$ . The public key is the pair $(\mathbf{h}, \mathbf{s}=\mathbf{x}+\mathbf{h}\cdot \mathbf{y})$ , where $\mathbf{h}$ is uniformly sampled in $\mathcal{R}$ . The infeasibility of recovering the secret key from the public key is ensured by the hardness of the DQCSD problem.
Encryption of a message $m$ : for correctness reasons, the plaintext $m$ is first encoded [6]. Note that this code has no relation with the code underlying the security assumption [7]. After uniformly sampling three elements $\mathbf{r_1}$ , $\mathbf{r_2}$ and $\mathbf{e}$ from $\mathcal{R}_{\omega}$ , the ciphertext of $m$ is the pair $(\mathbf{u}=\mathbf{r_1}+\mathbf{h}\cdot\mathbf{r_2}, \mathbf{v}=\text{Encode}(m) + \mathbf{s}\cdot\mathbf{r_2}+\mathbf{e})$ .
Decryption of $c$ : knowing the private key, the original message $m$ is recovered by decoding (with respect to the same code used in encryption) $\mathbf{v}-\mathbf{u}\cdot\mathbf{y}$ .

Decryption correctness follows from the equation:

$\begin{align*} \mathbf{v}-\mathbf{u}\cdot\mathbf{y} & = \text{Encode}(m)+\mathbf{s}\cdot \mathbf{r_2}+\mathbf{e}-\mathbf{u}\cdot\mathbf{y} \\ & = \text{Encode}(m)+\mathbf{s}\cdot \mathbf{r_2}+\mathbf{e}-\mathbf{r_1}\cdot\mathbf{y}-\mathbf{h}\cdot\mathbf{r_2}\cdot\mathbf{e} \\ & = \text{Encode}(m)+\underbrace{\mathbf{x}\cdot \mathbf{r_2}+\mathbf{e}-\mathbf{r_1}\cdot\mathbf{y}}_{\text{small term}} \end{align*}$

The additional term, being a sum of small-weight elements, is absorbed by the decoding process. An interesting observation is that the public key and ciphertext constructions closely resemble those of LWE-based schemes such as ML-KEM. Both involve multiplying a public matrix by a secret and adding noise. However, HQC and ML-KEM operate over distinct mathematical frameworks — codes and lattices, respectively — which leads to fundamentally different security assumptions.

HQC Key Encapsulation Mechanism (KEM)

The key generation, encapsulation and decapsulation algorithms of HQC KEM build upon the corresponding procedures of HQC PKE.

Key generation: this algorithm invokes the HQC PKE key generation procedure and additionally samples a secret $\sigma$ , which is used in case of decapsulation failure.
Encapsulation: a plaintext $m$ is uniformly sampled. The shared key $K$ is derived from $m$ and the public key via a hash function $\textsf{H}$ . The message $m$ is then encrypted with HQC PKE and transmitted.
Decapsulation of $c$ : the decryption, re-encryption and comparison steps from the Fujisaki–Okamoto transform are highlighted in red. If decapsulation fails, no explicit error is returned; instead, a random key is derived from the secret $\sigma$ . In this case, the two parties end up with distinct cryptographic keys and the mismatch is only detected in later communication — a property known as implicit rejection.

Performance

This section concludes by comparing the performance [8] of HQC, ML-KEM and the pre-quantum Elliptic Curve Diffie–Hellman (ECDH) scheme under equivalent security targets.

Compared to ECDH, HQC achieves a similar computational cost (approximately a $\times2$ factor) but exhibits a significant increase in key and ciphertext size (about $\times200$ ). This aligns with the general observations on the challenges of transitioning to post-quantum cryptography. Relative to ML-KEM, HQC shows a roughly $\times4$ increase in transmitted data size and a $\times9$ increase in computational cost. Indeed, one of the main strengths that led to ML-KEM’s selection in the third round was its excellent performance. For this reason, HQC is considered a backup alternative, to be preemptively implemented in case future cryptanalytic results undermine the security of ML-KEM.

[1] As with other contributions in this series, the discussion is slightly simplified compared to the official HQC documentation, while retaining its key concepts.

[2] The Hamming weight function applied to a vector in $\mathbb{F}_2^n$ returns the number of its entries equal to $1$ .

[3] Here, the Hamming weight function is computed considering the vector formed by the polynomial’s coefficients.

[4] For completeness, note that the problem described here is the 2-DSQC; HQC also requires assuming the hardness of its extension, the 3-DSQC.

[5] The rationale behind this construction is the same as for ML-KEM, detailed in the corresponding article.

[6] The encoding process consists of concatenating a Reed–Muller code with a Reed–Solomon code, both publicly known.

[7] In summary, HQC employs two distinct codes: one ensuring security and another ensuring correctness.

[8] Performance results refer to an optimized (AVX2) implementation on an Intel Xeon E-2124 processor.

This article belongs to a series of contributions, edited by the Telsy Cryptography Research Group, devoted to quantum computing and its implications on Cryptography. For reference to other articles, please refer to the index.

For other articles related to Quantum and Cryptography topics, please refer to the related categories in the blog.

The author

Francesco Stocco, a master’s degree in Mathematics at the University of Padua and the Université de Bordeaux attending the course of study “Algebra Geometry And Number Theory” (ALGANT), joined the Telsy research group in Cryptography at the end of 2020 focusing in particular on issues related to quantum technologies.