HQC Beyond the BSC: Towards Error Structure-Aware Decoding

Abstract

In Hamming Quasi-Cyclic (HQC), one of the finalists in the NIST competition for the standardization of post-quantum cryptography, decryption relies on decoding a noisy codeword through a public error-correcting code. The noise vector has a special form that depends on the secret key (a pair of sparse polynomials). However, the decoder, which is currently employed in HQC, is agnostic to the secret key, operating under the assumption that the error arises from a Binary Symmetric Channel (BSC). In this paper, we demonstrate that this special noise structure can instead be leveraged to develop more powerful decoding strategies.

We first study the problem from a coding-theoretic perspective. The current code design, which admits a non-zero decryption failure rate, is close to optimal in the setting of a decoder that is agnostic to the error structure. We show that there are code-decoder pairs with a considerably shorter code length that can guarantee unique decoding by taking the error structure into account. This result is non-constructive, i.e., we do not provide an explicit code construction and it remains open whether efficient decoding is possible. Nevertheless, it highlights the potential that can be tapped by taking the error structure into account. We then argue that, in practice, the matter of decoding in HQC can be related to solving an instance of the noisy syndrome decoding problem, in which the parity-check matrix is constituted by the polynomials in the secret key. We show that, using decoders for Low-Density Parity-Check (LDPC) and Moderate-Density Parity-Check (MDPC) codes, one can significantly reduce the entity of the noise and, de facto, also the Decoding Failure Rate (DFR) of the HQC decoder.

This preliminary study leaves some open questions and problems. While it shows that decoding in HQC can be improved, the modeling of the DFR gets more complicated: even for the basic decoder we propose in this paper, we have not been able to devise a reliable DFR model. This is likely due to the fact that the decoder structure resembles the iterative nature of LDPC/MDPC decoders, for which devising a reliable DFR estimation is a well-known difficult problem.

A Proofs of Propositions 1 and 2

We require two preliminary results, which we give and prove here.

Proposition 5

For two polynomials $\textbf{a}\in \mathcal R_{w_a}$ and $\textbf{b}\xleftarrow {\$}\mathcal R_{w_b}$, an arbitrary coefficient (say, the first one) in the product $\textbf{a}\cdot \textbf{b}$ is set with probability

$$\begin{aligned} \rho _{w_a, w_b} = \sum _{{\begin{smallmatrix} \ell \in [1 ; \min \{w_a, w_b\}]\\ \ell \text { odd}\end{smallmatrix}}}\frac{\left( {\begin{array}{c}w_a\\ \ell \end{array}}\right) \left( {\begin{array}{c}n-w_a\\ w_b - \ell \end{array}}\right) }{\left( {\begin{array}{c}n\\ w_b\end{array}}\right) }. \end{aligned}$$

Proof

According to the rules of polynomial multiplication, we have:

$$ c_\ell = \sum _{{\begin{smallmatrix}i,j\\ i + j \equiv \ell \mod n\end{smallmatrix}}} a_i \cdot b_j, \quad \text {for } \ell \in \{0,1, \ldots , n-1\}. $$

We have $c_\ell = 1$ only if, in the above equation, the number of terms $a_i\cdot b_j$ equal to 1 is odd. The probability to have exactly $\ell$ terms $a_i\cdot b_j$ which are equal to 1 is $\frac{\left( {\begin{array}{c}w_a\\ \ell \end{array}}\right) \left( {\begin{array}{c}n-w_a\\ w_b-\ell \end{array}}\right) }{\left( {\begin{array}{c}n\\ w_b\end{array}}\right) }$.   $\square$

Proposition 6

Let $\textbf{x},\textbf{y}\in \mathcal R_w$, $\textbf{r}^{(1)} \xleftarrow {\$}\mathcal R_{w_r}$, $\textbf{r}^{(2)} \xleftarrow {\$}\mathcal R_{w_r}$, and $\textbf{e}\xleftarrow {\$}\mathcal {R}_{w_e}$. An arbitrary coefficient of the polynomial $\textbf{z}= \textbf{x}\cdot \textbf{r}^{(2)}+\textbf{y}\cdot \textbf{r}^{(1)}+\textbf{e}$ follows a Bernoulli distribution with parameter

