# Sparse Vector Reconstruction from Distance Spectrum using Soft Information

Magali Salom, Nicolas Sendrier, Valentin Vasseur

► To cite this version:

Magali Salom, Nicolas Sendrier, Valentin Vasseur. Sparse Vector Reconstruction from Distance Spectrum using Soft Information. 2026. hal-05466728

HAL Id: hal-05466728

https://inria.hal.science/hal-05466728v1

Preprint submitted on 20 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Sparse Vector Reconstruction from Distance Spectrum using Soft Information

Magali Salom<sup>1,2</sup>, Nicolas Sendrier<sup>2</sup>, Valentin Vasseur<sup>1</sup>

<sup>1</sup> Thales, Gennevilliers, France

<sup>2</sup> Inria, Paris, France

**Abstract.** QC-MDPC based schemes feature secret sparse cyclic binary vectors. When those vectors are sparse enough, they can be reconstructed from their distance spectrum, that is the set of all distances between the coordinates of the non-zero coefficients. In this work, we revisit the reconstruction algorithms and we explore to what extent a secret sparse vector can be recovered from a partial knowledge of its distance spectrum. In particular, we show how to efficiently use reliability (soft information) in the reconstruction process. Another aspect of this work is to investigate which kind of side-channel leaks information about the distance spectrum and to understand the models that enable us to quantify the reliability on leaking data depending on the amount of side-channel observations (or queries). For instance, we show that for BIKE level 1, assuming that a side-channel leaks information about the syndrome weight, using soft information in the reconstruction process reduces the number of queries by a factor 10. Our technique can also be applied to HQC, which also features sparse secret vector, with similar figures, assuming there exists a side-channel leaking relevant information, the error weight in the case of HQC.

**Keywords:** code-based cryptography, QC-MDPC codes, BIKE, HQC, key recovery attack, distance spectrum, side-channel attack

## 1 Introduction

Some recent code-based cryptosystems (e.g. BIKE or HQC) involve secret sparse cyclic vectors. In such situations, the knowledge of the distance spectrum [4] allows the efficient reconstruction of the secret. Information on the distance spectrum may leak from a side-channel, e.g. reaction attack [4] or timing attack [2], which therefore allows key recovery.

The general scenario is a known plaintext side-channel attack, the attacker can make multiple queries to a decryption device which is assumed to leak information about the spectrum of a given fixed sparse secret. With sufficiently many queries the attacker can recover the full spectrum and efficiently reconstruct the secret. With less queries, the attacker only has a partial knowledge of the spectrum and the reconstruction, though harder, may still remain feasible.
In this paper, we revisit the reconstruction algorithm, in particular we propose and implement a variant able to handle a soft input spectrum, allowing us to efficiently deal with reliability information. Together with an accurate leakage model we are able to quantify the gain provided by such an algorithm. In the case of BIKE-1, the number of queries is reduced by a factor 10. Our study is made in an idealized abstract model in which the adversary has access to the Hamming weight of the syndrome used in BIKE's decapsulation procedure. In a more realistic scenario, the information leaking from the side-channel may only have a small correlation with the syndrome weight, possibly with extra noise. This will increase the number of queries to get a full or partial spectrum, but we believe that the gain factor between hard and soft input reconstructions will be of the same order.

## 1.1 Overview

The distance spectrum Sp(g) of a cyclic sparse vector $g \in \mathcal{R} = \mathbb{F}_2[x]/(x^r - 1)$ is the set of all distances between its 1's. For QC-MDPC-based encryption schemes, a sparse error pattern $e = (e_0, e_1) \in \mathcal{R}^2$ is encrypted using a public key pk into $c = \text{Enc}(e, pk)$ and later decrypted using a sparse private key sk = $(h_0, h_1) \in \mathcal{R}^2$ as $e = \text{Dec}(c, sk)$. It is assumed that an adversary can make queries $\text{Dec}(\text{Enc}(e, pk), sk)$ and observe a numerical value$^3 f(e_0, h_0)$ such that for all $\delta$ that may appear in a distance spectrum, i.e. $1 \le \delta \le r/2$, the (conditional) expectation $\mathbb{E}(f(e_0, h_0) | \delta \in \text{Sp}(e_0))$ is different depending on whether $\delta$ belongs to $\text{Sp}(h_0)$ or not. Concretely, for a given public/private key pair pk/sk:

(1) sample a set $\mathcal{E} \subset \mathcal{R}^2$ of error patterns;

(2) for all $e \in \mathcal{E}$, query the decryption oracle on $\text{Enc}(e, pk)$ and observe $f(e_0, h_0)$;

(3) for all $1 \le \delta \le r/2$, let $\mathcal{E}_{\delta} = \{e \in \mathcal{E} | \delta \in \text{Sp}(e_0)\}$ and decide whether $\delta \in \text{Sp}(h_0)$ depending on the value of

$$F_{\delta} = \frac{1}{|\mathcal{E}_{\delta}|} \sum_{e \in \mathcal{E}_{\delta}} f(e_0, h_0). \qquad (1)$$

Hopefully, if the sample set $\mathcal{E}$ is large enough, the adversary may recover the full spectrum of $h_0$ and then reconstruct $h_0$. This framework was first used in [4] with $f(e_0, h_0) = 1$ in case of decoding failure and 0 otherwise. Later, it was used in [2], either with $f(e_0, h_0) = i$ the number of iterations to succeed in the bit-flipping decoder, or with $f(e_0, h_0) = |e_0h_0 + e_1h_1|$ the syndrome weight. For instance, we plotted in Figure 1 the function $\delta \mapsto F_{\delta}$ (top) and the density function of the distribution of $F_{\delta}$ (bottom) when the observable is the syndrome weight. Other observables, e.g. failure or timing, give similar diagrams but require a substantially higher number of decryption queries. Dots in Figure 1 are red if $\delta \notin \text{Sp}(h_0)$ and blue otherwise. We remark that the values of $F_{\delta}$ concentrate

<footnote>$^3$ the attack may target either $h_0$ using $e_0$, or $h_1$ using $e_1$, without loss of generality we assume that the first block is targeted</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1. $f(e_0, h_0) = |e_0h_0 + e_1h_1|$ and $|\mathcal{E}| = 10^6$ for BIKE Level 1 parameters</figcaption></figure>

mostly in two stripes, red when $\delta \notin \text{Sp}(h_0)$ and blue$^4$ when $\delta \in \text{Sp}(h_0)$. The adversary, which is oblivious to colors but knows by analysis the red and blue lines, must guess the color of each dot depending on where it lies in the diagram. Finally, those diagrams emphasize the impact of multiplicity—we denote $\mu_g(\delta)$ the number occurrences of the distance $\delta$ between the 1 coordinates of g—on the modeling of the density distribution function of $F_\delta$.

*Recovery from Full or Partial Spectrum:* current key recovery techniques are successful when the full spectrum has been correctly guessed, but they are vulnerable to faulty data. On the other hand, reconstruction algorithms can easily be adapted to situations where the status, inside or outside the spectrum, of a small proportion of the distances is unknown—or deliberately ignored to avoid mistakes. Typically, the least reliable distances $\delta$ are such that $F_\delta$ lies inside the hatched area in Figure 1. Those distances can be ignored without impairing the reconstruction as long as there are not too many of them.

*Soft Information:* going further involves soft information and requires some kind of modeling. For each $\delta$, the observation $F_\delta$ is transformed into a probability distribution $(p_\nu)_{\nu \ge 0}$ where $p_\nu$ is the probability, given the observation $F_\delta$, to have $\delta$ appearing in $\text{Sp}(h_0)$ with multiplicity $\nu$. The reconstruction algorithm can then be adapted to properly and efficiently handle this reliability information.

## 1.2 Related Works

For code-based cryptography, the distance spectrum and the above framework were introduced in [4]. The observable is the decoding failure rate. This semi- nal paper also features a backtrack search reconstruction algorithm to obtain a

<footnote>$^4$ the additional dashed lines correspond to distances that appear multiple times in $h_0$</footnote>
key from its full spectrum. Variants of this attack with different observables— namely timing and syndrome weight—were proposed in [2] and variants of the key reconstruction algorithm were proposed in [9,8].

Key recovery from partial spectrum was first explored in [9]. In contrast with other works, their reconstruction technique requires both spectra, Sp(h₀) and Sp(h₁). The threshold to ignore distances is determined empirically and a reduction of 20% on the number of queries is claimed. Recovery from partial spectrum is also considered in [7], using the reconstruction technique of [8] which features a breadth-first search—rather than depth-first. The ignored distances, corresponding to the hatched region in Figure 1, is determined from a model of the density function. The model is a combination of Gaussian distribution whose parameters are determined empirically.

Key recovery from spectrum using soft information has been considered in [5]. The main focus of that paper is not reconstruction, but still it suggests some improvements for the backtrack search and also provides some guidelines for the use of reliability information. The latter was not implemented, but the authors estimate that using soft information could reduce the number of queries by a factor 2 to 4.

Finally, let us mention that this reconstruction problem has appeared in other fields, e.g. genetics or crystallography, and is sometimes referred to as the “turnpike” or “beltway” problem [10,1,6]. Context and parameters are rather different though.

## 1.3 Contributions

We consider a scenario in which the attacker derives the key spectrum, possibly with reliability information, from the observation of the syndrome weight.

- *An Improved Algorithm.* We revisit the key reconstruction algorithm from a full spectrum. We speed up the backtrack search technique by moving two steps at a time in the search tree. We also improve the pruning condition (a.k.a. consistency check) by introducing the concept of extension of a polynomial relatively to a spectrum. Overall, this improves on previous reconstruction techniques. With BIKE-1 parameters obtaining the full spectrum requires about 2 million queries to the decryption oracle.

- *Modeling the Observed Distribution.* We remark that the distribution of $F_{\delta}$ features a better discrimination between the key spectrum multiplicities when the observable is weighted with the multiplicity of $\delta$ in the error spectrum, for a given sample set $\mathcal{E}$ of error patterns:

$$F_{\delta} = \frac{1}{\sum_{e \in \mathcal{E}} \mu_{e_0}(\delta)} \sum_{e \in \mathcal{E}} \mu_{e_0}(\delta) f(e_0, h_0). \quad (2)$$

The usual model for the probability density function of $F_{\delta}$ is a combination of several normal distributions, one for each multiplicity, which is empirically determined, see Figure 1 (bottom). When the observable is the syndrome
weight, we obtain a model for (2) with proven coefficients for the combination and proven means for the normal distributions. The standard deviations are still determined empirically but, interestingly, seem to be the same for all multiplicities.

- *Reconstruction from Partial Spectrum.* We show how our algorithm can be adapted to handle a partial spectrum. In particular the above model is used to determine the least reliable distances. To perform correctly, our algorithm must know most of the complement of the spectrum but needs only a very small part of the spectrum. For BIKE-1 parameters, the number of queries drops to 700 thousands, about one third of the amount required for a full spectrum reconstruction.

- *Reconstruction from Soft Information.* We adapt our reconstruction algorithm to soft information, using a methodology close to the guidelines given in [5]. From our model for (2), we derive the multiplicity distribution for each $\delta$ and a score function which measures the chances for a node in the search tree to be in the path of a solution. This allows us to efficiently browse and prune the search space. For BIKE-1 parameters, the number of queries drops to 200 thousands, about one tenth of the amount required for a full spectrum reconstruction.

