A Finite Regime Analysis of Information Set Decoding Algorithms

In this work, we provide a survey of the existing ISD algorithms, with explicit finite regime expressions for their spatial and temporal complexities. We also detail which free parameters have to be optimized for each of the ISD algorithms, and provide a software tool implementing the said optimization procedure on a given set of code parameters in [26].

This work is organized as follows. Section 2 states the required notation and recollects the code-based cryptography background required to understand ISD algorithms. Section 3 surveys the existing ISD algorithms, providing complexity estimates for both the space they require and their execution time. Section 4 contains a critical discussion of the results obtained in the finite regime in comparison to the ones available via asymptotic estimates, while Section 5 summarizes our conclusions.

The class of NP-Complete problems is of particular interest to design cryptosystems, as it is widely believed that problems contained in such a class cannot be solved in polynomial time by a quantum computer. Indeed, the best known approaches to solve both the Codeword Finding Problem (CFP) and the Syndrome Decoding Problem (SDP) have a computational complexity which is exponential in the weight of the codeword or error vector to be found. A notable example of code-based cryptosystem relying on the hardness of the Syndrome Decoding Problem (SDP) is the one proposed by Niederreiter in [3].

Niederreiter cryptosystem generates a public–private key-pair selecting as the private key an instance of a code from a family for which efficient decoding algorithms are available. The code is then represented by its parity check matrix $H_{priv}$, which is multiplied by a rank-r random square binary matrix S obtaining the public key of the cryptosystem $H_{pub}=S{H}_{priv}$. The assumption made by Niederreiter is that the multiplication by the random, full rank matrix S makes $H_{pub}$ essentially indistinguishable from a random parity matrix. While the original choice to employ a Reed–Solomon code as private code was found to falsify this assumption and lead to a practical attack, other code families have proven to be good candidates (e.g., Goppa codes, Low/Medium Density Parity Check codes [28,29,30,31]). A message is encrypted in the Niederreiter cryptosystem encoding it as a fixed weight error vector e and computing its syndrome through $H_{pub}$, $s=H_{pub}{e}^T$, which acts as the ciphertext. The  owner of the private key $(S,H_{priv})$ is able to decipher the ciphertext through first obtaining $s^{\prime }=S^{-1}s$ and subsequently performing the syndrome decoding of $s^{\prime }$ employing $H_{priv}$.

It is easy to note that, under the assumption that $H_{pub}$ is indistinguishable from a random parity check matrix, an attacker willing to perform a Message Recovery Attack (MRA) must solve an instance of the Syndrome Decoding Problem (SDP). We note that, as proven by Niederreiter [3], the Syndrome Decoding Problem (SDP) is computationally equivalent to the problem of correcting a bounded amount of errors affecting a codeword, when given a random generator matrix of the code, G. Such  a problem goes by the name of Decoding Problem, and is the mainstay of the original cryptosystem proposal by McEliece [32]. In such a scheme, the ciphertext thus corresponds to the sum between a codeword of the public code, obtained as $mG$, with m being a length-k vector, and a vector e of weight t. The  message can either be encoded into e or into m; in the latter case, Message Recovery Attack (MRA) is performed by searching for the error vector e and, subsequently, by adding it to the intercepted ciphertext. We point out that this search can automatically turned into the formulation of Syndrome Decoding Problem (SDP), by first computing a valid $H_{pub}$ from G and then by trying to solve Syndrome Decoding Problem (SDP) on the syndrome of the intercepted ciphertext through $H_{pub}$.

One of the most prominent cases where Codeword Finding Problem (CFP) appears in code-based cryptosystems is represented by a Key Recovery Attack (KRA) against Niederreiter cryptosystems where the private parity check matrix $H_{priv}$ contains rows with a known low weight w. Indeed, in such a case, considering $H_{pub}$ as the generator matrix of the dual code, solving the Codeword Finding Problem (CFP) for such a code reveals the low weight rows of $H_{priv}$. We note that such a Key Recovery Attack (KRA) is in the same computational complexity class as Syndrome Decoding Problem (SDP), assuming that the obfuscation of $H_{pub}$ makes it indistinguishable from a random one.

