# 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.
We thus have that the probability of having all the rows independent from one another is \(\prod_{i=1}^{r}(1-\frac{2^{i-1}}{2^{r}})=\prod_{i=1}^{r}(1-\frac{1}{2^{r}})\). We thus have that the column permutation (Line 4), with computational complexity \(rn\) (which can be lowered to \(n\) keeping only the permuted column positions) and the Reduced Row Echelon Form (RREF) transformation (Line 5), with cost \(\mathcal{O}\left(\frac{nr^{2}}{2}+\frac{nr}{2}-\frac{r^{3}}{6}+r^{2}+\frac{r} {6}-1\right)\) have to be repeated \(\frac{1}{\prod_{i=1}^{r}(1-2^{-i})}\) times, yielding the first addend of the computational cost \(C_{\text{IS}}(n,r)\). The cost \(C_{\text{RREF}}(n,r)\) is derived considering the Reduced Row Echelon Form (RREF) as an iterative algorithm performing as many iterations as the rank of the identity matrix in the result (i.e., \(r\) in this case). Each iteration \(0\leq i\leq r-2\) proceeds to find a pivot, taking \(\mathcal{O}(r-i)\), swaps it with the \((r-i)\)th row in \(\mathcal{O}(n)\) and proceeds to add the pivot to all the remaining \(r-i-1\) rows which have a one in the \((n-i)\)th column. The total cost is  
\[C_{\text{RREF}}(n,r)=\mathcal{O}\left(\sum_{i=0}^{r-2}(r-i)+rn+\sum_{i=0}^{r- 2}(r-1-i)(n-i)\right)=\mathcal{O}\left(\frac{nr^{2}}{2}+\frac{nr}{2}-\frac{r^ {3}}{6}+r^{2}+\frac{r}{6}-1\right).\]  
The second addend of the cost \(C_{\text{IS}}(n,r)\) is constituted by the computational complexity of computing \(\tilde{s}=Us\), which is \(r^{2}\). The total cost of computing an iteration \(c_{\text{iter}}\) is the sum of \(C_{\text{IS}}(n,r)\) and the cost of building \(\widehat{e}\), i.e., \(\mathcal{O}(n)\). \(\Pr_{\text{succ}}\) is obtained as the number of permuted error vectors with the error-affected positions such that they are fitting the hypotheses made by the algorithm, divided by the number of all the possible error vectors. This fact holds for all ISD algorithms. In the case of [PERSON]'s ISD, the permuted error vectors admissible by the hypotheses are \((^{\prime}_{t})\), as all the error-affected positions should be within the last \(r\) bits of the permuted error vectors, while the number of error vectors is \((^{n}_{t})\). For the sake of clarity, from now on, we denote as \(\text{ISextract}(H,s)\) the procedure computing \(\langle P,[V\;I_{r}],\tilde{s}\rangle\), performed on Lines 2-7 of Algorithm 1, with computational time complexity \(C_{\text{IS}}(n,r)\) and space complexity \(\mathcal{O}(rn)\).