- *Generalization.* Though our primary target is BIKE in an ideal model where the adversary can directly observe the syndrome weight, we show that our technique can be adapted to other schemes, e.g. HQC, and to other side-channels as long as the leakage is correlated to the syndrome weight.

*Artifact.* C code to reproduce the simulations is available at https://github.com/m-salom/key_rec_spectrum.

## 1.4 Paper Organization

We first give some background results and definitions in §2, then present all variations of our reconstruction algorithm from a full §3, partial §4, or soft §5 spectrum. We give in §6 our model for the probability distribution of our observable and finally explain in §7 how the framework can be extended to other observables and schemes, together with the numerical results of some of our experiments.
## 2 Preliminaries

### NOTATION

<table><tr><td>$\mathbb{F}_2$:</td><td>the binary finite field</td></tr><tr><td>$\mathcal{R}$:</td><td>the cyclic polynomial ring $\mathbb{F}_2[x]/(x^r - 1)$, r an odd prime</td></tr><tr><td>$g_i$:</td><td>0 ≤ i < r, the i-th coordinate of g = $\sum_{0 \le i < r} g_i x^i$</td></tr><tr><td>$|g|$:</td><td>the Hamming weight of g</td></tr><tr><td>supp(g):</td><td>{i, 0 ≤ i < r, g_i = 1}</td></tr><tr><td>$i \in g$:</td><td>$i \in \text{supp}(g)$</td></tr><tr><td>$h \subset g$:</td><td>$\text{supp}(h) \subset \text{supp}(g)$</td></tr><tr><td>$f = h \cup g$:</td><td>$f \in \mathcal{R}$ such that $\text{supp}(f) = \text{supp}(h) \cup \text{supp}(g)$</td></tr><tr><td>$f = h \cap g$:</td><td>$f \in \mathcal{R}$ such that $\text{supp}(f) = \text{supp}(h) \cap \text{supp}(g)$</td></tr></table>

### 2.1 Distance Spectrum

**Definition 1 (Distance Spectrum).** Let $\mathcal{R} = \mathbb{F}_2[x]/(x^r - 1)$ with r an odd prime integer, let $h \in \mathcal{R}$, and let $\delta$ be an integer such that $1 \le \delta \le r/2$.

- The coordinate distance is defined for all $0 \le i, j < r$ as

$$d(i, j) = \min(i - j \mod r, j - i \mod r), 1 \le d(i, j) < r/2.$$

- The multiplicity of $\delta$ in h is defined as

$$\mu_h(\delta) = |\{(i, j) \mid h_i = h_j = 1, 0 \le i < j < r, d(i, j) = \delta\}|.$$

- The distance spectrum of h is defined as

$$\text{Sp}(h) = (\mu_h(\delta))_{1 \le \delta < r/2} \in \mathbb{N}^{\lfloor r/2 \rfloor}.$$

Originally [4] the distance spectrum is defined as a subset of $\{1, \dots, (r-1)/2\}$. We use multiplicity vectors instead and we extend the set notation as follows: for any $S = (S_\delta)_{1 \le \delta < r/2}$ and $S' = (S'_\delta)_{1 \le \delta < r/2}$ in $\mathbb{N}^{\lfloor r/2 \rfloor}$, we denote $\delta \in S$ if $S_\delta > 0$ and $S \subset S'$ if $S_\delta \le S'_\delta$ for all $\delta$.

**Proposition 1 (Multiplicity Distribution [11]).** For all integers $\delta$, $1 \le \delta < r/2$, and $\nu \ge 0$, we have

$$\rho_{\nu}(r, d) = \text{Pr}[\mu_h(\delta) = \nu] = \frac{\binom{d}{\nu} \binom{r-d-1}{d-\nu-1}}{\binom{r-1}{d-1}}$$

for $h \in \mathcal{R}$ uniformly distributed of Hamming weight $d$.

*Some Basic Properties.*

- Monotony (strict): $h \subsetneq g \Rightarrow \text{Sp}(h) \subsetneq \text{Sp}(g)$, g, h $\in \mathcal{R}$.
  (strict because the coefficients of $\text{Sp}(h)$ add to $|h| \cdot (|h| - 1)/2$)

- Invariance under rotation: $\text{Sp}(x^i g) = \text{Sp}(g)$, $g \in \mathcal{R}$ and $0 \le i < r$.

- Invariance by mirroring: $\text{Sp}(\bar{g}) = \text{Sp}(g)$, $g \in \mathcal{R}$ and $\bar{g} = \sum_{0 \le i < r} g_{r-1-i} x^i$.
## 2.2 QC-MDPC Codes – BIKE

The key encapsulation mechanism BIKE derives from a Niederreiter-like public key encryption scheme based on QC-MDPC (Quasi-Cyclic Moderate Density Parity Check) codes. The main parameters are three integers $(r, w, t)$ such that $r$ is prime and 2 is a primitive root modulo $r$ (the codelength is $n = 2r$), with $w \approx t \approx \sqrt{n}$ and $d = w/2$ odd.

- $\mathcal{H}_w = \{(h_0, h_1) \in \mathbb{R}^2 \mid |h_0| = |h_1| = d = w/2\}$ the secret key space

- $\mathcal{E}_t = \{(e_0, e_1) \in \mathbb{R}^2 \mid |e_0| + |e_1| = t\}$ the error (or message) space

- $\Psi: \mathbb{R}^3 \to \mathcal{R}$ a QC-MDPC decoder

$[\Psi(e_0h_0 + e_1h_1, h_0, h_1) = (e_0, e_1) \text{ with probability close to 1 if } (h_0, h_1) \in \mathcal{H}_w \text{ and } (e_0, e_1) \in \mathcal{E}_t \text{ with appropriately selected parameters } (r, w, t)]$

- $(h_0, h_1) \in \mathcal{H}_w$ a secret key and $h = h_1h_0^{-1} \in \mathcal{R}$ its associated public key, encryption and decryption are defined as follows:

$$ \text{Enc}: \quad \mathcal{E}_t \times \mathcal{R} \to \mathcal{R} \quad \left| \quad \text{Dec}: \quad \mathcal{R} \times \mathcal{H}_w \to \mathcal{E}_t \\ (e_0, e_1), h \mapsto e_0 + e_1h \quad \left| \quad c, (h_0, h_1) \mapsto \Psi(ch_0, h_0, h_1) \right. $$

In the attack model that we will consider, the adversary knows the sparse polynomials $(e_0, e_1) \in \mathcal{E}_t$ and seeks the sparse secret polynomials $(h_0, h_1) \in \mathcal{H}_w$ by using information about the Hamming weight of the syndrome $e_0h_0 + e_1h_1$ which may leak from the decoding process $\Psi(e_0h_0 + e_1h_1, h_0, h_1)$. This may reveal the distance spectrum of $h_0$ or $h_1$ and allow the recovery of the secrets.

<table><caption>**Table 1.** BIKE Parameters</caption><thead><tr><th>level</th><th>r</th><th>w</th><th>t</th></tr></thead><tbody><tr><td>BIKE-1</td><td>12 323</td><td>142</td><td>134</td></tr><tr><td>BIKE-3</td><td>24 659</td><td>206</td><td>199</td></tr><tr><td>BIKE-5</td><td>40 973</td><td>274</td><td>264</td></tr></tbody></table>