Two notable cases where solving the Codeword Finding Problem (CFP) is the currently best known method to perform a Key Recovery Attack (KRA) are the LEDAcrypt [33] and BIKE [34] proposals to the mentioned NIST standardization effort for post-quantum cryptosystems. Since such a Codeword Finding Problem (CFP) can also be seen as the problem of finding a binary vector c with weight w such that $H_{pub}{c}^T=0$, the problem is also known as the Homogeneous Syndrome Decoding Problem (SDP), as it implies the solution of a simultaneous set of linear equations similar to the Syndrome Decoding Problem (SDP), save for the syndrome being set to zero.

As described in the previous section, security of code-based cryptosystems relies on the hardness of solving Syndrome Decoding Problem (SDP) or Codeword Finding Problem (CFP) instances. In this section, we analyze the case of Syndrome Decoding Problem (SDP) and show that the optimal strategy to perform Message Recovery Attack (MRA) depends on the code parameters. The optimal strategy for solving Syndrome Decoding Problem (SDP) depends on the relation between the actual parameters of the instance under analysis. In particular, in the cases where t is above the Gilbert–Varshamov (GV) distance [35], Generalized Birthday Algorithm (GBA) is the best currently known algorithm for solving Syndrome Decoding Problem (SDP) [36,37]. However, for the cases we consider in this paper, practical values of t are significantly smaller than the GV distance; in such cases, the best known methods to solve Syndrome Decoding Problem (SDP) go by the name of Information Set Decoding (ISD) algorithms. Such algorithms are aimed at lessening the computational effort required in the guesswork of an exhaustive search for the unknown error vector e of weight t, given  a syndrome and a parity check matrix. We point out that it is also possible to adapt all Information Set Decoding (ISD) algorithms, save for the first one proposed by Prange [10], to solve the Codeword Finding Problem (CFP), as a consequence of the structural similarity of the two problems.

All Information Set Decoding (ISD) algorithms share a common structure where an attempt at retrieving the error vector corresponding to a given syndrome is repeated, for a number of times whose average value depends on the success probability of the single attempt itself. The complexity of all Information Set Decoding (ISD) variants can be expressed as the product between the complexity of each attempt, which we denote as $C_{\mathrm{iter}}$, and the average number of required attempts. In particular, such a value can be obtained as the reciprocal of the success probability of each attempt, which we denote as ${\mathrm{Pr}}_{\mathrm{succ}}$; thus, when considering a code with length n, redundancy $r=n-k$ and Hamming weight of the sought error bounded to t, we generically denote the time complexity of obtaining one solution of Syndrome Decoding Problem (SDP) employing the Information Set Decoding (ISD) variant at hand, i.e.,

As we show in the following, the work factor of a Message Recovery Attack (MRA) performed through Information Set Decoding (ISD) may actually depend on the system parameters; to  this end, we first exploit the following well-known result. Let $\mathcal{C}(n,k,d)$ be a linear binary code with length n, dimension k and minimum distance d, and let H be a parity-check matrix for $\mathcal{C}(n,k,d)$. Let s be a length-r binary vector and t be an integer ≤n; then, if $t<⌈\frac{d}{2}⌉$, there is at maximum one vector e of weight t such that $s=H{e}^T$.

Thus, when $H_{pub}$ is the parity-check matrix of a code with minimum distance $d>2t$, then solving Syndrome Decoding Problem (SDP) guarantees that the found error vector corresponds to the one that was used to encrypt the message. In this case, the attack work factor corresponds to $C_{\mathrm{ISD}}(n,r,t)$.

However, when $d\le 2t$, the time complexity of a Message Recovery Attack (MRA) needs to be derived through a different approach. Indeed, in such a case, the adversary has no guarantee that the output of Information Set Decoding (ISD) corresponds to the error vector that was actually used in the encryption phase. Thus, the work factor of a Message Recovery Attack (MRA) cannot be simply taken as the time complexity of the chosen Information Set Decoding (ISD) algorithm. Let  s be the syndrome corresponding to the intercepted ciphertext and e be the searched error vector, i.e., $s=H_{pub}{e}^T$. We  define

