# On the Independence Assumption in Quasi-Cyclic Code-Based Cryptography

Maxime Bombar, Nicolas Resch, Emiel Wiedijk

► To cite this version:

Maxime Bombar, Nicolas Resch, Emiel Wiedijk. On the Independence Assumption in Quasi-Cyclic Code-Based Cryptography. ISIT 2025 - IEEE International Symposium on Information Theory, Jun 2025, Ann Arbor, United States. pp.1-6, 10.1109/ISIT63088.2025.11195347. hal-05466410

HAL Id: hal-05466410

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

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
# On the Independence Assumption in Quasi-Cyclic Code-Based Cryptography

Maxime Bombar

Insitut de Mathématiques de Bordeaux,
France

Email: maxime.bombar@math.u-bordeaux.fr

Nicolas Resch and Emiel Wiedijk

University of Amsterdam
The Netherlands

Email: {n.a.resch,e.wiedijk}@uva.nl

**Abstract**—This work investigates the security of code-based cryptosystems such as BIKE and HQC, which are among the most promising candidates for post-quantum cryptography and rely on the hardness of decoding quasi-cyclic codes. A critical aspect of their security analysis involves understanding the distribution of elements formed by combining sparse polynomials (say with coordinates modeled as i.i.d. Bernoulli) and fixed circulant blocks. In particular, the HQC documentation models this distribution as a vector with independent coordinates and correct marginal distributions. However, we identify cases where this modeling fails, revealing that the behavior of the resulting noise is more complex than previously anticipated. While this does not invalidate the conclusion of HQC regarding the (empirically verified) Hamming weight of such elements, it does suggest that the behavior of the noise is more subtle than previously predicted. Lastly, we discuss implications of our result for potential worst-case to average-case reductions for quasi-cyclic codes.

## I. INTRODUCTION

In light of recent calls for post-quantum cryptography – which are designed to remain secure in a world with quantum computers – code-based cryptography has emerged as a leading candidate. Notably, all three remaining finalists in the 4th round of the NIST competition [1]–[3] are code-based. These systems rely on the hardness of decoding linear codes under the Hamming metric, which is widely conjectured to be resistant to quantum attacks.

From a more foundational perspective, the decoding problem is closely related to the Learning Parity with Noise (LPN). In its search variant, LPN asks one to recover a secret $s$ from an input pair $(\mathbf{A}, s\mathbf{A} + \mathbf{e})$, where $\mathbf{A} \leftarrow \mathbb{F}_2^{k \times n}$ and $s \leftarrow \mathbb{F}_2^k$ are uniformly distributed, and $\mathbf{e} \in \mathbb{F}_2^n$ is a noise vector with independently Bernoulli-distributed entries. This search variant is also often called the Decoding Problem. For cryptographic purposes, a decision variant is often required, which asks to distinguish a pair $(\mathbf{A}, s\mathbf{A} + \mathbf{e})$ from a uniform $(\mathbf{A}, \mathbf{b})$. However, the search and decision variant are known to be polynomially equivalent [4]. LPN inspired the related Learning With Errors (LWE) problem [5], which is at the core of lattice-based cryptography.

A significant challenge in constructing efficient public-key cryptography based on LWE or LPN lies in the size of the public key, of which the matrix $\mathbf{A}$ is a part. Thus, one is required to publish $n \cdot k$ fields elements, which renders these schemes uncompetitive. To remedy this situation, some cryptosystems (including NIST submissions [1], [2] which are based on quasi-cyclic codes) use structured matrices $\mathbf{A}$ for which the problem is still widely believed to be hard (even quantumly), but which admit short representations.

a) **Quasi-Cyclic Codes:** A quasi-cyclic (QC) code is a code that can be generated by a matrix composed of multiple blocks of circulant submatrices, i.e., where each row is a cyclic shift

of the first. These matrices naturally correspond to polynomial multiplication over the ring $\mathcal{R}_n \stackrel{\text{def}}{=} \mathbb{F}_2[X]/(X^n - 1)$. For example, a circulant matrix $M_a$ corresponds to the endomorphism $P(X) \mapsto a(X)P(X)$, where $a(X)$ represents the first row of the matrix. Consequently, an instance $(\mathbf{A}, s\mathbf{A} + \mathbf{e})$ of the Quasi-Cyclic Decoding Problem can be represented by a collection of polynomial samples of the form $(\mathbf{a}, \mathbf{a} \cdot s + \mathbf{e})$ in the ring $\mathcal{R}_n$.

b) **Analysis of the Noise:** In the security analysis of quasi-cyclic code-based cryptographic schemes such as HQC, one requires an understanding of the product of polynomials $t(X)R(X)$ where $t \in \mathcal{R}_n$ is a fixed polynomial and the coefficients of $R \in \mathcal{R}_n$ are independently Bernoulli distributed. In fact, one needs to analyze the distribution of sums of such products, such as $e(X) \stackrel{\text{def}}{=} t_1(X)R_1(X) + t_2(X)R_2(X)$. To make the analysis tractable, the authors make the simplifying assumption that the coefficients of $e$ are independent [2, Section 2.4]. Even though their analysis was backed by experimental results (at least, the claimed concentration of the Hamming weight of $e$ is supported empirically, which is the fact their analysis requires), this independence assumption was already challenged in later works aiming at deriving theoretical search-to-decision reductions in the case of structured codes [6, Section 5]. However, a lack of understanding of such distributions made such reductions impossible to prove.

