# A Finite Regime Analysis of Information Set Decoding Algorithms
## 3 A Finite Regime Analysis of Information Set Decoding Techniques
### Lee-Brickell
We do so following the same method employed for the aforementioned variants, i.e., augmenting the cost of the iteration accordingly. ### Speedups in ISD Algorithms Due to Quasi-Cyclic Codes

A common choice to reduce the size of the keys in a McEliece or Niederreiter cryptosystem is to employ a so-called _quasi-cyclic_ code. Such a code is characterized by a parity-check matrix composed by circulant block matrices, i.e., matrices where all the rows are obtained as a cyclic shift of the first one. It is possible to exploit such a structure to provide a polynomial speedup factor to both the solution of Codeword Finding Problem (CFP) and Syndrome Decoding Problem (SDP). The speedup in the solution of the Codeword Finding Problem (CFP) can be derived in a straightforward fashion observing that, in the case of both the Codeword Finding Problem (CFP) against the primal and the one against the dual code, for each codeword to be found in a quasi cyclic code with \(p\) sized circulant blocks, \(p-1\) more codewords can be derived simply as a block-wise circulant shift of the first one. As a consequence, for a given codeword with weight \(w\) sought by the algorithm, it is guaranteed that at least \(p\) many of them are present in the code. Thus, in this case. the success probability of each iteration can be obtained as \(1-(1-\Pr_{\mathrm{succ}})^{p}\); when \(p\Pr_{\mathrm{succ}}\ll 1\), this in turn implies that the probability of success approximately grows by a factor \(p\), in turn speeding up any ISD by the same factor. An analogous line of reasoning leads to exploit the Decoding One Out of Many (DOOM) algorithm proposed by [PERSON] in [38] to speed up the solution of the Syndrome Decoding Problem (SDP). Decoding One Out of Many (DOOM) relies on the fact that a set of syndromes \(S\) through the same parity check matrix are provided to the attacker, and he attempts at decoding at least one of them. In case of a quasi cyclic code, cyclically shifting the syndrome yields a different, valid syndrome, and a predictable cyclic shift on the corresponding (unknown) error vector. It is therefore possible for an attacker to derive \(p\) different syndromes, starting from one and, in case one of them is successfully decoded, no matter which one, he will be able to reconstruct the sought error vector. Essentially, Decoding One Out of Many (DOOM) performs multiple ISD instances, taking care of duplicating only the checks which involve the syndrome, thus pooling the considerable amount of effort required in the rest of the iteration. The overall speedup achieved by Decoding One Out of Many (DOOM) for a quasi cyclic code with block size \(p\) is \(\sqrt{p}\). ```
Input:\(s\): an \(r\)-bit long syndrome (column vector) \(H\): an \(r\times n\) binary parity-check matrix \(t\): the weight of the error vector to be recovered Output:\(e\): an \(n\)-bit binary row error vector s.t. \(He^{T}=s\), with weight\((e)=t\) Data:\(P\): an \(n\times n\) permutation matrix \(\widehat{e}=eP\): the error vector permuted by \(P\) \(p\): the weight of the first \(k\) bits of \(\widehat{e}\), \(0\leq p\leq t\) \(\ell\): a free parameter \(0\leq\ell\leq r-(t-p)\) \(\widehat{s}\): an \(r\)-bit long binary column vector, equal to the syndrome of \(e\) through \( \begin{bmatrix}V_{\text{up}}&0_{\ell\times(r-\ell)}\\ V_{\text{down}}&I_{r-\ell}\end{bmatrix} \), \(s= \begin{bmatrix}S_{\text{up}}\\ S_{\text{down}}\end{bmatrix} \) \(V\): an \(r\times(k+\ell)\) binary matrix \(V= \begin{bmatrix}v_{0}&\dots&v_{k-1}\end{bmatrix} = \begin{bmatrix}V_{\text{up}} \\ V_{\text{down}}\end{bmatrix} = \begin{bmatrix}v_{\text{up}}&0&\dots&v_{\text{up} \,k+\ell-1}\\ v_{\text{down}}&0&\dots&v_{\text{down}\,k+\ell-1}\end{bmatrix}