Clearly, $N\left(e\right)$ corresponds to the number of valid outputs that Information Set Decoding (ISD) can produce, when applied on the syndrome s corresponding to e. In such a case, the probability that an Information Set Decoding (ISD) iteration will not find any valid error vector can be estimated as ${\left(1-{Pr}_{\mathrm{succ}}\right)}^{N\left(e\right)}$. Thus, in such a case, one attempt of Information Set Decoding (ISD) will succeed with probability ${Pr}_{\mathrm{succ}}^{\prime }\left(e\right)=1-{\left(1-{Pr}_{\mathrm{succ}}\right)}^{N\left(e\right)}$. In particular, the algorithm will randomly return a vector among the set of the $N\left(e\right)$ admissible ones: thus, the probability that the obtained vector corresponds to e is $1/N\left(e\right)$.

To obtain a closed-form expression for the attack work factor, we can consider the average value of $N\left(e\right)$, which we obtain by averaging over all the possible vectors e of weight t and length n, and denote it with N. Then, the attack work factor can be computed as

In particular, it can be shown that $NP\ge 1-{\left(1-P\right)}^N$, so that with

We point out that, for the cases we analyze in this paper, we have $N{\mathrm{Pr}}_{\mathrm{succ}}\ll 1$, so that $\alpha \approx 1$. Thus, from now on, we assume $\alpha =1$, i.e., that the time complexity of performing a Message Recovery Attack (MRA) is equal to that of running an Information Set Decoding (ISD) algorithm in the case in which a unique solution exists.

Prange’s algorithm [10] is the first known variant of ISD, based on the idea of guessing a set $\mathcal{I}$ of k error-free positions in the error vector e to be found in the Syndrome Decoding Problem (SDP). For  this purpose, the columns of H are permuted so that those indexed by $\mathcal{I}$ are packed to the left. This operation is equivalent to the multiplication of H by an appropriately sized permutation matrix P. The column-reordered matrix $\widehat{H}=HP$ is hence obtained, which can be put in Reduced Row Echelon Form (RREF), with the identity matrix $I_r$ placed to the right, i.e., $\left[V{I}_r\right]=U\widehat{H}$. If turning $\widehat{H}$ in Reduced Row Echelon Form (RREF) is not possible as the $r\times r$ rightmost submatrix is not full-rank, a different permutation is picked. The same transformation U required to bring H in Reduced Row Echelon Form (RREF) is then applied to the single-bit rows of the column syndrome vector s, obtaining $\overline{s}=Us$. If  the weight of the permuted error vector $\widehat{e}$ obtained as $\widehat{e}=eP=\left[0_{1\times k}{\overline{s}}^T\right]$, where $0_{1\times k}$ is the all-zero error vector of length k, matches the expected error weight t, then the algorithm succeeds and the non-permuted error vector $\widehat{e}{P}^T$ is returned. A pseudo-code description of Prange’s ISD algorithm is provided in Algorithm 1.

For the sake of clarity, from now on, we denote as ISextract$(H,s)$ the procedure computing $\langle P,\left[V{I}_r\right],\overline{s}\rangle$, performed on Lines 2–7 of Algorithm 1, with computational time complexity $C_{\mathrm{IS}}(n,r)$ and space complexity $\mathcal{O}\left(rn\right)$.

The ISD algorithm introduced by Lee and Brickell in [11] starts with the same initial operations as in Prange’s, i.e., the computation of the Reduced Row Echelon Form (RREF) of $\widehat{H}$ and the derivation of the corresponding syndrome $\overline{s}$. However, Lee and Brickell improved Prange’s original idea by allowing p positions in the k selected in the error vector to be error-affected. These p remaining error positions are guessed. To verify the guess, Lee and Brickell exploit the identity $\left[V{I}_r\right]{\widehat{e}}^T=\overline{s}$, where  $\widehat{e}$ is split in two parts, $\widehat{e}=\left[{\widehat{e}}_1{\widehat{e}}_2\right]$, with ${\widehat{e}}_1$ being k bit long and with weight p, and ${\widehat{e}}_2$ being r bits long and with weight $t-p$. The identity is rewritten as $V{\widehat{e}}_1^T+I_r{\widehat{e}}_2^T=V{\widehat{e}}_1^T+{\widehat{e}}_2^T=\overline{s}$, from which follows the fact that $V{\widehat{e}}_1^T+\overline{s}={\widehat{e}}_2^T$ must have weight $t-p$. Indeed, this condition is employed by the algorithm to check if the guess of p positions is correct. The procedure is summarized in Algorithm 2.

