# 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+\ell}{2}-1\), and \(a_{\mathcal{I}}\) an \(\ell\)-bit binary column vector repeat \(\langle P_{r} \begin{bmatrix}V_{\text{up}}&0_{\ell\times(r-\ell)}\\ V_{\text{down}}&I_{r-\ell}\end{bmatrix} ,s\rangle\leftarrow\textsc{Isextract-FS}(H,s,\ell)\) \(\mathcal{L}\leftarrow\varnothing\) for\(j\gets 1\)to\( \begin{smallmatrix}(k+\ell)/2\\ p/2\end{smallmatrix} \)do \(\mathcal{I}\leftarrow\textsc{IntegerToCombination}(j)\)//\(\mathcal{I}\)is a set of \(p/2\) distinct int.s in \(\{0,\dots,\frac{k+\ell}{2}-1\}\) \(\mathcal{L}\leftarrow\mathcal{L}\cup\{(\mathcal{I},\widehat{s}_{\text{up}}+ \sum_{i\in\mathcal{I}}v_{\text{up}\ i})\}\) for\(j\gets 1\)to\( \begin{smallmatrix}(k+\ell)/2\\ p/2\end{smallmatrix} \)do \(\mathcal{J}\leftarrow\textsc{IntegerToCombination}(j)\)//\(\mathcal{J}\)is a set of \(p/2\) distinct int.s in \(\{0,\dots,\frac{k+\ell}{2}-1\}\) if\((\mathcal{I},\sum_{i\in\mathcal{J}}v_{\text{up}\ i+(k+\ell)/2})\in\mathcal{L}\)then ifweight\((\widehat{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)}\)\((\widehat{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+\ell)/2}\,1\,0_{1\times(r+(k+ \ell)/2-1-i)}]\) break untilweight\((\widehat{e})=t\) return\(\widehat{e}P^{T}\)
```
**Algorithm 6**Syndrome decoding formulation of Finiasz-Sendrier ISD. Considering that the invertibility condition is required only for an \((r-\ell)\times(r-\ell)\) submatrix, we have that

\[C_{\text{IS-FS}}(n,r,\ell)=\frac{1}{\prod_{i=1}^{r-\ell}(1-2^{-i})}\ C_{\text{ RREF}}(n,r,\ell)+r^{2}\]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). **Proposition 5** (Computational complexity of Algorithm 6). : _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 6 also requires two additional parameters \(0\leq p\leq t\), \(0\leq\ell\leq(k-p)\)._

_The time complexity of Algorithm 6 can be computed starting from the probability of success \(\Pr_{\mathrm{succ}}\) of a single iteration of the loop at Lines \(1\)-\(17\) and the computational requirements of executing the loop body \(c_{\mathrm{iter}}\). In particular, the time complexity is_

\[C_{\mathrm{ISD}}(n,r,t,p,\ell)=\frac{1}{\Pr_{\mathrm{succ}}}c_{ \mathrm{iter}} = \frac{\binom{(k)}{p/2}}{\binom{(k+\ell)/2}{p/2}\binom{(r-\ell)}{( t-p)}}\left(C_{\mathrm{IS-FS}}(n,r,\ell)\right.\] \[+ \left.(\genfrac{}{}{0.0 pt}{}{k+\ell/2}{p/2})\frac{p}{2}\ell+( \genfrac{}{}{0.0 pt}{}{k+\ell/2}{p/2})\left(C_{\mathrm{InfoComb}}+\frac{p}{2} \ell+\frac{(\genfrac{}{}{0.0 pt}{}{k+\ell/2}{p/2}}{2^{\ell}}p(r-\ell)\right) \right),\]

_where \(C_{\mathrm{InfoComb}}=\mathcal{O}((2k-p)(\log\binom{k}{p})^{2})\) is the cost of decoding an integer into its combinadics representation, i.e., finding the corresponding combination among all the \(\binom{(k+\ell)/2}{p/2}\) ones. Note that, if the value of \(p\) is fixed, it is possible to avoid \(C_{\mathrm{InitToComb}}\), specializing the algorithm with a \(p\)-deep loop nest to generate the combinations. The spatial complexity is \(S_{\mathrm{ISD}}(n,r,t,p,\ell)=\mathcal{O}\left(rn+(\genfrac{}{}{0.0 pt}{}{k+ \ell/2}{p/2})(\frac{p}{2}\log_{2}(\frac{k+l}{2})+\ell)\right).\)_

With a line of reasoning analogous to [PERSON]'s ISD, we consider the complexity of [PERSON] and [PERSON]'s ISD with a logarithmic memory access cost, multiplying the cost of the iteration by the binary logarithm of the size of the required memory.