# A Finite Regime Analysis of Information Set Decoding Algorithms
## 3 A Finite Regime Analysis of Information Set Decoding Techniques
### Lee-Brickell
: _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 4 requires two additional parameters \(0\leq p\leq t\), \(0\leq\ell\leq r\). The time complexity of Algorithm 4 can be computed starting from the probability of success \(\textsc{Pr}_{\text{succ}}\) of a single iteration of the loop at Lines \(1\)-\(11\) and the computational requirements of executing the loop body \(c_{\text{iter}}\). In particular, the time complexity is_

\[C_{\text{ISD}}(n,r,t,p,\ell)=\frac{1}{\textsc{Pr}_{\text{succ}}}c_{\text{iter }}=\frac{\binom{n}{t}}{\binom{k}{p}(\binom{r-\ell}{t-p})}\left(C_{\text{IS}} (n,r)+\binom{k}{p}\left(C_{\text{IntToComb}}+p\ell+\frac{\binom{k}{p}}{2\ell} p(r-\ell)\right)\right),\]

_where \(C_{\text{IS}}(n,r)\) is as in Equation (6) and \(C_{\text{IntToComb}}=\mathcal{O}((2k-p)(\log\binom{k}{p})^{2})\) is the cost of decoding an integer into its combinatics representation, i.e., finding the corresponding combination among all the \(\binom{k}{p}\) 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}}(r,n)=\mathcal{O}(rn)\)._

**Proof. ** The success probability of an iteration of [PERSON]'s algorithm follows the same line of reasoning of [PERSON]'s and [PERSON] and [PERSON]'s, dividing the number of admissible permuted error vectors \({k\choose p}({{t-\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 4-10 will perform \({k\choose p}\) iterations, where \(p+1\) vectors of length \(\ell\) are added together (complexity \(p\ell\)), and, if the result is zero, a further addition of \(p+1\) bit vectors, each one of length \(r-\ell\) has to be performed (complexity \(p(r-\ell)\)). This further addition takes place with a probability of \({k\choose p}\over 2^{\ell}\), as all possible values for \(\tilde{s}_{\text{up}}\) are \(2^{\ell}\), and only \({k\choose p}\) attempts at hitting the correct one are made, thus yielding the correct complexity, under the assumption that the sums of \(\ell\) bit vectors are independent and uniformly distributed over all the \(\ell\) bit strings. \(\square\)

### [PERSON]'s algorithm, introduced in [13], improves [PERSON]'s (Algorithm 4) by employing a meet-in-the-middle strategy to find which set of size \(p\), containing \(\ell\) bit portions of columns of \(V\), adds up to the first \(\ell\) bits of the syndrome \(\tilde{s}\). For the sake of clarity, consider \(V\) as \(V= \begin{bmatrix}V_{\text{up}}\\ V_{\text{down}}\end{bmatrix} = \begin{bmatrix}v_{\text{up}\ 0}&\ldots&v_{\text{up}\ k-1} \\ v_{\text{down}\ 0}&\ldots&v_{\text{down}\ k-1}\end{bmatrix} \) where \(v_{\text{up}\ i}\) are \(\ell\)-bit column vectors, and \(v_{\text{down}\ i}\) are \((r-\ell)\)-bit column vectors, and the transformed syndrome \(\tilde{s}\) as \(\tilde{s}= \begin{bmatrix}\tilde{s}_{\text{up}}\\ \tilde{s}_{\text{down}}\end{bmatrix} \). [PERSON]'s strategy splits the \(p\)-sized set \(\mathcal{I}^{\prime}\) of indexes of the columns of \(V_{\text{up}}\), which should add up to \(\tilde{s}_{\text{up}}\), into two \({p\over 2}\) sized ones \(\mathcal{I}\) and \(\mathcal{J}\) (\(\mathcal{I}^{\prime}=\mathcal{I}\cup\mathcal{J}\)). [PERSON]'s strategy mandates that all columns indexed by \(\mathcal{I}\) should be within the leftmost \({k\over 2}\) ones of \(V\), while the ones indexed by \(\mathcal{J}\) should be within the rightmost \({k\over 2}\) ones.