# A Finite Regime Analysis of Information Set Decoding Algorithms
## 3 A Finite Regime Analysis of Information Set Decoding Techniques
### Lee-Brickell
\) \(\mathcal{L}_{1}^{(e)}\): list of set of indexes \(\mathcal{I}^{(a)}\), at layer \(a\), (root layer: \(a=0\), leaf layer \(a=3\)) \(|\mathcal{I}^{(a)}|=p_{a}=p_{a-1}/2+\varepsilon_{a},a\in 1,2,3\), \(p_{0}=p,\varepsilon_{3}=0\); the elements of \(\mathcal{I}^{(a)}\) are integers in \(\{0,\dots,k+\ell-1\}\) \(\ell_{1},\ell_{2}\): parameters respectively \(0\leq\ell_{2}\leq\ell_{1}\leq\ell\), stated as optimized for \(l_{1}\approx\log_{2}{p\choose r/2}{k+l-p\choose\ell_{1}}\), \(l_{2}\approx\log_{2}{p\choose r_{1}/2}{k+l-p\choose\ell_{2}}\)
1 repeat \(\langle P, \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)\) for\(i\gets 0\)to\(0\)to\(3\)do \(\mathcal{L}_{2}^{(3)}\leftarrow\varnothing\) \(\mathcal{I}_{2i}\leftarrow\textsc{RandomExtract}(k+\ell)\) // populates \(\mathcal{I}_{2i}\) with \(\frac{k+\ell}{2}\) values in \(\{0,\dots,k+\ell-1\}\) \(\mathcal{I}_{2i+1}\leftarrow\{0,\dots,k+\ell-1\}\setminus\mathcal{I}_{2i}\) for\(j\gets 1\)to\((\frac{(k+\ell)/2}{k+\ell})\)do \(\mathcal{I}\leftarrow\textsc{EnumerateComb}(\mathcal{I}_{2i},p_{3j},j)\) // Picks the \(j\)th comb. of \(p_{3}\) items of \(\mathcal{I}_{3i}\) \(\mathcal{L}_{2i}^{(3)}\leftarrow\mathcal{L}_{2i}^{(3)}\cup\{(\mathcal{I}, \sum_{\ell\in\mathcal{I}}v_{\text{up}-\ell_{2}}\,i)\}\) for\(i\gets 0\)to\(1\)do \(x\leftarrow\textsc{RandomBitString}(\ell_{2})+s_{\text{up}-\ell_{2}}\) \(\mathcal{L}_{2i}^{(2)}\leftarrow\varnothing\) foreach\(j\gets 1\)to\((\frac{(k+\ell)/2}{p_{3}})\)do \(\mathcal{J}\leftarrow\textsc{EnumerateComb}(\mathcal{I}_{2i+1},p_{3j},j)\) \(a\gets x+\sum_{j\in\mathcal{J}}v_{\text{up}-\ell_{2}}\) if\((\mathcal{I},a)\in\mathcal{L}_{2i}^{(3)}\)then \(\mathcal{L}_{2i}^{(3)}\leftarrow\mathcal{L}_{2i}^{(2)}\cup\{(T\cup\mathcal{J}, x+\sum_{i\in\mathcal{I}\cup\mathcal{J}}v_{\text{up}-\ell_{1}}\,i)\}\) if\(|\mathcal{L}_{2i}^{(2)}|>(k+\ell_{2}^{(t)}/\left(\binom{p_{1}}{p_{2}}{k+l-p\choose\ell_{2}} \right))\)then break foreach\((\mathcal{I},\mathcal{J})\in\mathcal{L}_{0i}^{(1)}\times\mathcal{L}_{1}^{(1)}\)do if\(\sum_{i\in\mathcal{I}}v_{\text{up}-\ell_{1}}+\sum_{j\in\mathcal{J}}v_{\text{up}j}=\widehat{s} ^{(i)}\)then if\(\text{weight}(\widehat{a}_{\text{down}}\leftarrow\sum_{i\in\mathcal{I}\cup \mathcal{J}}v_{\text{down}})=t-p\)then \(\widehat{e}\leftarrow[0_{1\times(k+\ell)}\,(\widehat{a}_{\text{down}}+\sum_{i \in\mathcal{I}\cup\mathcal{J}}v_{\text{down}\,i})^{T}]\) foreach\(i\in\mathcal{I}\cup\mathcal{J}\)do \(\widehat{e}\leftarrow\widehat{e}+[0_{1\times i}\,1\,0_{1\times(r+k-1-i)}]\) break until weight\((\widehat{e})=t\) return\(\widehat{e}P^{T}\)
```

**Algorithm 8**Syndrome decoding formulation of Becker-Joux-May-Meurer ISD. ### Speedups from Quantum Computing

While there is no known polynomial time algorithm running on a quantum computer able to solve either Syndrome Decoding Problem (SDP) or Codeword Finding Problem (CFP), it is still possible to achieve a significant speedup in the attacks exploiting [PERSON]'s zero-finding algorithm. [PERSON]'s algorithm [PERSON] (1996) finds a zero of an \(n\)-input Boolean function with a computational cost of \(\sqrt{2^{n}}\) function computations, instead of the \(2^{n}\) required with a classical computer. The first instance of a proposed exploitation of [PERSON]'s algorithm to speed up ISDs was made by [PERSON] in [PERSON] (1996), observing that one iteration of [PERSON]'s algorithm can be rewritten as a Boolean function having a zero iff the iteration is successful in finding a valid error vector. The essence of the observation is that the Reduced Row Echelon Form (RREF) computation, and the weight check on the resulting syndrome can be expressed as Boolean functions, and it is straightforward to extend them so that a single bit output indicating the success of the iteration is added.