The structure of Lee and Brickell’s Information Set Decoding (ISD) allows employing substantially the same algorithm to solve the Codeword Finding Problem (CFP), given a parity matrix H as the representation of the code where a weight w codeword c should be found. The line of reasoning to employ Lee and Brickell’s Information Set Decoding (ISD) to solve the Codeword Finding Problem (CFP) is to note that, by definition, for any codeword c of the code represented by H we have that $H{c}^T=0_{1\times r}$, i.e., a codeword multiplied by the parity check matrix yields a null syndrome. As a consequence, we have that $0_{1\times r}=H{c}^T=HP{P}^T{c}^T=\widehat{H}{P}^T{c}^T=\widehat{H}{\widehat{c}}^T=V{\widehat{c}}_1^T+{\widehat{c}}_2^T$. This implies that $V{\widehat{c}}_1^T={\widehat{c}}_2^T$, which can be exploited as an alternative stopping condition to the one of Algorithm 2, yielding in turn Algorithm 3. The only remaining difference between the Syndrome Decoding Problem (SDP) solving Lee and Brickell’s ISD and the Codeword Finding Problem (CFP) is represented by the ISextract primitive, which no longer needs to compute a transformed syndrome $\overline{s}=Us$ as it is null. We thus have a small reduction in $C_{\mathrm{IS}}(n,r)$, which becomes $C_{\mathrm{IS}}(n,r)=\frac{1}{{\prod }_{i=1}^r(1-2^{-i})}{C}_{\mathrm{RREF}}(n,r)+n$, losing an additive $r^2$ term. We note that such a reduction is expected to have little impact in practice as the dominant portion of the ISextract function is represented by the Reduced Row Echelon Form (RREF) computation. This in turn implies that solving the Syndrome Decoding Problem (SDP) on a code $\mathcal{C}$ has practically the same complexity of finding a codeword with weight $w=t$ in the same code. Therefore, finding low-weight codewords in the code defined by a Niederreiter cryptosystem public key $H_{pub}$ has an effort comparable to the one of performing syndrome decoding assuming an error with the same weight as the codeword to be found. Two families of codes which may be vulnerable to such an attack unless the parameters are designed taking into account a Codeword Finding Problem (CFP) ISD are the Low Density Parity Check (LDPC) and Moderate Density Parity Check (MDPC) codes. Indeed, such code families can be represented with a parity check matrix with low-weight rows, and such a low-weight representation can be relied upon to perform efficient decoding, leading to an effective cryptosystem break. Indeed, we now show that, if a code $\mathcal{C}(n,k,d)$ can be represented by a low-weight parity matrix $H_{priv}$, the code will contain low weight codewords. Without loss of generality, consider $k>r$. Moreover, consider $H_{priv}$ as split in three portions $\left[A_l{A}_{r}B\right]$ of size $r\times (k-r)$, $r\times r$ and $r\times r$, respectively, with B non-singular. We derive the corresponding generator matrix as and consider the bottom r rows $\left[0_{r\times (k-r)}{I}_{r\times r}{\left(B^{-1}{A}_r\right)}^T\right]$. Consider the product of such bottom rows by $B^T$, yielding $\left[0_{r\times (k-r)}{I}_{r\times r}{\left(B^{-1}{A}_r\right)}^T\right]B^T=\left[0_{r\times (k-r)}{B}^T{A}_r^T\right]$ and note that all the rows of this product are valid codewords, as they are the result of a linear combination of rows of the generator matrix G. Moreover, given that the private parity-check matrix $H_{priv}$ has low row and column weight by construction, we have that the aforementioned codewords, i.e., the rows of $\left[0_{r\times (k-r)}{B}^T{A}_r^T\right]$, also have a low weight. This fact may thus allow an attacker to perform a Key Recovery Attack (KRA) retrieving the low-weight codewords and rebuilding $H_{priv}$.

