# A Finite Regime Analysis of Information Set Decoding Algorithms
## 3 A Finite Regime Analysis of Information Set Decoding Techniques
### [PERSON]'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., \([V\ I_{r}]=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 \(\bar{s}=Us\). If the weight of the permuted error vector \(\widehat{e}\) obtained as \(\widehat{e}=eP=[0_{1\times k}\bar{s}^{T}]\), 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 [PERSON]'s ISD algorithm is provided in Algorithm 1. ```
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 \(\textsc{weight}(e)=t\) Data:\(P\): an \(n\times n\) permutation matrix \(\bar{s}\) an \(r\)-bit long binary column vector \(V\): an \(r\times k\) binary matrix \(V=[v_{0},\ldots,v_{k-1}]\) repeat repeat \(P\leftarrow\textsc{RandomPermutationGen}(n)\) \(\widehat{H}\gets HP\)// the corresponding error vector is \(\widehat{e}=eP\) \(\langle\ U,\ [V|W]\ \rangle\leftarrow\textsc{RedRowEchelonForm}(\widehat{H})\)// \(UH=[V|W_{r\times r}]\) until\(W\
eq I_{r}\) \(\bar{s}\leftarrow Us\) \(\widehat{e}\leftarrow[0_{1\times k}\bar{s}^{T}]\) until\(\textsc{weight}(\widehat{e})=t\) return\(\widehat{e}P^{T}\)
```  
**Algorithm 1**Syndrome decoding formulation of [PERSON]'s ISD. **Proposition 1** (Computational complexity of Algorithm 1). : _Given \(H\), an \(r\times n\) binary parity-check matrix and \(s\), an \(r\)-bit long syndrome (column vector) obtained through \(H\), the complexity for finding the row error vector \(e\) with length \(n\) and weight \(t\) such that \(s=He^{T}\) with Algorithm 1 can be computed starting from the probability of success \(\Pr_{\text{Succ}}\) of a single iteration of the loop at Lines 1-9 and the computational requirements of executing the loop body \(c_{\text{iter}}\). In particular, the time complexity is \(C_{\text{ISD}}(n,r,t)=\frac{1}{\Pr_{\text{Succ}}}c_{\text{iter}}=\frac{\binom{t }{t}}{\binom{t}{t}}\left(C_{\text{IS}}(n,r)+n\right)\), with_  
\[C_{\text{IS}}(n,r) =\frac{1}{\prod_{i=1}^{r}(1-2^{-i})}\;C_{\text{RREF}}(n,r)+r^{2}+n,\] \[C_{\text{RREF}}(n,r) =\mathcal{O}\left(\frac{nr^{2}}{2}+\frac{nr}{2}-\frac{r^{3}}{6}+ r^{2}+\frac{r}{6}-1\right). \tag{6}\]  
_The spatial complexity is \(S_{\text{ISD}}(n,r,t)=\mathcal{O}(rn)\)._  
Proof. : The loop body of Algorithm 1 is dominated by the cost of finding an information set and validating it through checking that the matrix \(W\) is indeed an identity, i.e., that the corresponding submatrix of \(\tilde{H}\) indeed has full rank. Note that, in an \(r\times r\) binary matrix, the first row has a probability of \(\frac{1}{2^{r}}\) of being linearly dependent from itself (i.e., zero); the second row has a probability of \(\frac{2}{2^{r}}\) of being linearly dependent (i.e., zero or equal to the first). With an inductive argument, we obtain that the \(r\)th row has a probability of \(\frac{2^{r-1}}{2^{r}}\) of being linearly dependent from the previous ones.