c) **Our Work:** Let $\text{Ber}(\omega)$ denote the $\mathbb{F}_2$-valued distribution which outputs 1 with probability $\frac{1-2^{-\omega}}{2}$. We assume $\omega = O(\log n)$, as if it is $\omega(\log n)$ then the noise has negligible bias, so any relevant decoding task becomes inherently intractable.<fnref n="1" /> Note that with this notation, the sum of two independent Bernoulli random variables of respective parameters $\omega$ and $\omega'$ is now distributed as $\text{Ber}(\omega + \omega')$ (this fact is sometimes known as the *Piling-Up Lemma*). In particular, when $t \in \mathcal{R}_n$ has $\tau$ nonzero coefficients, and if the coefficients of $R \in \mathcal{R}_n$ are independently distributed as $\text{Ber}(\omega)$, then the marginals of $t \cdot R$ are distributed as $\text{Ber}(\tau\omega)$. In this work, we revisit the aforementioned independence assumption and prove that the statistical distance between the distribution of $t(X)R(X)$ and that of an idealized independent model with same marginals is $\Omega(\sqrt{n}2^{-2\omega})$ (Theorem 5). Note that in our case with $\omega = O(\log n)$ it follows that the statistical distance is $1/n^{\Omega(1)}$, i.e., non-negligible.

In Section IV we analyze the more general case of sums of such polynomials, i.e., $\sum_{i=1}^s t_i R_i$ where each $t_i$ is fixed and each $R_i$ is independently Bernoulli-distributed. In this case we

<footnote n="1">¹For example, in the case of standard LPN in the distinguishing variant, if $\omega$ is super-logarithmic then $\mathbf{e}$ is computationally indistinguishable from uniform, so distinguishing $(\mathbf{A}, s\mathbf{A} + \mathbf{e})$ from uniform $(\mathbf{A}, \mathbf{b})$ is trivially impossible for poly(n)-time algorithms.</footnote>
identify certain classes of structured $t_i$'s where there is still a non-negligible lower bound on the statistical distance between the idealized distribution. We conclude in Section V with a discussion of connections between our work and worst-case to average-case reductions for quasi-cyclic codes.

## II. GENERAL NOTATIONS

We let $\mathcal{R}_n$ denote the ring $\mathbb{F}_2[X]/(X^n - 1)$. Unless stated otherwise, we will assume that $n$ is an odd prime such that 2 is primitive modulo $n$, meaning that $\mathcal{R}_n$ is isomorphic to the product $\mathbb{F}_2 \times \mathbb{F}_{2^{n-1}}$. Another consequence is that the invertible elements of $\mathcal{R}_n$ are easily characterized as the polynomials of odd Hamming weight, which is a well-known fact in quasi-cyclic code-based cryptography.

For $\omega \in [0, +\infty]$, we denote by $\text{Ber}(\omega)$ the $\mathbb{F}_2$-valued distribution which outputs 1 with probability $\frac{1-2^{-\omega}}{2}$. For a probability distribution $P$ we denote sampling from this distribution via $X \leftarrow P$, and for a positive integer $n$, we let $P^{\otimes n}$ to denote the probability distribution of the random vector $(X_1, \dots, X_n)$ where each $X_i$ is independently distributed according to $P$. We sometimes abuse notation and write $R(X) \leftarrow \text{Ber}(\omega)^{\otimes n}$ to mean that $R(X) = \sum_{i=0}^{n-1} R_i X^i \in \mathcal{R}_n$ and $(R_1, \dots, R_n) \leftarrow \text{Ber}(\omega)^{\otimes n}$.

For distributions $P$ and $Q$, we use the following notation for information-theoretic quantities:

$$H(P) \stackrel{\text{def}}{=} \sum_x P(x) \log(1/P(x)) \quad (\text{entropy})$$

$$D(P \| Q) \stackrel{\text{def}}{=} \sum_x P(x) \log(P(x)/Q(x)) \quad (\text{KL divergence})$$

$$\Delta_{\text{tv}}(P, Q) \stackrel{\text{def}}{=} \frac{1}{2} \sum_x |P(x) - Q(x)| \quad (\text{statistical distance})$$

For convenience, we abuse notation by writing random variables instead of the distribution of these random variables. For example, when $X \leftarrow P$, we write $H(X)$ instead of $H(P)$.

We write $h(x) \stackrel{\text{def}}{=} -x \log(x) - (1-x) \log(1-x)$ for the binary entropy. We additionally write $\tilde{h}(\omega)$ for the entropy of a $\text{Ber}(\omega)$ random variable, so $\tilde{h}(\omega) \stackrel{\text{def}}{=} h(\frac{1-2^{-\omega}}{2})$.

## III. ANALYSIS

The general goal of this article is to analyze the distribution of $t(X)R(X)$ where $t(X) \in \mathcal{R}_n \stackrel{\text{def}}{=} \mathbb{F}_2[X]/(X^n - 1)$ is a fixed polynomial, and $R(X) \leftarrow \text{Ber}(\omega)^{\otimes n}$. First, denoting by $(tR)_k$ the coefficient of $X^k$ in $tR \in \mathcal{R}_n$, a simple computation shows that $(tR)_k = \sum_{0 \le j \le n-1 \atop t_{k-j}=1} R_j$. As a consequence, we can easily derive

the marginal distributions of $tR$.

**Lemma 1.** Let $t \in \mathcal{R}_n$ be fixed and let $R \leftarrow \text{Ber}(\omega)^{\otimes n}$. Denote by $\|t\|$ the Hamming weight of $t$. Then,