**HQC.** In HQC, the decoding is not of the same nature. Still, in a known plain-text attack model, the adversary knows some sparse polynomials $(e, r_1, r_2) \in \mathbb{R}^3$ and seeks the sparse secret polynomials $(x, y) \in \mathbb{R}^2$ using information leakage which may occur during the decoding process $\text{Decode}(m\mathbf{G} + e')$, where $e' = e + r_1x + r_2y$. The situation is not identical, however we will see that if information about the weight of $e'$ leaks, then this may reveal the distance spectrum of $x$ or $y$ and allow the recovery of the secrets.

## 3 Key reconstruction from a full spectrum

This section presents an algorithm to reconstruct the key from a full spectrum. It is inspired from [4] which is the first of its kind in the context of code-based
cryptography. Starting from a distance spectrum $S$, it essentially consists in building an appropriate increasing sequence $f_0 \subset f_1 \subset \cdots \subset f_\ell$ of polynomials, defined below as an $S$-reconstruction sequence, which eventually converges to the solution.

**Definition 2.** Let $S \in \mathbb{N}^{\lfloor \frac{r}{2} \rfloor}$, an $S$-reconstruction sequence is an increasing sequence $f_0 \subset f_1 \subset \cdots \subset f_\ell$ of polynomials in $\mathcal{R}$ such that $\text{Sp}(f_\ell) \subset S$. It is valid if there exists $g \in \mathcal{R}$ such that $S = \text{Sp}(g)$ and $f_\ell \subset g$.

The algorithm recursively builds an $S$-reconstruction sequence and attempts to lengthen it in each possible way. It exits successfully when it finds $\text{Sp}(f_\ell) = S$ and backtracks when the sequence cannot be lengthened.

## 3.1 The $S$-extension

**Definition 3 (S-extension).** For any $S \in \mathbb{N}^{\lfloor r/2 \rfloor}$, the $S$-extension of $h \in \mathcal{R}$ is defined as

$$h^{(S)} = \sum_{i \in \mathcal{I}} x^i \text{ where } \mathcal{I} = \{i \mid 0 \le i < r, \text{Sp}(h \cup x^i) \subset S\}.$$

For any $h$ such that $\text{Sp}(h) \subset S$, its extension will contain any monomial that can be added to $h$ and keep a spectrum included in $S$.

**Lemma 1.** For all $g, h \in \mathcal{R}$ and $S \in \mathbb{N}^{\lfloor r/2 \rfloor}$, we have

$$(i) h \subset g \Rightarrow g^{(S)} \subset h^{(S)}$$

$$(ii) S = \text{Sp}(g) \Rightarrow g = g^{(S)}$$

*Proof.* Let $h \subset g$ and $i \in g^{(S)}$. We have $\text{Sp}(h \cup x^i) \subset \text{Sp}(g \cup x^i)$ and $\text{Sp}(g \cup x^i) \subset S$, thus $i \in h^{(S)}$. Let $S = \text{Sp}(g)$, if $i \in g$ then $g = g \cup x^i$ and $i \in g^{(S)}$. Because of the strict monotony of the spectrum, if $i \notin g$ then $g \subsetneq g \cup x^i$ and $S \subsetneq \text{Sp}(g \cup x^i)$, thus $i \notin g^{(S)}$. $\square$

The following proposition directly derives from Lemma 1.

**Proposition 2.** Let $S \in \mathbb{N}^{\lfloor r/2 \rfloor}$, we consider a valid $S$-reconstruction sequence $f_0 \subset f_1 \subset \cdots \subset f_\ell$. We have

$$\text{Sp}(f_\ell) \subset S \subset \text{Sp}(f_\ell^{(S)}) \text{ and } f_0^{(S)} \supset f_1^{(S)} \supset \cdots \supset f_\ell^{(S)}$$

and there exists $g \in \mathcal{R}$ such that $S = \text{Sp}(g)$ and $f_\ell \subset g \subset f_\ell^{(S)}$.

In the execution of the algorithm, if the reconstruction sequence $f_0 \subset f_1 \subset \cdots \subset f_\ell$ is valid at depth $\ell$ and grows towards a solution $g$, then the sequence of extension is decreasing towards $g$ and we have $f_\ell \subset g \subset f_\ell^{(S)}$. If the weight $d$ of $g$ is known, the reconstruction is complete if either $|f_\ell| = d$ or $|f_\ell^{(S)}| = d$.

For a valid reconstruction sequence, we observed that the weight of the extension decreases very quickly and provides a very efficient stopping condition.

For instance, for BIKE-1, as shown in Table 2, the extension in Algorithm 1 will provide a solution, i.e. $|f_\ell^{(S)}| = d = 71$, at depth typically 5 or 6 and never more than 12, whereas the Hamming weight of $f_\ell$ is at most $2\ell$ at depth $\ell$.
<table><caption>**Table 2.** Statistics for reconstruction sequences ($f_ℓ$)$_ℓ≥0$ for 10 000 executions of Algorithm 1 with BIKE-1 parameters $(r, d) = (12, 323, 71)$. To get consistent statistics, we set $f_i^{(S)} = f_ℓ^{(S)}$ for $i > ℓ$ such that $|f_ℓ^{(S)}| = d$ (though such $f_i$ are never computed).</caption><thead><tr><th>ℓ</th><th>Pr[|f<sub>ℓ</sub><sup>(S)</sup>| = d]</th><th>avg. |f<sub>ℓ</sub><sup>(S)</sup>|</th></tr></thead><tbody><tr><td>1</td><td>0</td><td>1422.13</td></tr><tr><td>2</td><td>0</td><td>253.68</td></tr><tr><td>3</td><td>0</td><td>99.23</td></tr><tr><td>4</td><td>0.0488</td><td>75.83</td></tr><tr><td>5</td><td>0.4953</td><td>71.93</td></tr><tr><td>6</td><td>0.8446</td><td>71.19</td></tr><tr><td>7</td><td>0.9599</td><td>71.04</td></tr><tr><td>8</td><td>0.9914</td><td>71.01</td></tr><tr><td>9</td><td>0.9971</td><td>71.00</td></tr><tr><td>10</td><td>0.9995</td><td>71.00</td></tr><tr><td>11</td><td>0.9999</td><td>71.00</td></tr><tr><td>12</td><td>1</td><td>71</td></tr></tbody></table>

## 3.2 Reconstruction algorithm

Given a distance spectrum $S = (S_δ)_{1≤δ≤r/2} ∈ N^{|r/2|}$, the Algorithm 1 seeks a polynomial $h ∈ R$ of weight $d$ such that $Sp(h) = S$. For every instance $S$ and prior to the root recursive call, a set $Δ$ of distances belonging to the spectrum must be selected. The step-by-step rationale is the following:

*Choosing Δ.* The sequence $Δ$ contains only values of $δ$ such that $S_δ > 0$ in any order. A given $δ$ cannot appear more than $S_δ$ times in the sequence. It is heuristically better to put the (first occurrence of) distances with the highest multiplicity at the beginning of the sequence $Δ$.

*Root Call.* The first step, depth $ℓ = 0$, can be made simpler. Because of the spectrum invariance by rotation, the first element in the reconstruction sequence can always be $1+x^{δ_0}$. In fact the root call of the recursive search will be `KeySearch`($ℓ = 1, g = 1+x^{δ_0}, S, Δ$). Hence, if we refer to a reconstruction sequence as in Definition 3, we have $f_0 = 0$ and $f_1 = 1+x^{δ_0}$.

*Adding Monomials in Pairs.* At depth $ℓ$, the input polynomial $g = f_ℓ$ is augmented by including two monomials $x^s + x^{s+δ_ℓ}$ for all $0 ≤ s < r$. Only the polynomials $f_{ℓ+1} = f_ℓ ∪ (x^s + x^{s+δ_ℓ})$ such that $(f_i)_{0≤i≤ℓ+1}$ remains an $S$-reconstruction sequence are kept in $H$.

*Stopping Conditions.* Invalid reconstruction sequences will quickly become impossible to lengthen ($H = \emptyset$), while valid reconstruction sequences will end up with $|f_ℓ^{(S)}| = d$ the weight of the target solution.

*Remark 1.* a. In the worst case the Algorithm 1 has an exponential complexity. In fact known algorithms in other fields for the “turnpike” or “beltway” problem are known to have worst case exponential time behavior [10]. It happens to be easy here, when the vector is sparse enough, but proving that the algorithm always succeeds early in that case seems challenging. At the moment,
<caption>**Algorithm 1 Reconstruction From Full Spectrum**</caption>

KeySearch: ($\ell, g, S, \Delta$) $\mapsto$ h
Input: $\ell \ge 0$, $g \in \mathcal{R}$, $S \in \mathbb{N}^{\lfloor \frac{\ell}{2} \rfloor}$, $\Delta = (\delta_i)_{i \ge 0} \subset S$
Output: $\perp$ or $h \in \mathcal{R}$ of Hamming weight $d$ such that $\text{Sp}(h) = S$
1: $\mathcal{H} \leftarrow \{h = g \cup (x^s + x^{s+\delta\ell}) \mid 0 \le s < r, \text{Sp}(h) \subset S \subset \text{Sp}(h^{(S)}), |h^{(S)}| \ge d\}$
2: **for** $h \in \mathcal{H}$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;**if** $|h^{(S)}| = d$ **then** **return** $h^{(S)}$
4: &nbsp;&nbsp;&nbsp;&nbsp;**f** $\leftarrow$ KeySearch($\ell + 1$, $h$, $S$, $\Delta$)
5: &nbsp;&nbsp;&nbsp;&nbsp;**if** $f \ne \perp$ **then** **return** $f$
6: **return** $\perp$

we simply give empirical evidence that the algorithm almost always succeeds
in limited running time for parameters of interest.

b. Algorithm 1 without multiplicities, i.e. $S_{\delta} \in \{0, 1\}$, works essentially the same way.

c. The algorithm returns a polynomial whose spectrum is equal to $S$. Because of the spectrum invariance under rotation and by mirroring, and depending on the context of the attack, checking and rotating or reversing might be necessary.

**3.3 Results and Comparison**

Our algorithm performs orders of magnitude faster than previous techniques,
with the possible exception of [5] which has similar features as our algorithm
but whose performance is not very precisely documented. Compared with [9,8]
we observe a gain of a factor 1000 to 10 000 for similar parameters.

For BIKE-1 parameters, $(r, d, t) = (12323, 71, 134)$, our implementation of Algorithm 1 recovers $h_0$ from its full spectrum in about 2 milliseconds (on average over a few thousand independent executions). Using the syndrome weight as observable, the model of §3 and our experiments agree, and we get a faultless full spectrum 50% of the time with 2 million queries, and 95% of the time with 2.7 million queries.

We give later in the paper more details about our experiments for BIKE, for
other observables and for other schemes.

4 Reconstruction from a partial spectrum

In a practical scenario the full spectrum might not be available. Typically, the
least reliable distances cannot be confidently classified as inside or outside the
spectrum, and the reconstruction strategy is adapted. In [9] partial information
is handled by design and the algorithm in [8] is adapted to partial information
in [7].
## 4.1 Reconstruction Algorithm

For a given $S \in \mathbb{N}^{\lfloor \frac{r}{2} \rfloor}$, we assume that we know two tuples $S^{lo}$ and $S^{hi}$ in $\mathbb{N}^{\lfloor \frac{r}{2} \rfloor}$ such that $^5S^{lo} \subset S \subset S^{hi}$.

**Rationale:** Algorithm 1 gradually builds $S$-reconstruction sequences $(f_\ell)_{\ell \ge 0}$ and their $S$-extension $(f_\ell^{(S)})_{\ell \ge 0}$, a sequence is valid at step $\ell$ if $S \subset \text{Sp}(f_\ell^{(S)})$. If only bounds $S^{lo} \subset S \subset S^{hi}$ are available, the reconstruction is adapted as follows:

*Enlarged Search Space.* Any $S$-reconstruction sequence is also a $S^{hi}$-reconstruction sequence, thus if we explore all $S^{hi}$-reconstruction sequences we will explore in particular all $S$-reconstruction sequences. We explore more sequences, but we will eventually explore those that provide the solutions.

*Weaker Pruning Criterion.* The condition $S^{hi} \subset \text{Sp}(h^{(S^{hi})})$ is too strong and may discard sequences that are valid for $S$ (but invalid for $S^{hi}$). Instead the test $S^{lo} \subset \text{Sp}(h^{(S^{hi})})$ will never exclude a valid $S$-reconstruction sequence.

Hence the adapted Algorithm 2 will eventually reach a complete valid reconstruction sequence and a solution. Note that in addition, the set $\Delta$ must only contain distances that are in the spectrum, i.e. elements of $S^{lo}$.

**Algorithm 2 Reconstruction From Partial Spectrum**

KeySearch: $(\ell, g, S^{hi}, S^{lo}, \Delta) \mapsto h$
Input: $\ell \ge 0$, $g \in \mathcal{R}$, $S^{hi}$, $S^{lo} \subset \{1, \dots, \lfloor r/2 \rfloor\}$, $\Delta = (\delta_i)_{i \ge 0} \subset S^{lo}$
Output: $\perp$ or $h \in \mathcal{R}$ such that $|h| = d$ and $S^{lo} \subset \text{Sp}(h) \subset S^{hi}$
1: $\mathcal{H} \leftarrow \{h = g \cup (x^s + x^{s+\delta_\ell}) \mid 0 \le s < r, \text{Sp}(h) \subset S^{hi}, S^{lo} \subset \text{Sp}(h^{(S^{hi})}), |h^{(S^{hi})}| \ge d\}$
2: **for** $h \in \mathcal{H}$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;**if** $|h^{(S^{hi})}| = d$ **then** **return** $h^{(S^{hi})}$
4: &nbsp;&nbsp;&nbsp;&nbsp;**f** $\leftarrow \text{KeySearch}(\ell + 1, h, S^{hi}, S^{lo}, \Delta)$
5: &nbsp;&nbsp;&nbsp;&nbsp;**if** $f \ne \perp$ **then** **return** $f$
6: **return** $\perp$

## 4.2 Results and Comparison

The use of a partial spectrum was already considered in previous works. The algorithm in [9] has a different logic and direct comparison is difficult. The authors claim a reduction of 20% for the number of queries. The algorithm in [8] is comparable to ours, the authors measure the efficiency of their technique in terms of the proportion of unreliable distances (referred to as “suspicious”). Comparison is not straightforward but the order of magnitude for the amount of data needed to achieve the reconstruction seems to be the same. Algorithmic complexity is higher as for the full spectrum case.

<footnote n="5">⁵ recall that $(S_i)_i \subset (S'_i)_i$ iff $S_i \le S'_i$ for all $i$</footnote>
## Key Features:

**Impact of the Tightness of the Bounds.** Our experiments have highlighted the fact that a tight upper bound $S^{hi}$ is much more important than a tight lower bound $S^{lo}$. Indeed, a loose upper bound may dramatically increase the number of paths that are explored recursively in the search space, while a loose lower bound will only delay the point when the reconstruction sequence is found invalid, without necessarily blowing up the number of paths in the search tree. For BIKE Level 1, the lower bound $S^{lo}$ can be as low as 1% of the whole spectrum, whereas the running time blows up when the upper bound size exceeds 160% of the spectrum size, as shown in Table 3. Note also that with an exact upper bound the average running time with a 1% lower bound is only 4 ms instead of 2 ms with an exact lower bound.

<table><caption>**Table 3.** Average running time in seconds of Algorithm 2 for BIKE-1 parameters $(r, d) = (12323, 71)$ depending on the size of $S^{hi}$. The size of $S^{lo}$ is fixed to 1% of $|S|$.</caption><thead><tr><th>$S^{hi}$ / $|S|$</th><th>100%</th><th>120%</th><th>130%</th><th>140%</th><th>150%</th><th>160%</th></tr></thead><tbody><tr><td>Average running time (s)</td><td>0.004</td><td>0.03</td><td>0.1</td><td>0.37</td><td>2.2</td><td>13.13</td></tr></tbody></table>

**Connection with the Model.** Properly selecting $S^{lo}$ and $S^{hi}$ from the observable obeys to simple general rules but the process needs to be empirically adjusted for each set of parameters. We want to determine the smallest size for the sample set $\mathcal{E}$ such that there exists an upper limit $L$ for $F_{\delta}(\mathcal{E}, (h_0, h_1))$ (see Figure 2) which verifies simultaneously:

(1) the upper bound $S^{hi} = \{\delta | F_{\delta} \le L\}$ is small enough, e.g. from Table 3 not more than $1.6 \cdot |S|$ for BIKE-1,

(2) the probability $p = \Pr[\text{Sp}(h_0) \subset S^{hi}]$ to have the whole spectrum of the target secret below $L$ is high enough.

(as mentioned above, the lower limit for $F_{\delta}$ is never an issue and can be set relatively low)

Using the model of §6 for the syndrome weight observable and for BIKE-1 parameters, we need $|\mathcal{E}| \approx 550\,000$ for a success probability $p = 0.5$ and $|\mathcal{E}| \approx 750\,000$ for a success probability $p = 0.95$. Those numbers match with our experiments and are less than a third of what is needed to obtain a full spectrum.

# 5 Key Recovery from a Soft Distance Spectrum

When the number of queries reduces and there are too many unreliable distances, the partial spectrum approach fails. We either have too few data and the search becomes intractable or we have faults in the data and the algorithm fails.

To address this problem, we keep all the data and assign to each distance $\delta$ a probability distribution over all possible multiplicities, based on the observation.
<figure><img src="image_3.png" /><figcaption>Fig. 2. $F_{\delta}(\mathcal{E}, (h_0, h_1))$ with $f(e_0, h_0) = |e_0h_0 + e_1h_1|$ and $|\mathcal{E}| = 7 \cdot 10^5$ for BIKE-1</figcaption></figure>

## 5.1 Handling Soft Information

We define a soft distance spectrum as a tuple of probability distributions

$$S = (S_{\delta,\nu})_{1\le\delta\le r/2, \nu\ge 0}. \qquad (3)$$

Such a tuple can be obtained by modeling the observation as explained in Figure 5 of §6. For each distance $\delta$, the sequence $(S_{\delta,\nu})_{\nu\ge 0}$ is a probability distribution with $S_{\delta,\nu}$ the probability to have $\nu = \mu_{h_0}(\delta)$, where $h_0$ is the target sparse secret polynomial of Hamming weight $d$.

**Definition 4 (Score Function).** Given $S = (S_{\delta,\nu})_{1\le\delta\le r/2, \nu\ge 0}$ a soft distance spectrum and a polynomial $h \in \mathcal{R}$ we define the score as

$$\text{score}(h, S) = \sum_{1 \le \delta \le r/2} \log \left( \sum_{\nu \ge \mu_h(\delta)} S_{\delta, \nu} \right). \qquad (4)$$

The score of $(h, S)$ essentially measures the (log of the) probability for a polynomial $h$ to have its distance spectrum smaller than the distance spectrum of the secret polynomial whose observation led to the soft spectrum $S$. It is a negative number, and the highest values, i.e. closest to zero, are obtained for polynomials that have the highest probability to be included in a solution.

**Definition 5 (Soft Extension).** Given $S = (S_{\delta,\nu})_{0<\delta<r/2, \nu\ge 0}$ a soft distance spectrum and a polynomial $h \in \mathcal{R}$ we define a soft $S$-extension of $h$ as a tuple of all monomials $x^i$, $0 \le i < r$ sorted in decreasing order of score(h $\cup$ x$^i$, S), that is

$$h^{(S)} = (x^{j_0}, x^{j_1}, \dots, x^{j_{r-1}})$$

where score(h $\cup$ x$^{j_i}$, S) $\ge$ score(h $\cup$ x$^{j_{i+1}}$, S) for all $i = 0, \dots, r-2$. We will denote $h^{(S)}[\ell] = x^{j_0}$ and $h^{(S)}[0:d] = \sum_{0 \le \ell < d} h^{(S)}[\ell] = x^{j_0} + \dots + x^{j_{d-1}}$.

## 5.2 Reconstruction algorithm

*Rationale:* As for Algorithm 1, the reconstruction will recursively explore a reconstruction sequence $f_0 \subset f_1 \subset \dots \subset f_\ell$ and try to lengthen it in all plausible ways. The soft extension is used, as the extension in Algorithm 1, to extract
the solution at an early stage. Hopefully, as when the extension has weight $d$ in Algorithm 1, when we hit a solution, the first $d$ monomials of the soft extension correspond to scores that are clearly better than the last $r-d$, and the solution is formed by those $d$ monomials.

Step by step:

- Choice of $\Delta$. It is best to use the distances that have the highest chances to belong to the spectrum. We place in $\Delta$ the distances $\delta$ in decreasing order of the expected multiplicity $\sum_{\nu} \nu S_{\delta,\nu}$.

- At each recursive call of depth $\ell$, the input polynomial $g$ is augmented into $h$ by adding (at most) two monomials $x^s + x^{s+\delta_\ell}$. We keep in $\mathcal{H}$ the values of $h$ that have a score higher than a threshold $T_\ell$ which depends on $\ell$ and is determined empirically.

- For each $h \in \mathcal{H}$, we compute its soft $S$-extension: a score for each monomial $x^i$, $0 \le i < r$, reflecting how likely is $h \cup x^i$ to belong to a solution given the soft spectrum $S$. We explore first the $h$ that have the best $d$ scores, in fact we look at the highest score($h \cup x^i$, $S$) where $x^i = h^{(S)}[d-1]$ is the $d$-th best monomial for $h$.

- If $h^{(S)}[0:d]$, the sum of the best $d$ monomials for $h$, is not a solution the recursive search continues at depth $\ell+1$ with input $h$.

The algorithm is depth-first search. Pruning will happen when $\mathcal{H} = \emptyset$. The choice of the thresholds, or of any other rule to build the set of candidates $\mathcal{H}$, is empirical and must be fine-tuned for each set of parameters.

<caption>**Algorithm 3 Reconstruction From Soft Spectrum**</caption>

KeySearch: $(\ell, g, S, \Delta) \mapsto h$
Input: $\ell \ge 0$, $g \in \mathcal{R}$, $S$, $\Delta = (\delta_i)_{i \ge 0}$
Output: $\perp$ or $h \in \mathcal{R}$ such that $|h| = d$
1: $\mathcal{H} \leftarrow \{h = g \cup (x^s + x^{s+\delta_\ell}), 0 \le s < r, \text{score}(h, S) > T_\ell\}$
   $\triangleright$ $(T_\ell)_{\ell \ge 0}$ determined empirically
2: **for** $h \in \mathcal{H}$ **in decreasing order of score(h + h^{(S)}[d-1], S)** **do**
3:     **if** "$h^{(S)}[0:d]$ is good" **then** return $h^{(S)}[0:d]$
4:     **f** $\leftarrow$ KeySearch($\ell + 1$, $h$, $S$, $\Delta$)
5:     **if** $f \ne \perp$ **then** return $f$
6: **return** $\perp$

The assertion "$h^{(S)}[0:d]$ is good" is admittedly a bit vague. In practice, in our cryptographic context, it is always possible to test the solution (and its reverse) against the public key. But, since it would be expensive to do that for all elements of $\mathcal{H}$, an efficient filter consists in looking at the $d$-th and the $(d+1)$-th best scores in the soft extension. If we do not see a significant drop then we continue the execution without performing the full test. In practice, this heuristic filter selects the valid solutions and only them.
Empirically, we found that it was more efficient to select for $\mathcal{H}$ the augmented
polynomials with a score high enough, but to browse through $\mathcal{H}$ in an order
depending on the score of the soft extension. As it is written, though it is unlikely,
the algorithm may fail to find a solution even with unlimited time. A more
elaborate logic might provably exhaust the search space, but we do not believe
it could reduce the order of magnitude of the practical complexity nor of the
success rate.

## 5.3 Results

To recover a full spectrum for BIKE-1, more than 2 million queries are required, in order to perfectly distinguish between multiplicities (stripes in scatter plot). With a soft spectrum, the reconstruction succeeds with 200 000 queries, about one tenth of the amount needed to get the full spectrum.

# 6 Observables and Models

We consider a cryptographic protocol which involves an encryption scheme based
on QC-MDPC codes (e.g. BIKE). For a given secret key, a pair of sparse poly-
nomials, the adversary can make queries with known plaintexts and can observe
a quantity, an *observable*, related to the distance spectrum of the sparse secret
key. This observable can be the decoding failure rate [4], the timing [2], the syn-
drome weight [2], or, more generally, any quantity that can be observed from a
side-channel.

Here, we will focus on the syndrome weight. As remarked in [4,2], this quantity influences the decoding failure rate and the timing of the bit-flipping decoder of QC-MDPC codes. Failure and timing strongly depend on the parameter choice and on the exact variant of the decoding algorithm, while in contrast, the syndrome is a fundamental quantity of the scheme that inevitably appears during the decoding process. Its Hamming weight is thus prone to leakage, independently of any choice of parameters and algorithms. One of the purposes of this work is to expose and understand the vulnerabilities stemming from that.

An additional benefit of the syndrome weight as an observable is that it
can also be used for HQC. Though there is no decoding in it, HQC features a
fundamental quantity similar to the syndrome and which also depends on the
plaintext and on sparse secrets. Experiments show that if this quantity can be
observed, it reveals the distance spectrum of the secrets as for BIKE.

## 6.1 Attack Model

For a given secret key $\mathbf{s}\mathbf{k} = (\mathbf{h}_0, \mathbf{h}_1) \in \mathcal{H}_w$ and a known error pattern $\mathbf{e} = (\mathbf{e}_0, \mathbf{e}_1) \in \mathcal{E}_t$, the adversary may query a decryption oracle and observe a randomized numerical value $f(\mathbf{e}_0, \mathbf{h}_0)$ which we refer to as an *observable*. The key property of an observable for our purpose is that the expectation of $\mu_{\mathbf{e}_0}(\delta) f(\mathbf{e}_0, \mathbf{h}_0)$
when e is uniformly distributed differs with $\mu_{h_0}(\delta)$. Hence, after observing multiple queries for the same secret key and a sample set of errors $\mathcal{E} \subset \mathcal{E}_t$, the adversary computes for all $\delta$, $1 \le \delta \le r/2$, the quantity

$$F_{\delta}(\mathcal{E}, (h_0, h_1)) = \frac{1}{\sum_{e \in \mathcal{E}} \mu_{e_0}(\delta)} \sum_{e \in \mathcal{E}} \mu_{e_0}(\delta) f(e_0, h_0) \quad (5)$$

and guesses $\mu_{h_0}(\delta)$ from $F_{\delta}$.

In this work, we will favor a scenario in which the adversary strictly follows the protocol, i.e. queries are made with uniformly distributed errors of Hamming weight $t$.

## 6.2 Model for BIKE's Syndrome Weight

The following proposition is proven in appendix.

**Proposition 3.** For all $(h_0, h_1) \in \mathcal{H}_w$ and all $\delta$, $1 \le \delta \le r/2$, we have

$$\frac{\sum_{(e_0, e_1) \in \mathcal{E}_t} \mu_{e_0}(\delta) |e_0 h_0 + e_1 h_1|}{\sum_{(e_0, e_1) \in \mathcal{E}_t} \mu_{e_0}(\delta)} = W_{\mu_{h_0}(\delta)}(n, w, t), \quad (6)$$

where for all integer $\nu \ge 0$

$$W_{\nu}(n, w, t) = (n/2 - w + \nu) \cdot S(n-2, w, t-2) + \nu \cdot S(n-2, w-2, t-2) \\ + (w-2\nu) \cdot (1 - S(n-2, w-1, t-2)), \quad (7)$$

with

$$S(n, w, t) = \sum_{i \text{ odd}} \frac{\binom{w}{i} \binom{n-w}{t-i}}{\binom{n}{t}}.$$

*Remark 2.* a. Each value of $W_{\nu}$ corresponds to a stripe in the observation diagram or to a bump in the measured density (see Figure 1 for instance). Note that the difference $W_{\nu} - W_{\nu+1}$ is independent of $\nu$.

b. A formula similar to (6) is given in [2] and [5]. It measures an average syndrome weight conditioned by $\nu = \mu_{h_0}(\delta)$ and gives an approximation rather than an identity as we have here. This is commented further later in this section.

c. The proportion $\rho_{\nu}(r, d)$ of distances $\delta$, $1 \le \delta \le r/2$, that appear in the spectrum of an element of $\mathcal{R}$ of weight $d$ with multiplicity exactly $\nu$ is given in [11] (given here in Proposition 1). Together with the above proposition those numbers will characterize the model for the density of $F_{\delta}$. For instance for BIKE-1

<table><thead><tr><th>ν</th><th>W<sub>ν</sub></th><th>ρ<sub>ν</sub></th></tr></thead><tbody><tr><td>0</td><td>4869.007</td><td>0.667</td></tr><tr><td>1</td><td>4868.573</td><td>0.272</td></tr><tr><td>2</td><td>4868.139</td><td>0.054</td></tr><tr><td>3</td><td>4867.705</td><td>0.007</td></tr></tbody></table>
**Modeling with a Combination of Normal Distributions.** From the above proposition, for any $(h_0, h_1)$ and any $\delta$, the average value of $F_\delta(\mathcal{E}, (h_0, h_1))$ as defined in (5) with $f(e_0, h_0) = |e_0h_0 + e_1h_1|$ over all possible choice of $\mathcal{E} \subset \mathcal{E}_t$ is equal to $W_\nu(n, w, t)$ where $\nu = \mu_{h_0}(\delta)$. From our observation, which is consistent with other works, e.g. [5,7], the probability $\Pr[F_\delta = x | \nu = \mu_{h_0}(\delta)]$ is accurately modeled by a normal distribution $\mathcal{N}(W_\nu, \sigma^2)$. The mean$^6$ $W_\nu$ derives from Proposition 3. The standard deviation $\sigma$ is determined empirically and we observed in our experiments that, independently of $\nu$, it is close to $\sigma_0/\sqrt{N}$ where $N = |\mathcal{E}|$ and $\sigma_0$ only depends on the system parameters $(n, r, w, d, t)$. The probability density function of $F_\delta(\mathcal{E}, (h_0, h_1))$ for a given $\nu = \mu_{h_0}(\delta)$ is well modeled by

$$ \varphi_\nu(x) = \frac{\sqrt{|\mathcal{E}|}}{\sigma_0\sqrt{2\pi}}\exp\left(-\frac{|\mathcal{E}|}{2\sigma_0^2}(x - W_\nu)^2\right), \qquad (8) $$

and, denoting $\rho_\nu$ the proportion of distances of multiplicity $\nu$ given in Proposition 1, we get the following model for the probability distribution function of $F_\delta(\mathcal{E}, (h_0, h_1))$

$$ \varphi(x) = \sum_{\nu \ge 0} \rho_\nu \varphi_\delta(x). \qquad (9) $$

We observe in Figure 3, for $|\mathcal{E}| = 10^6$ and BIKE-1 parameters, that the model in dashed blue is relatively close to the measured density in red.

<figure><img src="image_4.png" /><figcaption>**Fig. 3.** Density of $F_\delta(\mathcal{E}, (h_0, h_1))$ for all distances $\delta$ and for $(r, d, t) = (12323, 71, 134)$, $w = 142$, $n = 24646$. The observed density is in red and the model in dashed blue.</figcaption></figure>

**Centering the Model and the Observation.** For BIKE-1 parameters, the expected syndrome weight is equal to $r \cdot S(n, w, t) = 4868.831$ while for the error patterns in $\mathcal{E}$ used in Figure 3, the average is 4868.848. The difference is +0.017, small but measurable. If we compare $W_\nu$ with the measured average values of

<footnote>$^6$ here and in similar situations throughout the paper we dropped the arguments $(n, w, t)$ as there is no ambiguity in the context</footnote>
$F_\delta$ conditioned with $\nu$ we observe the same difference in the whole range:

<table><thead><tr><th>ν</th><th>W<sub>ν</sub>(n, w, t)</th><th>avg. F<sub>δ</sub></th><th>ν</th><th>difference</th></tr></thead><tbody><tr><td>0</td><td>4869.007</td><td>4869.023</td><td></td><td>+0.016</td></tr><tr><td>1</td><td>4868.573</td><td>4868.588</td><td></td><td>+0.015</td></tr><tr><td>2</td><td>4868.139</td><td>4868.159</td><td></td><td>+0.020</td></tr><tr><td>3</td><td>4867.705</td><td>4867.726</td><td></td><td>+0.021</td></tr></tbody></table>

In fact, a close observation of Figure 3 reveals that the measured data, the red curve, is slightly shifted to the right compared to the model. This shift could go left as well. This variation is expected as the standard deviation of the syndrome weight is relatively high, e.g. ≈ 50 for BIKE-1 parameters, and for instance if $N = |\mathcal{E}| = 10^6$, the standard deviation of the average syndrome weight is still ≈ $50/\sqrt{N} = 0.05$ which is not so small compared to the difference $W_ν - W_{ν+1} \approx 0.434$ we are trying to detect.

This can be handled by centering. We subtract the average syndrome weight $r \cdot S(n, w, t)$ from the modeled distribution function input, and we subtract the observed average syndrome weight from $F_\delta$. We get a centered model

$$ \bar{\varphi}_{\nu}(x) = \varphi_{\nu}(x - r \cdot S(n, w, t)) \quad \text{and} \quad \bar{\varphi}(x) = \sum_{\nu \ge 0} \rho_{\nu} \bar{\varphi}_{\delta}(x) \quad (10) $$

and a centered observation

$$ \bar{F}_{\delta}(\mathcal{E}, (h_0, h_1)) = F_{\delta}(\mathcal{E}, (h_0, h_1)) - \frac{1}{|\mathcal{E}|} \sum_{(e_0, e_1) \in \mathcal{E}} |e_0 h_0 + e_1 h_1| \quad (11) $$

which give a more accurate estimate of the multiplicities and their reliability.

<figure><img src="image_5.png" /><figcaption>**Fig. 4.** Density of $\bar{F}_\delta(\mathcal{E}, (h_0, h_1))$ for all $\delta$ splitted according to $\nu = \mu_{h_b}(\delta)$ ($\nu = 0$ in red, $\nu = 1$ in blue, $\nu = 2$ in green, $\nu \ge 3$ not represented), the model $\rho_\nu \bar{\varphi}_\nu(x)$ appears in dashes. The cumulated value $\bar{F}_\delta$ is shown in dotted black.</figcaption></figure>

**Soft Information from the Centered Average Syndrome Weight.** To use the soft input algorithm of §5, we need to build a soft distance spectrum (3) from the observation. For each $\delta$ and each $\nu$, according to the model, the
probability to have $\mu_{h_0}(\delta) = \nu$ given the (centered) observation $\bar{F}_\delta$ is

$$ \mathrm{Pr} [\mu_{h_b}(\delta) = \nu | \bar{F}_\delta = x] = \frac{\rho_\nu \cdot \bar{\varphi}_\nu(x)}{\bar{\varphi}(x)}. $$

From this we can obtain the soft distance spectrum, the process is summed up in Figure 5.

For a given secret key $(h_0, h_1)$, the observable $f(e_0, h_0) = |e_0h_0 + e_1h_1|$ is known for all $(e_0, e_1)$ in the sample set $\mathcal{E} \subset \mathcal{E}_t$. The soft distance spectrum used in Algorithm 3 is defined for all $\delta$, $1 \le \delta \le r/2$, and all $\nu \ge 0$ by

$$ S_{\delta, \nu} = \frac{\rho_{\nu}(r, d) \cdot \bar{\varphi}_{\nu}(\bar{F}_{\delta}(\mathcal{E}, (h_0, h_1)))}{\bar{\varphi}(\bar{F}_{\delta}(\mathcal{E}, (h_0, h_1)))} $$

where $\bar{F}_\delta$ is defined by (5) and (11), $\bar{\varphi}$ and $\bar{\varphi}_\nu$ are defined by (9), (8) and (10), and $\rho_\nu$ is defined in Proposition 1.

<caption>**Fig. 5.** Soft Distance Spectrum for BIKE When the Observable is the Syndrome Weight</caption>

**Comment About the Use of the Weighted Average.** In our modeling, we have considered for $F_\delta$ the average of $f(e_0, h_0)$ weighted with the error multiplicity (5) rather than simply the average of $f(e_0, h_0)$ for error patterns such that $\delta \in \mathrm{Sp}(e_0)$

$$ F'_{\delta} = \frac{1}{|\mathcal{E}_{\delta}|} \sum_{e_0 \in \mathcal{E}_{\delta}} f(e_0, h_0) \text{ where } \mathcal{E}_{\delta} = \{e \in \mathcal{E} \mid \delta \in \mathrm{Sp}(e_0)\} $$

as in previous works [2,5]. The main benefit is a larger difference between the stripes. For BIKE-1 parameters, we get

<table><thead><tr><th>ν</th><th>avg. F'<sub>δ</sub></th><th>ν</th><th>avg. F<sub>δ</sub></th><th>ν</th><th>W<sub>ν</sub></th></tr></thead><tbody><tr><td>0</td><td>4868.9778</td><td>1</td><td>4868.5704</td><td>4868.5733</td><td></td></tr><tr><td>1</td><td>4868.6144</td><td>2</td><td>4868.1360</td><td>4868.1391</td><td></td></tr><tr><td>2</td><td>4868.2496</td><td>3</td><td>4867.7081</td><td>4867.7049</td><td></td></tr><tr><td>3</td><td>4867.9006</td><td></td><td></td><td></td><td></td></tr></tbody></table>

The above table compares the average values of $F'_\delta$ and $F_\delta$ for a given $\nu$. We observe a difference of 0.36 in the first column rather than 0.43 in the second. Thus $F_\delta$ will be better to discriminate between the multiplicities. Another benefit is the Proposition 3 which gives a closed formula (7) for $W_\nu$ which is met, on average, by $F_\delta$. Previous works also give the formula (7) for the average syndrome weight but the small deviation with experiments was already observed [2].
# 7 Variants and Numerical Results

The framework we have described can be applied to other observables $f(e_0, h_0)$ for BIKE. It is relevant if the average value of $\mu_{e_0}(\delta) \cdot f(e_0, h_0)$ differs with the multiplicity of $\delta$ in the spectrum of $h_0$. The model, i.e. the (centered) probability density functions $\bar{\phi}_{\nu}$ for $\nu \ge 0$, which can be established empirically by simulation if not available theoretically, will allow the construction of soft distance spectra to be used in Algorithm 3.

In this section, we first give numerical results for all security levels of BIKE when the observable is the syndrome weight. Then we will consider other relevant observables, timing or noisy syndrome weight, which are closer to the kind of leakage that can occur in practical situation. Finally, we show how the framework, observable and model, can be applied to recover sparse secret polynomials in HQC. The code used to obtain the results in this section is available at https://github.com/m-salom/key_rec_spectrum.

## 7.1 Syndrome Weight

We first summarize the results considering the Hamming weight of the syndrome as an observable, i.e. $f(e_0, h_0) = |e_0h_0 + e_1h_1|$, which was considered throughout this paper.

**Full Spectrum.** A full spectrum is obtained when there is a complete separation between distances with multiplicity 0 and 1. We want to determine the smallest size of $|\mathcal{E}|$ such that the full spectrum is exactly corresponding to the set of distances below some limit $L$ with probability $p$. We set $L = \frac{W_0+W_1}{2}$.

Using the model described in §6, Table 4 reports the minimal number of queries $|\mathcal{E}|$ to obtain a full spectrum with success probabilities $p = 0.5$ and $p = 0.95$, for different BIKE security levels.

<table><caption>**Table 4.** Minimal size of $\mathcal{E}$ in millions of queries to have a full spectrum with probability $p$ for 3 levels of BIKE.</caption><thead><tr><th></th><th>$p = 0.5$</th><th>$p = 0.95$</th></tr></thead><tbody><tr><td>BIKE-1</td><td>2</td><td>2.7</td></tr><tr><td>BIKE-3</td><td>5.2</td><td>7</td></tr><tr><td>BIKE-5</td><td>11</td><td>14.6</td></tr></tbody></table>

**Soft Spectrum.** The soft spectrum can be obtained using the process described in Figure 5. Table 5 gives the number of queries and average running time required to successfully recover the key using soft information in Algorithm 3 on BIKE-1 parameters. The algorithm always terminates but sometimes without recovering the key. The average running time is computed over successful runs.
We achieve the reconstruction of the key 50% of the time with 200 000 queries, about one tenth of the amount needed to get the full spectrum.

<table><caption>**Table 5.** Minimal size of $\mathcal{E}$ and average running time in seconds to recover the key with Algorithm 3 with probability $p$ for BIKE-1 parameters.</caption><thead><tr><th></th><th>p = 0.5</th><th>p = 0.95</th></tr></thead><tbody><tr><td>|E|</td><td>200 000</td><td>300 000</td></tr><tr><td>Avg running time (s)</td><td>155</td><td>70</td></tr></tbody></table>

## 7.2 Noisy Syndrome Weight

In a practical side-channel attack, an attacker may have access to a noisy version of the syndrome weight. To better reflect a realistic scenario, we extend the framework to noisy observations of the form:

$$f(e_0, h_0) = |e_0h_0 + e_1h_1| + \mathcal{N}(0, \sigma^2)$$

where the noise is modeled with a Gaussian distribution of mean 0 and of standard deviation $\sigma$ which is a common model in side-channel contexts.

Being more specific would require targeting a specific implementation, which is out of the scope of this paper. The point of this section is to establish that our work applies to any side-channel leaking information correlated to the syndrome weight.

**Full Spectrum.** The experiments were run for three levels of noise that were chosen arbitrarily for BIKE-1 parameters. Using the model of §6 adapted to take the noise into account, Table 6 shows the minimal number of queries needed to recover a full spectrum with different probabilities.

<table><caption>**Table 6.** Minimal size of $\mathcal{E}$ in millions of queries to have a full spectrum with probability $p$ for different levels of noise $\sigma$ for BIKE-1 parameters.</caption><thead><tr><th></th><th>p = 0.5</th><th>p = 0.95</th></tr></thead><tbody><tr><td>σ = 10</td><td>2</td><td>2.7</td></tr><tr><td>σ = 30</td><td>2.2</td><td>3</td></tr><tr><td>σ = 50</td><td>2.7</td><td>3.6</td></tr></tbody></table>

**Soft Spectrum.** Increasing the noise level impacts the benefit of using soft information. As shown in Table 7, when the noise increases, the gain provided by soft information decreases from a factor 10 in the noiseless case to 6.75 for $\sigma = 50$.
<table><caption>**Table 7.** Minimal size of $\mathcal{E}$ and average running time in seconds to recover the key with Algorithm 3 with probability 0.5 for different levels of noise $\sigma$ for BIKE-1 parameters.</caption><thead><tr><th></th><th>|E|</th><th>Avg running time (s)</th></tr></thead><tbody><tr><td>σ = 10</td><td>200 000</td><td>205</td></tr><tr><td>σ = 30</td><td>280 000</td><td>259</td></tr><tr><td>σ = 50</td><td>400 000</td><td>304</td></tr></tbody></table>

## 7.3 Timing Attack

Another observable we considered is the number of iterations in the bit-flipping algorithm: $f(e_0, h_0) = i$. This quantity may be measured through a side-channel like timing and is correlated to the syndrome weight hence, it behaves the same way.

The main point of this section is to observe that the weighted average (i.e. weighting the average observation with the error multiplicity) is relevant for timing, as we believe it is for any observable in this framework. We did not consider soft information in this case, though it could be done after building an empirical observation model from simulations.

**Full Spectrum.** Following the initial scenario namely strictly following the protocol, for BIKE-1 parameters $(r, d, t) = (12323, 71, 134)$, the experiments show that this observable requires a significantly higher amount of queries than the syndrome weight, about 1000 times more. To recover a full spectrum, we need $|\mathcal{E}| \approx 2.2$ billion for a success probability $p = 0.5$ and $|\mathcal{E}| \approx 3$ billion for a success probability $p = 0.95$. Those numbers seem hard to reach in practice.

To deal with this issue, we can consider a scenario in which the error weight $t$ can be increased. The experiments for BIKE-1 parameters with an increased error weight $(r, d, t) = (12323, 71, 180)$ show that more queries are still needed than with the syndrome weight, but the factor drops to 20 instead of 1000. We need $|\mathcal{E}| \approx 40$ million for a success probability $p = 0.5$ and $|\mathcal{E}| \approx 55$ million for a success probability $p = 0.95$ to recover a full spectrum.

**Weighted Average.** For this observable, we have again considered the average of $f(e_0, h_0)$ weighted with the multiplicity in the error. Just like for the syndrome weight, it allows a better discrimination between multiplicities:

<table><thead><tr><th></th><th colspan="2">(12323, 71, 134)</th><th colspan="2">(12323, 71, 180)</th></tr><tr><th>ν</th><th>avg. F'<sub>δ</sub> | ν</th><th>avg. F<sub>δ</sub> | ν</th><th>avg. F'<sub>δ</sub> | ν</th><th>avg. F<sub>δ</sub> | ν</th></tr></thead><tbody><tr><td>0</td><td>2.999572</td><td>2.9995727</td><td>8.884984</td><td>8.885543</td></tr><tr><td>1</td><td>2.999567</td><td>2.9995660</td><td>8.881557</td><td>8.880761</td></tr><tr><td>2</td><td>2.999562</td><td>2.9995602</td><td>8.877729</td><td>8.875403</td></tr></tbody></table>

For $(r, d, t) = (12323, 71, 134)$, we observe a difference of $5.59 \cdot 10^{-6}$ between multiplicity 0 and 1 in the first column while in the second column, the difference is $6.674 \cdot 10^{-6}$.
For $(r, d, t) = (12323, 71, 180)$, the average number of iterations is increased. We observe a difference of 0.00343 between multiplicity 0 and 1 in the first column and of 0.00478 in the second column.

## 7.4 HQC

We will use the notation of the HQC specification, except for the blocksize which we denote $r$ instead of $n$ in [3]. Let $\mathcal{R} = \mathbb{F}_2[x]/(x^r - 1)$, for any integer $\omega$, we will denote $\mathcal{R}_\omega = \{g \in \mathcal{R} \mid |g| = \omega\}$. HQC parameters are $(r, \omega, \omega_r, \omega_e)$ with $\omega \approx \omega_r \approx \omega_e \approx \sqrt{r}/2$. The scheme features a secret key $(x, y) \in \mathcal{R}_\omega^2$, and for each Encapsulation/Decapsulation instance a triple $(r_1, r_2, e) \in \mathcal{M} = \mathcal{R}_\omega^2 \times \mathcal{R}_{\omega_e}$ is selected uniformly at random. We assume that the adversary can observe the Hamming weight of $e' = r_1x + r_2y + e$ through a side channel and will try to discover the spectrum of $x$.

**Proposition 4.** For all $(x, y) \in \mathcal{R}_\omega^2$ and all $\delta$, $1 \le \delta \le r/2$, we have

$$ \frac{\sum_{(r_1, r_2, e) \in \mathcal{M}} \mu_{r_1}(\delta) |r_1x + r_2y + e|}{\sum_{(r_1, r_2, e) \in \mathcal{M}} \mu_{r_1}(\delta)} = W_{\mu_x(\delta)}^{\text{HQC}}(r, \omega, \omega_r, \omega_e), \quad (12) $$

where for all integer $\nu \ge 0$

$$ W_{\nu}^{\text{HQC}}(r, \omega, \omega_r, \omega_e) = \omega' + (1 - 2\omega'/r) \cdot \omega_1 \quad (13) $$

with

$$ \omega_1 = (r - 2\omega + \nu) \cdot S(r - 2, \omega, \omega_r - 2) + \nu \cdot S(r - 2, \omega, \omega_r - 2) \\ + 2(\omega - \nu) \cdot (1 - S(r - 2, \omega, \omega_r - 2)) \quad (14) $$

and

$$ \omega' = \omega_e + (r - 2\omega_e) \cdot S(r, \omega, \omega_r). \quad (15) $$

The proposition is proven in appendix. We remark that in (13), only $\omega_1$ depends on the multiplicity $\nu$, and this dependency is very similar to what we have for BIKE. Hence, after observation of a sample set $\mathcal{E} \subset \mathcal{M}$ drawn uniformly at random, we get

$$ F_{\delta}(\mathcal{E}, (x, y)) = \frac{\sum_{(r_1, r_2, e) \in \mathcal{E}} \mu_{r_1}(\delta) |r_1x + r_2y + e|}{\sum_{(r_1, r_2, e) \in \mathcal{E}} \mu_{r_1}(\delta)}. $$

As in §6, we gain some accuracy by centering the observation and the model. The average weight of $|r_1x + r_2y + e|$ is equal to $\omega' + (1 - 2\omega'/r) \cdot S(r, \omega, \omega_r)$ where $\omega'$ is defined by (15). The approach used for BIKE in Figure 5 can be applied and provides a soft distance spectrum to be used in Algorithm 3.
**Full spectrum.** Using the model described above, we recover a full spectrum with probability 0.5 using 1.2 million queries and with probability 0.95 using 1.6 million queries which matches our experiments.