$$\begin{aligned} \rho _z = 4\rho _{w, w_r}^2\rho _e - 2\rho _{w, w_r}^2 - 4 \rho _{w, w_r}\rho _e+2\rho _{w, w_r}+\rho _e. \end{aligned}$$

Under the assumption that the coefficients behave as independent random variables, the weight of $\textbf{z}$ follows a binomial distribution.

Proof

According to Proposition 5, the i-th coefficient of both products $\widehat{\textbf{x}} = \textbf{x}\cdot \textbf{r}^{(2)}$ and $\widehat{\textbf{y}} = \textbf{y}\cdot \textbf{r}^{(1)}$ is Bernoulli distributed with parameter $\rho _{w, w_r^{(2)}}$ and $\rho _{w, w_r^{(1)}}$. Then, the i-th coefficient of $\textbf{z}$ will be set with probability

$$\begin{aligned} &\textrm{Pr}\left[ \widehat{x}_i = 1\right] \cdot \textrm{Pr}\left[ \widehat{y}_i = 0\right] \cdot \textrm{Pr}\left[ e_i = 0\right] + \textrm{Pr}\left[ \widehat{x}_i = 0\right] \cdot \textrm{Pr}\left[ \widehat{y}_i = 1\right] \cdot \textrm{Pr}\left[ e_i = 0\right] \\ \nonumber & \qquad + \textrm{Pr}\left[ \widehat{x}_i = 0\right] \cdot \textrm{Pr}\left[ \widehat{y}_i = 0\right] \cdot \textrm{Pr}\left[ e_i = 1\right] + \textrm{Pr}\left[ \widehat{x}_i = 1\right] \cdot \textrm{Pr}\left[ \widehat{y}_i = 1\right] \cdot \textrm{Pr}\left[ e_i = 1\right] . \end{aligned}$$

Substituting the probabilities with the associated Bernoulli parameters, we get

$$\begin{aligned} &\rho _z=(1-\rho _{w,w_r})(1-\rho _{w,w_r})\rho _e + (1-\rho _{w,w_r})\rho _{w,w_r}(1-\rho _e)\\\nonumber & {\qquad \qquad \qquad } +\rho _{w,w_r}(1-\rho _{w,w_r})(1-\rho _e)+\rho _{w,w_r}\rho _{w,w_r}\rho _e. \end{aligned}$$

After some manipulations, we obtain the expression for $\rho _z$.    $\square$

We now proceed to prove Proposition 1; the proof for Proposition 2 is carried out in the same way and is hence omitted.

1.1 A.1 Proof of Proposition 1

For $i\in \text {supp}(\textbf{r}^{(2)})$, we derive the probability distribution of the counter value. We express $\textbf{r}^{(2)}$ as

$$ \textbf{r}^{(2)} = \underbrace{(0,\cdots ,0,1,0,\cdots ,0)}_{{\begin{smallmatrix}\text {1 in position }j\text {,}\\ 0 \text { elsewhere}\end{smallmatrix}}}+\widetilde{\textbf{r}}^{(2)}, $$

where $\widetilde{\textbf{r}}^{(2)}$ is equal to $\textbf{r}^{(2)}$ apart from the coefficient in position j, which is 0 (instead of 1). Observe that $\textrm{wt}( \widetilde{\textbf{r}}^{(2)} ) = w_r - 1$. The counter associated to $r^{(2)}_j$ is obtained by summing the coefficients of the estimated error vector $\widehat{\textbf{z}}$ in the positions indexed by $\text {supp}(\textbf{x})+j = \{s + j\mod n\mid s\in \text {supp}(\textbf{x})\}$. For each $\ell \in \text {supp}(\textbf{x})+j$, we have:

$$ z_\ell = 1 + \underbrace{(\textbf{x}\cdot \widetilde{\textbf{r}}^{(2)})_\ell + (\mathbf {y\cdot \textbf{r}^{(1)}}+\textbf{e})_\ell }_{\widetilde{z}_\ell } = 1+\widetilde{z}_\ell , $$

where $z_\ell$ is the $\ell$-th coefficient of $\widetilde{\textbf{z}} = \textbf{x}\cdot \widetilde{\textbf{r}}^{(2)} + \mathbf {y\cdot \textbf{r}^{(1)}}+\textbf{e}$. With arguments analogous to those in Proposition 6, we see that $(\mathbf {y\cdot \textbf{r}^{(1)}}+\textbf{e})_j$ is Bernoulli distributed with parameter

$$ \rho _{w, w_r}\left( 1-\frac{w_e}{n}\right) + (1- \rho _{w, w_r})\frac{w_e}{n} . $$

Also $(\textbf{x}\cdot \widetilde{\textbf{r}}^{(2)})_j$ can be considered as Bernoulli distributed; in particular, the probability that its $\ell$-th coefficient is 1 corresponds to

$$ \widetilde{\rho }_{w, w_r-1} = \sum _{{\begin{smallmatrix}\ell \in [1 ; \min \{w-1, w_r -1\}]\\ \ell \text { odd}\end{smallmatrix}}}\frac{\left( {\begin{array}{c}w-1\\ \ell \end{array}}\right) \left( {\begin{array}{c}n-1-w\\ w_r-1-\ell \end{array}}\right) }{\left( {\begin{array}{c}n-1\\ w_r - 1\end{array}}\right) }. $$

Notice that this probability slightly differs from the one in Proposition 5. This is because we are considering only $w-1$ coefficients of $\textbf{x}$ and $n-1$ coordinates for $\widetilde{\textbf{r}}^{(2)}$ (as one is set to 0).

Putting everything together, we get that $\widetilde{z}_j$ is equal to 1 with probability

$$\begin{aligned} \widetilde{\rho } = \underbrace{\widetilde{\rho }_{w, w_r - 1}}_{\textrm{Pr}\left[ (\textbf{x}\cdot \widetilde{\textbf{r}}^{(2)})_\ell = 1\right] }& \nonumber \underbrace{\left( 1-\rho _{w, w_r} \left( 1-\frac{w_e}{n}\right) - (1- \rho _{w, w_r})\frac{w_e}{n}\right) }_{\textrm{Pr}\left[ (\textbf{y}\cdot \textbf{r}^{(1)}+\textbf{e})_\ell = 0\right] } \\\nonumber & + \underbrace{(1- \widetilde{\rho }_{w, w_r - 1})}_{\textrm{Pr}\left[ (\textbf{x}\cdot \textbf{r}^{(2)})_\ell = 0\right] }\underbrace{\left( \rho _{w, w_r}\left( 1-\frac{w_e}{n}\right) + (1- \rho _{w, w_r})\frac{w_e}{n}\right) }_{\textrm{Pr}\left[ (\textbf{y}\cdot \textbf{r}^{(1)}+\textbf{e})_\ell = 1\right] } \end{aligned}$$

Let $\bot _{\textrm{in}}(\ell )$ indicate the event that the inner code codeword in which the $\ell$-th coordinate is contained is wrongly decoded. The complementary event (i.e., a decoding success) is indicated as ${\bar{\bot }}_{\textrm{in}}(\ell )$. Then, we have

$$\begin{aligned} \textrm{Pr}\left[ \widehat{z}_\ell = 1\right] = \textrm{Pr}\left[ \bar{\bot }_{\textrm{in}}(\ell )\mid \widetilde{z}_\ell = 0\right] \cdot \textrm{Pr}\left[ \widetilde{z}_\ell = 0\right] + \textrm{Pr}\left[ \bot _{\textrm{in}}(\ell )\mid \widetilde{z}_\ell = 1\right] \textrm{Pr}\left[ \widetilde{z}_\ell = 1\right] . \end{aligned}$$