$$(tR)_k \leftarrow \text{Ber}(\|t\|\omega).$$

While Lemma 1 characterizes the marginal distributions of $tR$, it does not establish independence among coefficients. In particular, $tR$ is not distributed as $\text{Ber}(\|t\|\omega)^{\otimes n}$ since coefficients $(tR)_k$

and $(tR)_{k'}$ will depend on the same coefficients in $R$ when the intersection

$$\{j \in \{0, \dots, n-1\} \mid t_{k-j} = 1\} \cap \{j \in \{0, \dots, n-1\} \mid t_{k'-j} = 1\}$$

is not empty. In particular, many conventional methods to analyze the weight $\|tR\|$ are not directly applicable. Nonetheless, previous analyses (e.g., [7]) demonstrate that it is indeed somewhat concentrated around its mean $\mathbb{E}[\|tR\|] = n \cdot \frac{1-2^{-\|t\|\omega}}{2}$, as previously experimentally conjectured in [2].

However, this dependence between the coefficients $(tR)_i$ turns out to be significant in general. It is crucial to better understand the statistical distance between $tR$ and $I \leftarrow \text{Ber}(\|t\|\omega)^{\otimes n}$ with independent coefficients both for practical reasons (preventing unexpected decryption failures in quasi-cyclic code-based cryptosystems) and for providing theoretical security reductions [6]. First, let us remark that a Bernoulli distribution reaches every polynomial with non-zero probability. In particular, for this statistical distance to be small, we must have $\text{Pr}[t(X)R(X) = 1] > 0$, which in turns implies that $t$ must be invertible. In this situation, if $R(X)$ is uniform $(\omega = +\infty)$, then $t(X)R(X)$ is also uniform and this distance is indeed zero. Our main goal will therefore be to determine how low the bias of $R(X)$ can be for $t(X)R(X)$ to look like a Bernoulli, outside of this extreme case.

In order to analyze the statistical distance between $t(X)R(X)$ and an independent Bernoulli distribution, we first give an exact analysis of their KL-divergence, which the following lemma states has a relatively simple form. This result is quite likely folklore, but for lack of a good reference, we provide a proof in the long version [8].

**Lemma 2.** Let $P: \mathcal{X} \to [0, 1]$ be a discrete distribution over $\mathcal{X} = \mathcal{X}_1 \times \dots \times \mathcal{X}_n$, with $P_1, \dots, P_n$ the marginal distributions. Define

$$Q \stackrel{\text{def}}{=} P_1 \otimes \dots \otimes P_n$$

the distribution, such that the marginal distributions of $Q$ and $P$ agree (so $Q_i = P_i$), and the marginal distributions of $Q$ are independent. Then

$$D(P \| Q) = H(Q) - H(P).$$

Our KL-divergence now follows from the above lemma since the entropy $H(\text{Ber}(\omega)) = \tilde{h}(\omega)$. See the full version [8] for more details.

**Theorem 1 (Dependence of $tR$).** Fix an invertible polynomial $t \in \mathcal{R}_n$ and let $R \leftarrow \text{Ber}(\omega)^{\otimes n}$. Let $I \leftarrow \text{Ber}(\|t\|\omega)^{\otimes n}$. Then

$$D(tR \| I) = n \left( \tilde{h}(\|t\|\omega) - \tilde{h}(\omega) \right).$$

### A. Approximation for divergence of one product

To give a stricter bound on when the divergence $D(tR \| I)$ is small we need a lemma to approximate $\tilde{h}(\omega)$. This approximation follows from a standard use of Taylor's expansion. See the full version [8] for the computation.

**Lemma 3 (Approximation of $\tilde{h}(\omega)$).** Let $\omega > 0$ we have that

$$\tilde{h}(\omega) = 1 - \frac{2^{-2\omega}}{\ln(2)} + \mathcal{O}(2^{-4\omega}).$$
Filling in the approximation in Theorem 1 we can deduce the following corollary.

**Corollary 1.** Fix an invertible polynomial $t \in \mathbb{R}_n$ and let $R \leftarrow \text{Ber}(\omega)^{\otimes n}$. Let $I \leftarrow \text{Ber}(\|t\|\omega)^{\otimes n}$. Then

$$D(tR\|I) = n\Theta(2^{-2\omega}).$$

When $\omega$ is small, Corollary 1 does not tell us much about the quantity. However, even assuming that $\tilde{h}(\|t\|\omega) - \tilde{h}(\omega)$ remains constant, $D(tR\|I) \to \infty$ when $n \to \infty$. Notably, if we want $D(tR\|I) \to 0$, then we need $\omega \to \infty$. In particular, in the standard setting $\omega = C \log n$, the bound is non-negligible $1/n^{\Theta(1)}$.

## B. Statistical distance

To get an upper bound on the statistical distance, we can use Pinsker's inequality.

**Theorem 2 (Pinsker's inequality [9, Sec. 6]).** For $P$ and $Q$ distributions

$$\Delta_{\text{tv}}(P, Q) \le \sqrt{\frac{1}{2} D(P\|Q)}.$$

Pinsker's inequality immediately tells us that

$$\Delta_{\text{tv}}(tR, I) \le \sqrt{\frac{1}{2} D(tR\|I)} = \sqrt{\frac{n}{2}} \cdot (\tilde{h}(\|t\|\omega) - \tilde{h}(\omega)),$$

and alternatively

$$\Delta_{\text{tv}}(tR, I) \le \sqrt{n} \cdot \mathcal{O}(2^{-\omega}).$$

Still we would also like to get a lower bound on the statistical distance. This other direction is harder, because given a certain statistical distance $\delta = \Delta_{\text{tv}}(P, Q)$ the Kullback-Leibler divergence $D(P\|Q)$ can be infinitely large, specifically when there is an $x$ such that $P(x) > 0$ and $Q(x) = 0$. As $P(x)$ can be arbitrarily small, a lower bound on the statistical distance based on the Kullback-Leibler divergence is not possible in general.

In our case, we are working with Bernoulli variables that span the entire outcome space $\mathbb{F}_2[X]/(X^n - 1)$. In particular, this extreme case cannot occur, and we can use a so-called reversed Pinsker's inequality.

**Theorem 3 (Reverse Pinsker Inequality [10].)** Let $P, Q: \mathcal{X} \to [0, 1]$ be distinct discrete probability distributions over $\mathcal{X}$. Let

$$m = \min_{x \in \mathcal{X}} \frac{P(x)}{Q(x)}, \quad M = \max_{x \in \mathcal{X}} \frac{P(x)}{Q(x)}.$$

Then

$$D(P\|Q) \le \Delta_{\text{tv}}(P, Q) \frac{m \log(m)}{1-m} + \frac{M \log(M)}{M-1}.$$

From that, we can now deduce the following lower bound.

**Theorem 4.** For $n \ge 3$ and $\omega \ge \log(n)$,

$$\Delta_{\text{tv}}(tR\|I) \ge 1/3 \cdot D(tR\|I).$$

Theorem 4 is a special case of Theorem 6 where $s = 1$. We defer the proof to the generic theorem. However, we can immediately deduce bounds on the statistical distance.

**Theorem 5.** Assuming $\omega \ge \log(n)$ the statistical distance $\Delta_{\text{tv}}(tR, I)$ can be bounded to the range

$$\Delta_{\text{tv}}(tR, I) \in [n \cdot \Theta(2^{-2\omega}), \sqrt{n} \cdot \Theta(2^{-\omega})].$$

## IV. GENERALIZATION: SUM OF PRODUCTS

In practice, the relevant distribution involves more polynomials: it is of the form $\pi_s \stackrel{\text{def}}{=} t_1 R_1 + \dots + t_s R_s$ for $s \ge 2$. Denote by $\tau \stackrel{\text{def}}{=} \|t_1\| + \dots \|t_s\|$. From the previous section, it is clear that the marginals of this distribution follow $\text{Ber}(\tau\omega)$. However, note that $\pi_s$ is constrained in the ideal $\langle t_1, \dots, t_s \rangle$. In particular, for $\pi_s$ to be close to having independent coefficients, it is necessary that this ideal be equal to the full ring $\mathbb{R}_n$. This is the generalization of asking $t$ to be invertible in the case $s = 1$.

**Theorem 6.** Let $t_1, \dots, t_s \in \mathbb{R}_n$ be fixed and such that $\langle t_1, \dots, t_s \rangle = \mathbb{R}_n$. Let $R_1, \dots, R_s \leftarrow \text{Ber}(\omega)^{\otimes n}$ i.i.d. Furthermore, let $I \leftarrow \text{Ber}(\tau\omega)^{\otimes n}$. For $n \ge 3$ and $\omega \ge \log(n)$, the statistical distance has a lower bound

$$\Delta_{\text{tv}}(t_1 R_1 + \dots + t_s R_s, I) \ge 1/(3s) \cdot D(t_1 R_1 + \dots + t_s R_s \|I).$$

*Proof.* The idea is to bound $\text{Pr}[t_1 R_1 + \dots + t_s R_s = x]/\text{Pr}[I = x]$ from above and below, and then apply Theorem 3. First, remark that for any $x \in \mathbb{R}_n$, there are at exactly $2^{(s-1)n}$ tuples $(r_1, \dots, r_s)$ such that $t_1 r_1 + \dots + t_s r_s = x$. For each of them we have

$$\left(\frac{1 - 2^{-\omega}}{2}\right)^{sn} \le \text{Pr}[(R_1, \dots, R_s) = (r_1, \dots, r_s)] \le \left(\frac{1 + 2^{-\omega}}{2}\right)^{sn}.$$

Therefore,

$$\frac{\text{Pr}[t_1 R_1 + \dots + t_s R_s = x]}{\text{Pr}[I = x]} \le \frac{\max_{x \in \mathbb{R}_n} \text{Pr}[t_1 R_1 + \dots + t_s R_s = x]}{\min_{x \in \mathbb{R}_n} \text{Pr}[I = x]} \\ \le \frac{2^{(s-1)n} ((1 + 2^{-\omega})/2)^{sn}}{((1 - 2^{-\|t\|\omega})/2)^n} \\ \le \frac{(1 + 2^{-\omega})^{sn}}{(1 - 2^{-\omega})^{sn}} \\ \le \left(\frac{1 + 1/n}{1 - 1/n}\right)^{ns} \quad (\text{using } \omega \ge \log(n)).$$

Define $u_n \stackrel{\text{def}}{=} (\frac{1+1/n}{1-1/n})^n$. It is readily seen that $(u_n)$ is decreasing, and that $u_3 \le 8$, which leads an upper bound of $8^s$, independent of $n$.

For a lower bound on the probability ratio we can apply a similar approach to prove that

$$\frac{\text{Pr}[t_1 R_1 + \dots + t_s R_s = x]}{\text{Pr}[I = x]} \ge (1/u_n)^s \ge (1/8)^s.$$

We are now ready to apply reverse Pinsker's inequality. Note that $x \mapsto x \log(x)/(1-x)$ is monotonically decreasing. Therefore, with the notations of Theorem 3, we have

$$\frac{m \log(m)}{1-m} + \frac{M \log(M)}{M-1} \le \frac{(1/8^s) \cdot \log(1/8^s)}{1 - (1/8^s)} + \frac{8^s \log(8^s)}{8^s - 1} \\ = 3s \left( \frac{8^s}{8^s - 1} - \frac{8^{-s}}{1 - 8^{-s}} \right) \\ = 3s.$$

which implies

$$\Delta_{\text{tv}}(t_1 R_1 + \dots + t_s R_s, I) \ge 1/(3s) \cdot D(t_1 R_1 + \dots + t_s R_s \|I), \\ \text{concluding the proof.} \quad \square$$

A natural approach to get a meaningful lower bound would be to compute the entropy $H(t_1 R_1 + \dots + t_s R_s)$ and apply Lemma 2.
In the extreme case when $t_1 = \cdots = t_s \stackrel{\text{def}}{=} t$ are all equal to an invertible $t$, then $t_1 R_1 + \cdots + t_s R_s = t(R_1 + \cdots + R_s)$ and we return to the special of a product $tR$ where $R \leftarrow \text{Ber}(s\omega)^{\otimes n}$ which we analyzed in Section III. In particular,

$$D(t(R_1 + \dots + R_s)\|I_s) = n(\tilde{h}(\|t\|s\omega) - \tilde{h}(s\omega)).$$

Unfortunately, the entropy of the general case seems very hard to compute in general. The interested reader may refer to [11], [12] for related works on the entropy of sums.

Instead, we choose to analyze the entropy based on the distribution of the coefficients. Write $t_1 R_1 + \cdots + t_s R_s$ as a polynomial $C_0 + C_1 X + \cdots + C_{n-1} X^{n-1}$ where each $C_i$ is distributed as $\text{Ber}(\tau\omega)$ where $\tau = \|t_1\| + \cdots + \|t_s\|$. In other words, $H(t_1 R_1 + \cdots + t_s R_s) = H(C_0, C_1, \ldots, C_{n-1})$. Then, since $n$ is supposed to be an odd prime, we have

$$H(C_0, \dots, C_{n-1}) \le H(C_0, C_1) + H(C_2, C_3) + \dots + H(C_{n-3}, C_{n-2}) + H(C_{n-1}).$$

It turns out that for each $1 \le i < j \le n-2$, we can compute explicitly the distribution $(C_i, C_j)$ following [13]. Write $T_i \in \mathbb{F}_2^{n \times n}$ for the cyclic matrix that represents the multiplication by $t_i(X)$. Then define

$$T \stackrel{\text{def}}{=} \left( \begin{array}{c|c|c} T_1 & \dots & T_s \end{array} \right)$$

which one can view as a parity-check matrix of some quasi-cyclic code. Furthermore, let $R \stackrel{\text{def}}{=} (R_1 | \dots | R_s)$ be the concatenation of the $R_i$'s. Then, $(C_0, \dots, C_{n-1})$ is nothing but the syndrome $TR^\top$.

In the sequel, it will be important to view elements of $\mathbb{F}_2^n$ (or, more generally, $\mathbb{R}_n$) as elements of $\mathbb{R}^n$ where we naturally map $0 \in \mathbb{F}_2$ to $0 \in \mathbb{R}$ and $1 \in \mathbb{F}_2$ to $1 \in \mathbb{R}$. For clarity, a real value corresponding to a boolean object $A$ (e.g., vector, matrix or polynomial) will be denoted by $\hat{A}$.

The distribution of $(C_i, C_j)$ depends on the symmetric matrix $\Lambda \stackrel{\text{def}}{=} \hat{T}^\top \hat{T} \in \mathbb{R}^{n \times n}$. Let $\lambda_{i,j}$ denote the coefficients of $\Lambda$. By definition,

$$\lambda_{ij} = \langle \widehat{X^i \cdot t_1}, \widehat{X^j \cdot t_1} \rangle_{\mathbb{R}} + \dots + \langle \widehat{X^i \cdot t_s}, \widehat{X^j \cdot t_s} \rangle_{\mathbb{R}},$$

where $\langle \cdot, \cdot \rangle_{\mathbb{R}}$. As the multiplication by $X^i$ is just a shift of the vector by $i$ positions, we can replace two shifts by just one shift, so

$$\lambda_{ij} = \langle \hat{t}_1, X^{\widehat{i-j} \cdot t_1} \rangle_{\mathbb{R}} + \dots + \langle \hat{t}_s, X^{\widehat{i-j} \cdot t_s} \rangle_{\mathbb{R}}. \quad (1)$$

Notably, the value of $\lambda_{ij}$ only depends on the difference between the coefficients $i-j$. Alternatively, one can note that for each $\ell \in [s]$,

$$\langle \hat{t}_\ell, X^{\widehat{i-j} \cdot t_\ell} \rangle_{\mathbb{R}} = |\text{supp}(t_\ell) \cap \text{supp}(X^{i-j} t_\ell)|,$$

where for a polynomial $P \in \mathbb{R}_n$, its support $\text{supp}(P)$ is the set of nonzero coefficients. Write $p(\omega) \stackrel{\text{def}}{=} (1 - 2^{-\omega})/2$ for the success probability of $\text{Ber}(\omega)$. Following [13, Eq. (14)], we can obtain, for each pair $(C_i, C_j)$, the joint distribution represented in the table below.

<table><caption>TABLE I</caption><thead><tr><th>C<sub>i</sub> \ C<sub>j</sub></th><th>0</th><th>1</th></tr></thead><tbody><tr><th>0</th><td>1 - p(τω) - <sup>1</sup>&frasl;<sub>2</sub>p(2(τ - λ<sub>ij</sub>)ω)</td><td><sup>1</sup>&frasl;<sub>2</sub>p(2(τ - λ<sub>ij</sub>)ω)</td></tr><tr><th>1</th><td><sup>1</sup>&frasl;<sub>2</sub>p(2(τ - λ<sub>ij</sub>)ω)</td><td>p(τω) - <sup>1</sup>&frasl;<sub>2</sub>p(2(τ - λ<sub>ij</sub>)ω)</td></tr></tbody></table>

We give the computation of one of these quantities (the others are similar). As the coefficients of $t_1 R_1 + \cdots + t_s R_s$, each $C_k$ is of the form $\sum_{(u,v) \in S_k} R_{u,v} \in \mathbb{F}_2$, where $R_{u,v}$ are independently distributed as $\text{Ber}(\omega)$ and $u \in \{1, \dots, n\}$ and $v \in \{1, \dots, s\}$. Furthermore, each $S_k$ has the same size $|S_k| = \tau$ and for each pair $(i, j)$, the intersection $S_{ij} \stackrel{\text{def}}{=} S_i \cap S_j$ has cardinality $|S_{ij}| = \lambda_{ij}$. Let $E_{ij} \stackrel{\text{def}}{=} \sum_{(u,v) \in S_{ij}} R_{u,v}$. Then, conditioned on $(E_{ij} = 0)$, we have that $C_i = 0$ iff $\sum_{(u,v) \in S_i \setminus S_j} R_{u,v} = 0$. We can write a similar sum for the case $C_j = 1$, conditioned on $E_{ij} = 1$. Therefore,

$$\begin{aligned} \text{Pr}[C_i = 0, C_j = 1] &= \text{Pr}[C_i = 0, C_j = 1 | E_{ij} = 0] \text{Pr}[E_{ij} = 0] \\ &\quad + \text{Pr}[C_i = 0, C_j = 1 | E_{ij} = 1] \text{Pr}[E_{ij} = 1] \\ &= (1 - p(\omega(\tau - \lambda_{ij})))p(\omega(t - \lambda_{ij}))(1 - p(\omega\lambda_{ij})) \\ &\quad + p(\omega(\tau - \lambda_{ij}))(1 - p(\omega(\tau - \lambda_{ij})))p(\omega\lambda_{ij}) \\ &= \frac{1}{2}p(2\omega(\tau - \lambda_{ij})). \end{aligned}$$

We now consider the entropy.

$$\begin{aligned} H(C_i, C_j) &= H(C_i) + H(C_j | C_i) \\ &= \tilde{h}(\tau\omega) + p(\tau\omega)H(C_j | C_i = 1) \\ &\quad + (1 - p(\tau\omega))H(C_j | C_i = 0) \\ &= \tilde{h}(\tau\omega) + p(\tau\omega)h\left(\frac{p(2(\tau - \lambda_{ij})\omega)}{2p(\tau\omega)}\right) \\ &\quad + (1 - p(\tau\omega))h\left(\frac{p(2(\tau - \lambda_{ij})\omega)}{2(1 - p(\tau\omega))}\right) \\ &\le \tilde{h}(\tau\omega) + h\left(p(\tau\omega)\frac{p(2(\tau - \lambda_{ij})\omega)}{2p(\tau\omega)}\right) \\ &\quad + (1 - p(\tau\omega))\frac{p(2(\tau - \lambda_{ij})\omega)}{2(1 - p(\tau\omega))} \\ &= \tilde{h}(\tau\omega) + \tilde{h}(2(\tau - \lambda_{ij})\omega), \end{aligned}$$

where the inequality uses the concavity of $h(\cdot)$. Let's compare this to the entropy of $H(C_i) + H(C_j) = 2\tilde{h}(\tau\omega)$ for the idealized case where $C_i$ and $C_j$ are independent. Note that if $\lambda_{ij} > \tau/2$, then the above establishes

$$H(C_i, C_j) \le \tilde{h}(\tau\omega) + \tilde{h}(2(\tau - \lambda_{ij})\omega) < 2\tilde{h}(\tau\omega) = H(C_i) + H(C_j).$$

Thus, to make this gap large (proving that there is a huge dependency) we would like $\lambda_{ij}$ to be large (that is $\lambda_{ij} \approx \tau$). By (1), we need pairs $i, j$ for which shifting by $j - i$ leads to another coefficient vector with large overlap. In general, this seems to be hard to analyze. However, if the supports of the $t_i$'s are sufficiently structured, then this is doable.

**Arithmetic progression:** Suppose that the support of the $t_i$'s are in arithmetic progression, that is

$$\text{supp}(t_k) = \{ax + b_k \mid x \in \{0, \dots, \|t_k\| - 1\}\}$$

for all $k \in [s]$. Then

$$\langle \hat{t}_k, \widehat{X^a t_k} \rangle_{\mathbb{R}} = |\text{supp}(t_k) \cap \text{supp}(X^a t_k)| \ge \|t_k\| - 1.$$
Thus, for each $i$, we have

$$ \lambda_{i,i+a} = \langle \hat{t}_1, \widehat{X^a t_1} \rangle_{\mathbb{R}} + \dots + \langle \hat{t}_s, \widehat{X^a t_s} \rangle_{\mathbb{R}} \geq \tau - s, $$

yielding

$$ H(C_i, C_{i+a}) \leq \tilde{h}(\tau\omega) + \tilde{h}(2s\omega). $$

If $n$ is odd, and $a$ and $n$ are coprime, then we can upper bound the total entropy by

$$ \begin{aligned} H(C_0, \dots, C_{n-1}) &\leq H(C_0, C_a) + H(C_{2a}, C_{3a}) \\ &\quad + \dots + H(C_{(n-3)a}, C_{(n-2)a}) \\ &\quad + H(C_{(n-1)a}) \\ &\leq \frac{n-1}{2} \left( \tilde{h}(\tau\omega) + \tilde{h}(2s\omega) \right) + \tilde{h}(\tau\omega) \end{aligned} $$

where the indices $i$ in $C_i$ are read modulo $n$, and using that $0, a, \dots, (n-1)a$ are distinct values mod $n$ when $a$ and $n$ are coprime.

Lemma 2 now yields in this case

$$ \begin{aligned} D(t_1 R_1 + \dots + t_s R_s \| \operatorname{Ber}(\tau\omega)^{\otimes n}) = & H(\operatorname{Ber}(\tau\omega)^{\otimes n}) \\ & - H(C_0, \dots, C_{n-1}) \\ & \geq \frac{n-1}{2} \left( \tilde{h}(\tau\omega) - \tilde{h}(2s\omega) \right). \end{aligned} $$

Using the approximation for $\tilde{h}(\omega)$, we can characterize the divergence asymptotically.

**Corollary 2.** Let $\omega \geq \log(n)$ and $\tau \geq 2s$. Let $t_1(X), \dots, t_s(X)$ be vectors with supports in arithmetic progression with the same common difference. Then the divergence to $I \stackrel{\text{def}}{=} \operatorname{Ber}(\tau\omega)^{\otimes n}$ can be bounded to the range

$$ D(t_1 R_1 + \dots + t_s R_s, I) = \Theta(n2^{-4s\omega}). $$

Notably, this value is non-negligible when $s\omega = O(\log(n))$.

*Proof.* The argument generalizes that of Corollary 1. The details are provided in the full version [8]. □

## V. CONCLUSION

In this work, we studied distributions of the form $\sum_{i=1}^s t_i(X)R_i(X)$ where the $t_i \in P_n$ are fixed and $R_i \leftarrow \operatorname{Ber}(\omega)^{\otimes n}$ (independently), and when $\omega = \Theta(\log n)$ we established cases where this distribution is non-negligibly far from the ideal distribution, i.e., the distribution over $P_n$ with matching marginal distributions and independent coefficients. As discussed, understanding the behavior of this distribution is crucial for understanding the decryption failure rate for HQC [2]. To conclude this paper, we discuss implications of our work for worst-case to average-case reductions in quasi-cyclic code-based cryptography.

For cryptographic purposes, it is of course vital that hardness assumptions hold for average-case problems: namely, it is hard to solve some computational problem (such as the decoding problem) when the instances are sampled randomly. However, from a complexity-theoretic perspective we have a much firmer theory of the hardness of worst-case problems. That is, we have a more mature theory of which problems are hard when the instances for a given algorithm are chosen adversarially.

In the case of LWE, Regev [14], [15] famously showed that the average-case LWE problem can be reduced to certain worst-case problems on lattices. Inspired by this, Brakerski et al. [16] recently introduced a worst-case to average-case reduction for codes: namely, a reduction from the classic worst-case decoding problem where $\mathbf{A}$, $\mathbf{s}$ and $\mathbf{e}$ are adversarially chosen, with the promise that $\mathbf{e}$ has Hamming weight at most $\tau$. One can imagine generalizing this to the quasi-cyclic case, as was successfully done in the case of lattices (the analogous problem there is typically termed Ring-LWE). Here, if one works with a rate $1/s$ quasi-cyclic code the natural reduction strategy takes as input a noisy codeword $(a_1(X)m(X) + t_1(X), \dots, a_s(X)m(X) + t_s(X))$ (with the sum of the weights of the noise vectors $t_i$ being at most $\tau$), and then produces “Ring-LPN” like samples by sampling a “smoothing” vector $(R_1(X), \dots, R_s(X))$ and considering

$$ \left( \sum_{i=1}^{s} a_i(X) R_i(X), \left( \sum_{i=1}^{s} a_i(X) R_i(X) \right) m(X) + \sum_{i=1}^{s} t_i(X) R_i(X) \right). $$

At the very least, this requires us to analyze the distribution $\sum_{i=1}^s t_i(X)R_i(X)$, as we undertake in this work.<fnref n="2" /> Furthermore, for the standard Ring-LPN assumption, one must have $\sum_{i=1}^s t_i(X)R_i(X)$ close to an independent Bernoulli polynomial. Our work points out that for certain vectors $t_1, \dots, t_s$ this provably fails. We remark that the structural assumptions made in our work – such as the supports of the $t_i$'s lying in arithmetic progression – lead to instances of the (worst-case) decoding problem that can be efficiently solved (essentially by guessing the arithmetic progression, of which there are at most $O(n^2)$). Hence, it is reasonable to hope that for “hard” instances of the decoding problem $\sum_{i=1}^s t_i(X)R_i(X)$ is indeed close to an independent Bernoulli polynomial. Nonetheless, our work highlights subtleties that the analysis of such a reduction must account for.

## ACKNOWLEDGMENT

The authors would like to thank Jeroen Zuiddam and Christian Schaffner for helpful feedback. MB’s work was supported by NWO Gravitation Project QSC. NR is supported by an NWO (Dutch Research Council) grant with number C.2324.0590. This work was done in part while NR was visiting the Simons Institute for the Theory of Computing, supported by DOE grant # DE-SC0024124.

## REFERENCES

[1] C. Aguilar Melchor, N. Aragon, P. Barreto, S. Bettaieb, L. Bidoux, O. Blazy, J.-C. Deneuville, P. Gaborit, S. Ghosh, S. Gueron, T. Güneysu, R. Misoczki, E. Persichetti, J. Richter-Brockmann, N. Sendrier, J.-P. Tillich, V. Vasseur, and G. Zémor, “BIKE,” Round 4 Submission to the NIST Post-Quantum Cryptography Call, v. 5.1, Oct. 2022. [Online]. Available: https://bikesuite.org

[2] C. Aguilar Melchor, N. Aragon, S. Bettaieb, L. Bidoux, O. Blazy, J. Bos, J.-C. Deneuville, A. Dion, P. Gaborit, J. Lacan, E. Persichetti, J.-M. Robert, P. Véron, G. Zémor, and J. Bos, “HQC,” Round 4 Submission to the NIST Post-Quantum Cryptography Call, Oct. 2022, https://pqc-hqc.org/.

<footnote n="2">²More precisely, we make a step assuming one is choosing the Bernoulli distribution to smooth. Other choices could be made, but we view this as a natural first step.</footnote>
<footnote>[3] M. Albrecht, D. J. Bernstein, T. Chou, C. Cid, J. Gilcher, T. Lange, V. Maram, I. von Maurich, R. Mizoczki, R. Niederhagen, E. Persichetti, K. Paterson, C. Peters, P. Schwabe, N. Sendrier, J. Szefer, C. J. Tjhai, M. Tomlinson, and W. Wen, “Classic McEliece (merger of Classic McEliece and NTS-KEM),” https://classic.mceliece.org, Nov. 2022, fourth round finalist of the NIST post-quantum cryptography call.</footnote>

<footnote>[4] J.-B. Fischer and J. Stern, "An efficient pseudo-random generator provably as secure as syndrome decoding," in *Advances in Cryptology - EUROCRYPT'96*, ser. LNCS, U. Maurer, Ed., vol. 1070. Springer, 1996, pp. 245–255.</footnote>

<footnote>[5] O. Regev, “On lattices, learning with errors, random linear codes, and cryptography,” in *Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005*, 2005, pp. 84–93. [Online]. Available: http://doi.acm.org/10.1145/1060590.1060603</footnote>

<footnote>[6] M. Bombar, A. Couvreur, and T. Debris-Alazard, “Pseudorandomness of decoding, revisited: Adapting ohcp to code-based cryptography,” in *Advances in Cryptology - ASIACRYPT 2023 29th International Conference on the Theory and Application of Cryptology and Information Security*, ser. LNCS, J. Guo and R. Steinfeld, Eds. Springer, Dec. 2023.</footnote>

<footnote>[7] A. Kawachi, “Hamming Weight of Product of Random Sparse Polynomials.”</footnote>

<footnote>[8] M. Bombar, N. Resch, and E. Wiedijk, “On the independence assumption in quasi-cyclic code-based cryptography,” 2025, long version: https://arxiv.org/ abs/2501.02626.</footnote>

<footnote>[9] J. H. B. Kemperman, “On the optimum rate of transmitting information,” in *Probability and Information Theory*, M. Behara, K. Krickeberg, and J. Wolfowitz, Eds. Springer, pp. 126–169.</footnote>

<footnote>[10] O. Binette, “A Note on Reverse Pinsker Inequalities,” vol. 65, no. 7, pp. 4094–4096.</footnote>

<footnote>[11] T. Tao, “Sumset and Inverse Sumset Theory for Shannon Entropy,” vol. 19, no. 4, pp. 603–639.</footnote>

<footnote>[12] B. Green, F. Manners, and T. Tao, “Sumsets and entropy revisited,” *Random Structures & Algorithms*, vol. 66, no. 1, 2025.</footnote>

<footnote>[13] C. Pacher, P. Grabenweger, and D. E. Simos, “Weight distribution of the syndrome of linear codes and connections to combinatorial designs,” in *2016 IEEE International Symposium on Information Theory (ISIT)*, pp. 3038–3042.</footnote>

<footnote>[14] O. Regev, “On lattices, learning with errors, random linear codes, and cryptography,” in *Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing*, ser. STOC '05. Association for Computing Machinery, pp. 84–93.</footnote>

<footnote>[15] Z. Brakerski, A. Langlois, C. Peikert, O. Regev, and D. Stehlé, “Classical hardness of learning with errors,” in *Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing*. ACM, pp. 575–584.</footnote>

<footnote>[16] Z. Brakerski, V. Lyubashevsky, V. Vaikuntanathan, and D. Wichs, “Worst-Case Hardness for LPN and Cryptographic Hashing via Code Smoothing,” in *Advances in Cryptology – EUROCRYPT 2019*, ser. Lecture Notes in Computer Science, Y. Ishai and V. Rijmen, Eds. Springer International Publishing, pp. 619–635.</footnote>