**Soft Spectrum.** We can adapt the process in Figure 5 using HQC-1 parameters and model to obtain a soft spectrum. Table 8 shows that the numbers of queries to get a full spectrum are reduced by a factor of about 10, as for BIKE.

<table><caption>**Table 8.** Minimal size of *E* and average running time in seconds to recover the key with Algorithm 3 with probability *p* for HQC-1 parameters.</caption><thead><tr><th></th><th><i>p</i> = 0.5</th><th><i>p</i> = 0.95</th></tr></thead><tbody><tr><td>|<i>E</i>|</td><td>110 000</td><td>190 000</td></tr><tr><td>Avg running time (s)</td><td>239</td><td>61</td></tr></tbody></table>

# 8 Conclusion

In this paper we have fully specified and implemented an algorithm to efficiently recover a sparse polynomial from its distance spectrum using soft information. For BIKE, we have shown that, in an idealized leakage model in which the adversary has access to the syndrome weight, the amount of queries to recover the secret key is significantly reduced, by a factor 10 for BIKE-1. Our framework also applies to HQC if an adversary has access to the error weight, and the soft information approach also reduces the number of queries, by a factor 10 for HQC-1. Finally, we have given evidence that the framework also applies to more realistic leakage models, for instance a noisy observation of the syndrome weight in BIKE, with a significant reduction in the amount of queries when soft information is used.

