# A Finite Regime Analysis of Information Set Decoding Algorithms
## 3 A Finite Regime Analysis of Information Set Decoding Techniques
### Lee-Brickell
\) \(\mathcal{L}\): list of pairs \((\mathcal{I},a_{\mathcal{I}})\), with \(\mathcal{I}\) a set of integer indexes between \(0\) and \(\frac{k}{2}-1\), and \(a_{\mathcal{I}}\) an \(\ell\)-bit binary column vector repeat \(\langle P,[V\;I_{r}],\tilde{s}\rangle\leftarrow\textsc{ISextract}(H,s)\) \(\mathcal{L}\leftarrow\varnothing\) for\(j\gets 1\)to\(\binom{k/2}{p/2}\)do \(\mathcal{I}\leftarrow\textsc{IntegerToCombination}(j)\)// \(\mathcal{I}\) is a set of \(p/2\) distinct integers in \(\{0,\ldots,\frac{i}{2}-1\}\) \(\mathcal{L}\leftarrow\mathcal{L}\cup\{(\mathcal{I},\tilde{s}_{\text{up}}+ \sum_{i\in\mathcal{I}}v_{\text{up i}})\}\) for\(j\gets 1\)to\(\binom{k/2}{p/2}\)do \(\mathcal{J}\leftarrow\textsc{IntegerToCombination}(j)\)// \(\mathcal{J}\) is a set of \(p/2\) distinct integers in \(\{0,\ldots,\frac{i}{2}-1\}\) if\((\mathcal{I},\sum_{i\in\mathcal{J}}v_{\text{up i}+k/2})\in\mathcal{L}\)then if\(\textsc{weight}(\tilde{s}_{\text{down}}+\sum_{i\in\mathcal{I}\cup\mathcal{J}}v_{\text{ down}\;i})=t-p\)then \(\widehat{e}\leftarrow[0_{1\times(k+\ell)}\;(\tilde{s}_{\text{down}}+\sum_{i\in \mathcal{I}\cup\mathcal{J}}v_{\text{down}\;i})^{T}]\) foreach\(i\in\mathcal{I}\)do \(\widehat{e}\leftarrow\widehat{e}+[0_{1\times i}\;1\;0_{1\times(r+k-1-i)}]\) foreach\(i\in\mathcal{J}\)do \(\widehat{e}\leftarrow\widehat{e}+[0_{1\times i+k/2}\;1\;0_{1\times(r+k/2-1-i)}]\) break until\(\widehat{e})=t return\(\widehat{e}\widehat{e}^{\text{DT}}\)
```
**Algorithm 5**Syndrome decoding formulation of [PERSON]'s ISD. **Proposition 4** (Computational complexity of Algorithm 5). : _As for Algorithm 4, given \(H\), an \(r\times n\) binary parity-check matrix and \(s\), an \(r\)-bit long syndrome (column vector) obtained through \(H\), finding the row error vector \(e\) with length \(n\) and weight \(t\) such that \(s=He^{T}\) with Algorithm 5 requires two additional parameters \(0\leq p\leq t\), \(0\leq\ell\leq(k-p)\)._The time complexity of Algorithm 5 can be computed starting from the probability of success \(\Pr_{\text{succ}}\) of a single iteration of the loop at Lines \(1\)-\(17\) and the computational requirements of executing the loop body \(c_{\text{iter}}\). In particular, the time complexity is

\[\mathrm{C_{ISD}}(n,r,t,p,\ell) = \frac{1}{\Pr_{\text{succ}}}c_{\text{iter}}\] \[= \frac{{{{{{{{{{t}}}}}}\choose{p/2}}}^{2}}{{{{{r}}}-{{{ {\ell}}}}\choose{t-p}}}}\left(C_{\text{IS}}(n,r)+{{{{k}}/{2}}\choose{p/2}} \frac{p}{2}\ell+{{{{k}}/{2}}\choose{p/2}}(C_{\text{IntToComb}}+\frac{p}{2} \ell+{{{{{k}}/{2}}\choose{p/2}}}p(r-\ell))\right)\]

where \(C_{\text{IS}}(n,r)\) is as in Equation (6) and \(C_{\text{IntToComb}}=\mathcal{O}((2k-p)(\log{{{{k}}}\choose{p}})^{2})\) is the cost of decoding an integer into its combinadics representation, i.e., finding the corresponding combination among all the \({{{{k}}/{2}}\choose{p/2}}\) ones. Note that, if the value of \(p\) is fixed, it is possible to avoid \(C_{\text{IntToComb}}\), specializing the algorithm with a \(p\)-deep loop nest to generate the combinations. The spatial complexity is \(S_{\text{ISD}}(n,r,t,p,\ell)=\mathcal{O}\left(rn+{{{k}}/{2}\choose{p}}(\frac{p }{2}\log_{2}(\frac{k}{2})+\ell)\right)\). Proof. : The success probability of an iteration of [PERSON]'s algorithm follows the same line of reasoning of the previous ones, dividing the number of admissible permuted error vectors \({{{{k}}/{2}}\choose{p/2}}^{2}{{{{r}}}-{{{{\ell}}}\choose{t-p}}}\) by the total one \({{{{n}}\choose{t}}}\). The complexity of a single iteration is obtained considering that the loop at Lines \(5\)-\(7\) will compute \({{{{k}}/{2}}\choose{p/2}}\) additions of \(\frac{p}{2}+1\) vectors, each one \(\ell\) bits in length (complexity \({{{{k}}/{2}}\choose{p/2}}\frac{p}{2}\ell\)). The loop at Lines \(8\)-\(16\) performs \({{{{k}}/{2}}\choose{p/2}}\) iterations, where \(\frac{p}{2}+1\) vectors of length \(\ell\) are added together (complexity \(p\ell\)), and the result is looked up in table \(\mathcal{L}\).