A different attack strategy for the same code families is to try and find codewords in the dual code with respect to the one represented by the parity check matrix $H_{priv}$. Such a code, by definition, sees $H_{priv}$ as a valid generator matrix, and thus makes it possible to directly reconstruct $H_{priv}$ solving r instances of Codeword Finding Problem (CFP) to obtain the r instances of $H_{priv}$. Solving the Codeword Finding Problem (CFP) on the dual code implies that Algorithm 3 is called considering the aforementioned G matrix as a parity check matrix. Thus, if we denote with $C_{ISD}(n,r,w)$ the complexity of solving Codeword Finding Problem (CFP) on the code described by $H_{priv}$, solving the Codeword Finding Problem (CFP) on the dual code, will have a complexity of $C_{ISD}(n,k,w^{\prime })$, where $w^{\prime }$ is the weight of the codeword of the dual code. Whether this strategy or the one of solving the Codeword Finding Problem (CFP) on the primal code is more advantageous depending on the code rate and the values of w and $w^{\prime }$.

The algorithm proposed by Leon in [12], reported in Algorithm 4, improves the Lee and Brickell’s Information Set Decoding (ISD) assuming that the contribution to the value of the first ℓ bits of the syndrome $\overline{s}$, ${\overline{s}}_{\mathrm{up}}$, comes only from columns in V, i.e., there is a run of zeroes of length ℓ leading the final r bits of the permuted error vector $\widehat{e}$, i.e., $\widehat{e}=\left[{\widehat{e}}_1{0}_{1\times \ell }{\widehat{e}}_2\right]$, where ${\widehat{e}}_1$ is k bits long and ${\widehat{e}}_2$ is $r-\ell$ bits long. We thus have that the expected situation after the permutation and RREF computation is where ${\widehat{e}}_{\mathrm{down}}$ is assumed to have a run of ℓ zeroes in its first bits. Such an assumption will clearly reduce the success rate of an iteration, as not all the randomly chosen permutations will select columns having this property. However, making such an assumption allows performing a preliminary check of the value of the sum of the ℓ topmost bits only of each column of V. Indeed, such a sum should match the value of the corresponding ℓ topmost bits of $\overline{s}$, ${\overline{s}}_{\mathrm{up}}$, because the ℓ leading null bits in ${\widehat{e}}_{\mathrm{down}}$ in turn nullify the contribution of the columns in the topmost ℓ rows $I_{\mathrm{up}}$ of the identity matrix. Such a check (Line 5 in Algorithm 4) allows discarding a selection of the p columns from the ones of V, earlier, saving  addition instructions with respect to a full column check. The length ℓ of the run of zeroes should be picked so that the trade-off between the reduction in success probability is compensated by the gain in the speed of a single iteration.

Stern’s algorithm, introduced in [13], improves Leon’s (Algorithm 4) by employing a meet-in-the-middle strategy to find which set of size p, containing ℓ bit portions of columns of V, adds up to the first ℓ bits of the syndrome $\overline{s}$. For the sake of clarity, consider V as $V=\left[\begin{array}{c}{V}_{\mathrm{up}}\\ V_{\mathrm{down}}\end{array}\right]=\left[\begin{array}{ccc}{v}_{\mathrm{up}0}& \dots & v_{\mathrm{up}k-1}\\ v_{\mathrm{down}0}& \dots & v_{\mathrm{down}k-1}\end{array}\right]$ where $v_{\mathrm{up}\mathrm{i}}$ are ℓ-bit column vectors, and  $v_{\mathrm{down}i}$ are $(r-\ell )$-bit column vectors, and the transformed syndrome $\overline{s}$ as $\overline{s}=\left[\begin{array}{c}{\overline{s}}_{\mathrm{up}}\\ {\overline{s}}_{\mathrm{down}}\end{array}\right]$.