An important takeaway of this work for BIKE or HQC developers, is to be aware of the need to avoid any leakage of respectively the syndrome weight or the error weight in an implementation of those schemes.
## References

1. Mark Cieliebak, Stephan J. Eidenbenz, and Paolo Penna. Noisy data make the partial digest problem np-hard. In Gary Benson and Roderic D. M. Page, editors, *Algorithms in Bioinformatics, Third International Workshop, WABI 2003, Budapest, Hungary, September 15-20, 2003, Proceedings*, volume 2812 of Lecture Notes in Computer Science, pages 111-123. Springer, 2003.

2. Edward Eaton, Matthieu Lequesne, Alex Parent, and Nicolas Sendrier. QC-MDPC: A timing attack and a CCA2 KEM. In *Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings*, pages 47-76, 2018.

3. Philippe Gaborit, Carlos Aguilar-Melchor, Nicolas Aragon, Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Jean-Christophe Deneuville, Edoardo Persichetti, Gilles Zémor, Jurjen Bos, Arnaud Dion, Jérôme Lacan, Jean-Marc Robert, Pascal Véron, Paulo L. Barreto, Santosh Ghosh, Shay Gueron, Tim Güneysu, Rafael Misoczki, Jan Richter-Brokmann, Nicolas Sendrier, Jean-Pierre Tillich, and Valentin Vasseur. HQC, August 2025.