(3)

Indeed, the first term (i.e., $\textrm{Pr}\left[ \bar{\bot }_{\textrm{in}}(\ell )\mid \widetilde{z}_\ell = 0\right] \cdot \textrm{Pr}\left[ \widetilde{z}_\ell = 0\right]$) is the probability that $z_\ell = 1$ and decoding is successful, so $z_\ell$ is correctly estimated. Analogously, the second term (i.e., $\textrm{Pr}\left[ \bot _{\textrm{in}}(\ell )\mid \widetilde{z}_\ell = 1\right] \textrm{Pr}\left[ \widetilde{z}_\ell = 1\right]$) corresponds to the probability that $z_\ell = 0$ but there is a decoding failure, so $z_\ell$ is wrongly estimated.

Let $\text {supp}_{\textrm{in}}(\ell )$ denote the set of indices that correspond to the same inner codeword as position $\ell$. Then, $\widehat{z}_\ell = z_\ell = 1$ if and only if the remaining $n_2-1$ positions allow correct decoding of position $\ell$, despite position $\ell$ being erroneous. This happens whenever the number of set coefficients in $\text {supp}_{\textrm{in}}(\ell )\setminus \{\ell \}$ is not greater than $t-1$, where $t=\lfloor \frac{n_2-1}{2} \rfloor$ denotes the error-correction capability of the inner repetition code. The DFR analysis of HQC assumes independence between the coefficients of the error $\textbf{z}$ [3]. Similarly, we assume that the positions in $\text {supp}_{\textrm{in}}(\ell )\setminus \{\ell \}$ are independently Bernoulli distributed with parameter $\rho _z$ as in Proposition 6. Then, the required probabilities can be calculated as

$$ \textrm{Pr}\left[ \bar{\bot }_{\textrm{in}}(\ell )\mid \widetilde{z}_\ell = 0\right] = \sum _{k = 0}^{t-1}\left( {\begin{array}{c}n_2-1\\ k\end{array}}\right) \rho _z^k (1-\rho _z)^{n_2-1-k}. $$

With analogous reasoning, we obtain

$$ \textrm{Pr}\left[ \bot _{\textrm{in}}(j)\mid \widetilde{z}_j = 1\right] = \sum _{k = t}^{n_2-1}\left( {\begin{array}{c}n_2-1\\ k\end{array}}\right) \rho _z^k(1-\rho _z)^{n_i-1-k}. $$

Then, writing $\widehat{\rho }= \textrm{Pr}\left[ \widehat{z}_\ell = 1\right]$, we obtain (3) as

$$\begin{aligned} \widehat{\rho }= (1-\widetilde{\rho })\sum _{k = 0}^{t-1}\left( {\begin{array}{c}n_i-1\\ k\end{array}}\right) \rho _z^k(1-\rho _z)^{n_2-1-k} + \widetilde{\rho }\sum _{k = t}^{n_2-1}\left( {\begin{array}{c}n_2-1\\ k\end{array}}\right) \rho _z^k(1-\rho _z)^{n_2-1-k}. \end{aligned}$$

(4)

We model $\sum _{j\in \text {supp}\textbf{x}+i} \widehat{z}_j$ as a sum of independent random variables. Consequently, $\sum _{j\in \text {supp}\textbf{x}+i} \widehat{z}_j$ follows the binomial distribution with w trials and success probability $\widehat{\rho }$ and we obtain

$$\begin{aligned} \tau _{1\rightarrow 0} = \sum _{\ell = 0}^{T-1}\left( {\begin{array}{c}w\\ \ell \end{array}}\right) \widehat{\rho }^{\ell }(1-\widehat{\rho })^{w-\ell }. \end{aligned}$$