Stern’s strategy splits the p-sized set ${\mathcal{I}}^{\prime }$ of indexes of the columns of $V_{\mathrm{up}}$, which should add up to ${\overline{s}}_{\mathrm{up}}$, into two $\frac{p}{2}$ sized ones $\mathcal{I}$ and $\mathcal{J}$ (${\mathcal{I}}^{\prime }=\mathcal{I}\cup \mathcal{J}$). Stern’s strategy mandates that all columns indexed by $\mathcal{I}$ should be within the leftmost $\frac{k}{2}$ ones of V, while the ones indexed by $\mathcal{J}$ should be within the rightmost $\frac{k}{2}$ ones. It then exploits the following equation to precompute the value of ${\overline{s}}_{\mathrm{up}}+{\sum }_{i\in \mathcal{I}}{v}_{\mathrm{up}i}$ for all possible $\left(\genfrac{}{}{0pt}{}{k/2}{p/2}\right)$ choices of $\mathcal{I}$, and store them into a lookup table $\mathcal{L}$, together with the corresponding choice of $\mathcal{I}$. The algorithm then enumerates all possible $\frac{p}{2}$ sized sets of indexes $\mathcal{J}$, computing for each one ${\sum }_{j\in \mathcal{J}}{v}_{\mathrm{up}j}$, and checking if the result is present in $\mathcal{L}$. If this is the case, the algorithm has found a candidate pair $(\mathcal{I},\mathcal{J})$ for which ${\sum }_{i\in \mathcal{I}\cup \mathcal{J}}{v}_{\mathrm{up}i}={\overline{s}}_{\mathrm{up}}$ holds, and thus proceeds to check if ${\sum }_{i\in \mathcal{I}\cup \mathcal{J}}{v}_{\mathrm{down}i}={\overline{s}}_{\mathrm{down}}$. This strategy reduces the cost of computing an iteration quadratically at the price of increasing the number of iterations with respect to Lee and Brickell’s approach, and taking a significant amount of space to store the lookup table $\mathcal{L}$ which contains $\left(\genfrac{}{}{0pt}{}{k/2}{p/2}\right)$ elements. We note that Stern’s variant of the ISD is the first one to exhibit non-polynomial memory requirements, due to the size of the set $\mathcal{I}$, which should be memorized and looked up. Stern’s algorithm is summarized in Algorithm 5.

The aforementioned temporal complexity is obtained assuming a constant memory access cost which, given the exponential amount of memory required is likely to be ignoring a non-negligible amount of time spent to perform memory accesses. Indeed, it is possible to take into account such a time employing a logarithmic memory access cost model. Recalling that the address decoding logic for an n element digital memory of any kind cannot have a circuit depth smaller than ${log}_2\left(n\right)$, we consider that the operations involved in the computation of an iteration will require such an access, in turn obtaining a cost per iteration equal to $c_{iter-logcost}=c_{iter}{log}_2\left(S_{\mathrm{ISD}}(n,r,t,p,\ell )\right)$.

Finiasz and Sendrier in [14] proposed two improvements on Stern’s Information Set Decoding (ISD) algorithm, obtaining Algorithm 6. The first improvement is represented by removing the requirement for the presence of a run of ℓ zeroes in the permuted error vector $\widehat{e}$ and allowing the p error bits to be guessed to be present also in that region of $\widehat{e}$. Such an approach raises the success probability of an iteration. Following the fact that the p positions which should be guessed are picked among the first $k+\ell$ ones of the error vector, Finiasz and Sendrier computed only a partial Reduced Row Echelon Form (RREF) transformation obtaining a smaller, $(r-\ell )\times (r-\ell )$, identity matrix in the lower rightmost portion of $U\widehat{H}=\left[\begin{array}{cc}{V}_{\mathrm{up}}& 0_{\ell \times (r-\ell )}\\ V_{\mathrm{down}}& I_{r-\ell }\end{array}\right]$, and leaving a zero submatrix on top of the identity. As a consequence, the cost of computing such an Reduced Row Echelon Form (RREF) is reduced to

Considering that the invertibility condition is required only for an $(r-\ell )\times (r-\ell )$ submatrix, we  have that for a use of the ISD to solve Syndrome Decoding Problem (SDP), while the last $r^2$ term is not present in case the method is employed to solve the Codeword Finding Problem (CFP).