4. Qian Guo, Thomas Johansson, and Paul Stankovski. A key recovery attack on MDPC with CCA security using decoding errors. In Jung Hee Cheon and Tsuyoshi Takagi, editors, *Advances in Cryptology - ASIACRYPT 2016*, volume 10031 of LNCS, pages 789-815, 2016.

5. Qian Guo, Thomas Johansson, and Paul Stankovski Wagner. A key recovery reaction attack on QC-MDPC. *IEEE Transactions on Information Theory*, 65(3):1845-1861, 2019.

6. Shuai Huang and Ivan Dokmanic. Reconstructing point sets from distance distributions. *IEEE Trans. Signal Process.*, 69:1811-1827, 2021.

7. Motonari Ohtsuka, Takahiro Ishimaru, Rei Iseki, Shingo Kukita, and Kohtaro Watanabe. Key reconstruction for QC-MDPC McEliece from imperfect distance spectrum. Cryptology ePrint Archive, Paper 2025/485, 2025.

8. Motonari Ohtsuka, Takahiro Ishimaru, Yuta Tsukie, Shingo Kukita, and Kohtaro Watanabe. Efficient reconstruction in key recovery attack on the QC-MDPC McEliece cryptosystems. *IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences*, E108.A(3):414-422, 2025.

9. Thales Paiva and Routo Terada. Improving the efficiency of a reaction attack on the QC-MDPC McEliece. *IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences*, E101.A:1676-1686, 10 2018.

10. Steven Skiena, Warren D. Smith, and Paul Lemke. Reconstructing sets from inter-point distances (extended abstract). In Raimund Seidel, editor, *Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, June 6-8, 1990*, pages 332-339. ACM, 1990.

11. Valentin Vasseur. *Post-quantum cryptography: a study of the decoding of QC-MDPC codes*. Thesis, Université de Paris, March 2021.

## A Proof of Proposition 3

We denote $W_{n,t}$ the set of words of weight $t$ in $\mathbb{F}_2^n$. For any given $h \in \mathbb{F}_2^n$, we admit the following result

$$ \mathbb{E} \left[ \langle h, e \rangle = 1 \mid e \stackrel{\$}{\leftarrow} W_{n,t} \right] = S(n, |h|, t) \quad (16) $$
where $\langle h, e \rangle$ denote the scalar product of h and e and for any integers $n, w, t$

$$S(n, w, t) = \sum_{i \text{ odd}} \frac{\binom{w}{i} \binom{n-w}{t-i}}{\binom{n}{t}}.$$

**Lemma 2.** For any matrix $\mathbf{H} = (h_{i,j})_{0 \le i < r, 0 \le j < n} \in \mathbb{F}_2^{r \times n}$ of constant row weight $w$,

$$\mathbb{E} \left[ |e\mathbf{H}^T| \mid e \leftarrow \mathcal{W}_{n,t} \right] = r \cdot S(n, w, t).$$

*Proof.* Let $h_i$, $0 \le i < r$ denote the $i$-th row of $\mathbf{H}$, we easily derives from (16):

$$\begin{aligned}
\mathbb{E} \left[ |e\mathbf{H}^T| \mid e \leftarrow \mathcal{W}_{n,t} \right] &= \frac{1}{\binom{n}{t}} \sum_{|e|=t} |e\mathbf{H}^T| \\
&= \frac{1}{\binom{n}{t}} \sum_{|e|=t} \sum_{0 \le i < r} \langle h_i, e \rangle \\
&= \sum_{0 \le i < r} \frac{1}{\binom{n}{t}} \sum_{|e|=t} \langle h_i, e \rangle \\
&= \sum_{0 \le i < r} S(n, |h_i|, t) = r \cdot S(n, w, t).
\end{aligned}$$

□

Note that the lemma holds for any matrix as long as the row weight condition is verified, in particular, a dependence between rows (e.g. as in block circulant matrices) does not affect the result. Dependence between rows would affect the standard deviation though.

**Lemma 3.** For any matrix $\mathbf{H} = (h_{i,j})_{0 \le i < r, 0 \le j < n} \in \mathbb{F}_2^{r \times n}$ of constant row weight $w$, and for any pair of distinct columns indices $0 \le j, j' < n$, we have

$$\mathbb{E} \left[ |e\mathbf{H}^T| \mid e \leftarrow \mathcal{W}_{n,t}, e_j = e_{j'} = 1 \right] = \nu_0 \cdot S(n-2, w, t-2) \\ + \nu_1 \cdot (1 - S(n-2, w-1, t-2)) + \nu_2 \cdot S(n-2, w-2, t-2), \quad (17)$$

where $\nu_\ell = |\{i, 0 \le i < r \mid |(h_{i,j}, h_{i,j'})| = \ell\}|, 0 \le \ell < 2$.

*Proof.* We reorder the columns of $\mathbf{H}$ so that the $j$-th and $j'$-th columns appear left, and we reorder the rows of $\mathbf{H}$ in increasing order relatively the weight of those two coordinates. We get

$$\mathbf{H}' = \begin{array}{c|c} 2 & n-2 \\ \hline 00 & \mathbf{H}'_0 \in \mathbb{F}_2^{\nu_0 \times (n-2)} \\ 01 & \mathbf{H}'_1 \in \mathbb{F}_2^{\nu_1 \times (n-2)} \\ 10 & \mathbf{H}'_2 \in \mathbb{F}_2^{\nu_2 \times (n-2)} \\ \hline 11 & \mathbf{H}'_3 \in \mathbb{F}_2^{\nu_3 \times (n-2)} \end{array} \begin{array}{c} \nu_0 \\ \nu_1 \\ \nu_2 \end{array}$$
with $\mathbf{H}'_l$, $0 \le l \le 2$, of row weight $w-l$ respectively. For $e \in \mathbb{F}_2^n$, we write $e = (e_0, e_1, e')$ with $e' \in \mathbb{F}_2^{n-2}$. If $e_0 = e_1 = 1$, we have (with 1 the all one vector)

$$ \mathrm{e}\mathbf{H}'^{\mathrm{T}} = (\mathrm{e}'\mathbf{H}'_{0}^{\mathrm{T}}, 1+\mathrm{e}'\mathbf{H}'_{1}^{\mathrm{T}}, \mathrm{e}'\mathbf{H}'_{2}^{\mathrm{T}}) \text{ and } |\mathrm{e}\mathbf{H}'^{\mathrm{T}}| = |\mathrm{e}'\mathbf{H}'_{0}^{\mathrm{T}}| + \nu_1 - |\mathrm{e}'\mathbf{H}'_{1}^{\mathrm{T}}| + |\mathrm{e}'\mathbf{H}'_{2}^{\mathrm{T}}|. \quad (18) $$

From Lemma 2, we get

$$ \mathbb{E} \left[ \left| \mathrm{e}' \mathbf{H}'_l^{\mathrm{T}} \right| \middle| \mathrm{e}' \stackrel{\$}{\leftarrow} \mathcal{W}_{n-2,t-2} \right] = \nu_l \cdot S(n-2, w-l, t-2), \quad 0 \le l \le 2. \quad (19) $$

The following identities

$$ \begin{aligned} \mathbb{E} \left[ \left| (1, 1, e') \mathbf{H}'^{\mathrm{T}} \right| \middle| \mathrm{e}' \stackrel{\$}{\leftarrow} \mathcal{W}_{n-2,t-2} \right] &= \mathbb{E} \left[ \left| \mathrm{e}\mathbf{H}'^{\mathrm{T}} \right| \middle| \mathrm{e} \stackrel{\$}{\leftarrow} \mathcal{W}_{n,t}, e_0 = e_1 = 1 \right] \\ &= \mathbb{E} \left[ \left| \mathrm{e}\mathbf{H}'^{\mathrm{T}} \right| \middle| \mathrm{e} \stackrel{\$}{\leftarrow} \mathcal{W}_{n,t}, e_j = e_{j'} = 1 \right]. \end{aligned} $$

together with (18) and (19) give (17), which completes the proof. $\square$

<figure><img src="image_6.png" /></figure>

**Lemma 4.** Let $r = n/2$, $(h_0, h_1) \in \mathcal{H}_w$, $b \in \{0, 1\}$ and $1 \le \delta \le |r/2|$. For all $i$, $0 \le i < r$, define $\mathcal{E}_t(b, \delta, i) = \{(e_0, e_1) \in \mathcal{E}_t \mid e_{b,i} = e_{b,i+\delta} = 1\}$. We have

$$ (i) \sum_{0 \le i < r} |\mathcal{E}_t(b, \delta, i)| = \sum_{(e_0, e_1) \in \mathcal{E}_t} \mu_{e_b}(\delta), $$

$$ (ii) \sum_{0 \le i < r} \sum_{(e_0, e_1) \in \mathcal{E}_t(b, \delta, i)} |e_0 h_0 + e_1 h_1| = \sum_{(e_0, e_1) \in \mathcal{E}_t} \mu_{e_b}(\delta) |e_0 h_0 + e_1 h_1|, $$

$$ (iii) \quad \begin{aligned} & \sum_{(e_0, e_1) \in \mathcal{E}_t(b, \delta, i)} |e_0 h_0 + e_1 h_1| = |\mathcal{E}_t(b, \delta, i)| \cdot W_\nu(n, w, t), \\ & \text{with} \\ & W_\nu(n, w, t) = (n/2 - w + \nu) \cdot S(n-2, w, t-2) + \nu \cdot S(n-2, w-2, t-2) \\ & \qquad + (w-2\nu) \cdot (1 - S(n-2, w-1, t-2)). \end{aligned} $$

*Proof.* First remark that for any $(b, \delta)$, each $(e_0, e_1) \in \mathcal{E}_t$ will appear in exactly $\mu_{e_b}(\delta)$ of the sets $\mathcal{E}_t(b, \delta, i)$, $0 \le i < r$, hence (i) and (ii) hold.

To $(h_0, h_1) \in \mathcal{H}_w$ we associate the matrix $\mathbf{H}$ consisting of two $r \times r$ circulant blocks, hence $n = 2r$, whose first columns are respectively $h_0$ and $h_1$. To $(e_0, e_1) \in \mathcal{E}_t$ we associate the vector $e \in \mathbb{F}_2^n$ obtained by concatenating $e_0$ and $e_1$. Indeed, we have $e_0 h_0 + e_1 h_1 = \mathrm{e}\mathbf{H}^{\mathrm{T}}$, and

$$ \begin{aligned} \sum_{(e_0, e_1) \in \mathcal{E}_t(b, \delta, i)} |e_0 h_0 + e_1 h_1| &= |\mathcal{E}_t(b, \delta, i)| \cdot \mathbb{E} \left[ |e_0 h_0 + e_1 h_1| \mid (e_0, e_1) \stackrel{\$}{\leftarrow} \mathcal{E}_t(b, \delta, i) \right] \\ &= |\mathcal{E}_t(b, \delta, i)| \cdot \mathbb{E} \left[ |\mathrm{e}\mathbf{H}^{\mathrm{T}}| \mid \mathrm{e} \stackrel{\$}{\leftarrow} \mathcal{W}_{n,t}, e_j = e_{j'} = 1 \right], \end{aligned} $$

with $j = br + i$ and $j' = br + (i + \delta \mod r)$. For given $(b, \delta)$, we apply formula (17) of Lemma 3 to the matrix $\mathbf{H}$ and to the indices $(j, j')$. This formula makes use of the following coefficients

$$ \nu_l = |\{i, 0 \le i < r \mid |(h_{b,i}, h_{b,i+\delta})| = \ell\}|, \quad 0 \le \ell < 2. $$
By definition of the spectrum multiplicity, we have $\nu_2 = \nu = \mu_{h_0}(\delta)$. We must have $\nu_1 = w - 2\nu$ (the total weight of two columns is $2d = w$) and thus $\nu_0 = r - \nu_1 - \nu_2 = n/2 - w + \nu$. Finally, this yields

$$ \sum_{(e_0, e_1) \in \mathcal{E}_t(b, \delta, i)} |e_0 h_0 + e_1 h_1| = |\mathcal{E}_t(b, \delta, i)| \cdot W_\nu(n, w, t). $$

□

We recall the proposition.

**Proposition 3.** For all $(h_0, h_1) \in \mathcal{H}_w$ and all $\delta$, $1 \le \delta \le r/2$, we have

$$ \frac{\sum_{(e_0, e_1) \in \mathcal{E}_t} \mu_{e_0}(\delta) |e_0 h_0 + e_1 h_1|}{\sum_{(e_0, e_1) \in \mathcal{E}_t} \mu_{e_0}(\delta)} = W_{\mu_{h_0}(\delta)}(n, w, t), \quad (6) $$

where for all integer $\nu \ge 0$

$$ W_{\nu}(n, w, t) = (n/2 - w + \nu) \cdot S(n-2, w, t-2) + \nu \cdot S(n-2, w-2, t-2) \\ + (w-2\nu) \cdot (1 - S(n-2, w-1, t-2)), \quad (7) $$

with

$$ S(n, w, t) = \sum_{i \text{ odd}} \frac{\binom{w}{i} \binom{n-w}{t-i}}{\binom{n}{t}}. $$

*Proof (of Proposition 3).* We apply Lemma 4. First adding (iii) for all $r$, then use (i) and (ii) to get the identity (6) of Proposition 3.

## B Proof of Proposition 4

The sum of two words of weight $w$ and $w'$ has a weight $w + w' - 2ww'/r$ when everything is uniformly distributed. The following Lemmas, which we admit, generalizes this for any distributions assuming some uniformity properties.

**Lemma 5.** Let $\mathcal{D}$ denote a distribution over $\mathbb{F}_2^r$ such that the probability of $h \in \mathbb{F}_2^r$ only depends of its Hamming weight. For all $g \in \mathcal{R}$

$$ \mathbb{E} \left[ |g + h| \mid h \stackrel{\mathcal{D}}{\leftarrow} \mathbb{F}_2^r \right] = \omega + (1 - 2\omega/r) \cdot |g| $$

$$ \text{where } \omega = \mathbb{E} \left[ |h| \mid h \stackrel{\mathcal{D}}{\leftarrow} \mathbb{F}_2^r \right]. $$

**Lemma 6.** Let $\mathcal{D}_1$ and $\mathcal{D}_2$ denote distributions over $\mathbb{F}_2^r$ such that the probability of $h \in \mathbb{F}_2^r$ only depends of its Hamming weight. If $h_1$ and $h_2$ are drawn according
to $D_1$ and $D_2$, the probability of $h_1 + h_2$ only depends of its Hamming weight.
Moreover we have

$$ \mathbb{E} \left[ |h_1 + h_2| \mid h_1 \underset{D_1}{\leftarrow} \mathbb{F}_2^r, h_2 \underset{D_2}{\leftarrow} \mathbb{F}_2^r \right] = \omega_1 + (1 - 2\omega_1/r) \cdot \omega_2 $$

$$ \text{where } \omega_b = \mathbb{E} \left[ |h| \mid h \underset{D_b}{\leftarrow} \mathbb{F}_2^r \right], b \in \{1, 2\}. $$

We recall the proposition.

**Proposition 4.** For all $(x, y) \in \mathcal{R}_{\omega}^2$ and all $\delta$, $1 \le \delta \le r/2$, we have

$$ \frac{\sum_{(r_1, r_2, e) \in \mathcal{M}} \mu_{r_1}(\delta) |r_1 x + r_2 y + e|}{\sum_{(r_1, r_2, e) \in \mathcal{M}} \mu_{r_1}(\delta)} = W_{\mu_x(\delta)}^{\text{HQC}}(r, \omega, \omega_r, \omega_e), \quad (12) $$

where for all integer $\nu \ge 0$

$$ W_{\nu}^{\text{HQC}}(r, \omega, \omega_r, \omega_e) = \omega' + (1 - 2\omega'/r) \cdot \omega_1 \quad (13) $$

with

$$ \omega_1 = (r - 2\omega + \nu) \cdot S(r - 2, \omega, \omega_r - 2) + \nu \cdot S(r - 2, \omega, \omega_r - 2) \\ + 2(\omega - \nu) \cdot (1 - S(r - 2, \omega, \omega_r - 2)) \quad (14) $$

and

$$ \omega' = \omega_e + (r - 2\omega_e) \cdot S(r, \omega, \omega_r). \quad (15) $$

*Proof (of Proposition 4).* Let $(x, y) \in \mathcal{R}_{\omega}^2$ and $(r_1, r_2, e) \in \mathcal{R}_{\omega_r}^2 \times \mathcal{R}_{\omega_e}$. We define $e' = r_1x + r_2y + e$. If $r_2$ is uniformly distributed, the distribution of $r_2y$ verifies the uniformity condition of Lemma 6 and has an average weight $r \cdot S(r, \omega, \omega_r)$. From Lemma 6, the distribution of $r_2y + e$ only depends of its Hamming weight and has an average weight $\omega' = \omega_e + (r - 2\omega_e) \cdot S(r, \omega, \omega_r)$.

Applying Lemma 5 with $r_2y + e$ and a fixed value of $r_1x$, we get

$$ \mathbb{E} \left[ |r_1x + r_2y + e| \mid r_2 \stackrel{\mathcal{S}}{\leftarrow} \mathcal{R}_{\omega_r}, e \stackrel{\mathcal{S}}{\leftarrow} \mathcal{R}_{\omega_e} \right] = \omega' + (1 - 2\omega'/r) \cdot |xr_1|. \quad (20) $$

Finally, a reasoning similar to the proof of Lemma 4 shows that for all $\delta$

$$ \frac{\sum_{r_1 \in \mathcal{R}_{\omega_r}} \mu_{r_1}(\delta) |r_1 x|}{\sum_{r_1 \in \mathcal{R}_{\omega_r}} \mu_{r_1}(\delta)} = \omega_1, \quad (21) $$

$$ \omega_1 = (r - 2\omega + \nu) \cdot S(r - 2, \omega, \omega_r - 2) + \nu \cdot S(r - 2, \omega, \omega_r - 2) \\ + 2(\omega - \nu) \cdot (1 - S(r - 2, \omega, \omega_r - 2)). $$
From (20) and (21), we easily derive

$$ \frac{\sum_{(r_1,r_2,e) \in \mathcal{M}} \mu_{r_1}(\delta) |r_1 x + r_2 y + e|}{\sum_{(r_1,r_2,e) \in \mathcal{M}} \mu_{r_1}(\delta)} = \omega' + (1 - 2\omega'/r) \cdot \omega_1. $$

□