# A Finite Regime Analysis of Information Set Decoding Algorithms
## 3 A Finite Regime Analysis of Information Set Decoding Techniques
### Lee-Brickell
If the result is found, a further addition of \(p+1\) bit vectors, each one \(r-\ell\) bits long is performed (complexity \(p(r-\ell)\)). This further addition takes place with a probability of \({{{{k}}/{2}}\choose{p/2}}\), as all the possible values for the computed \(\ell\) bit sum are \(2^{\ell}\), and only \({{{k}}/{2}\choose{p/2}}\) are present in \(\mathcal{L}\). The spatial complexity of [PERSON]'s algorithm is the result of adding together the space required for the operations on the \(H\) matrix (i.e., \(rn\)) with the amount of space required by the list \(\mathcal{L}\), which is \({{{k}}/{2}\choose{p/2}}\) elements long. Each element of the list takes \(\frac{p}{2}\log_{2}(\frac{k}{2})\) bits to store the set of indexes, and \(\ell\) bits to store the partial sum, yielding a total spatial cost for the list of \({{{{k}}/{2}}\choose{p/2}}(\frac{p}{2}\log_{2}(\frac{k}{2})+\ell)\) bits. The aforementioned temporal complexity is obtained assuming a constant memory access cost which, given the exponential amount of memory required is likely to be ignoring a non-negligible amount of time spent to perform memory accesses. Indeed, it is possible to take into account such a time employing a logarithmic memory access cost model. Recalling that the address decoding logic for an \(n\) element digital memory of any kind cannot have a circuit depth smaller than \(\log_{2}(n)\), we consider that the operations involved in the computation of an iteration will require such an access, in turn obtaining a cost per iteration equal to \(c_{iter-logcost}=c_{iter}\log_{2}(S_{\text{ISD}}(n,r,t,p,\ell))\). ### [PERSON] and [PERSON] in [14] proposed two improvements on [PERSON]'s Information Set Decoding (ISD) algorithm, obtaining Algorithm 6. The first improvement is represented by removing the requirement for the presence of a run of \(\ell\) zeroes in the permuted error vector \(\widehat{e}\) and allowing the \(p\) error bits to be guessed to be present also in that region of \(\widehat{e}\). Such an approach raises the success probability of an iteration. Following the fact that the \(p\) positions which should be guessed are picked among the first \(k+\ell\) ones of the error vector, [PERSON] and [PERSON] computed only a partial Reduced Row Echelon Form (RREF) transformation obtaining a smaller, \((r-\ell)\times(r-\ell)\), identity matrix in the lower rightmost portion of \(U\widehat{H}= \begin{bmatrix}V_{\text{up}}&0_{\ell\times(r-\ell)}\\ V_{\text{down}}&I_{r-\ell}\end{bmatrix} \), and leaving a zero submatrix on top of the identity. As a consequence, the cost of computing such an Reduced Row Echelon Form (RREF) is reduced to

\[C_{\text{RREF-FS}}(n,r,\ell)=-\frac{\ell^{3}}{3}-\frac{\ell^{2}n}{2}+\frac{\ell^ {2}r}{2}-\frac{3\ell^{2}}{2}-\frac{3\ell n}{2}+\frac{\ell r}{2}-\frac{13\ell}{6 }+\frac{nr^{2}}{2}+\frac{nr}{2}-\frac{r^{3}}{6}+r^{2}+\frac{r}{6}-1.\]
```
0:\(s\): an \(r\)-bit long syndrome (column vector) \(H\): an \(r\times n\) binary parity-check matrix \(t\): the weight of the error vector to be recovered Output:\(e\): an \(n\)-bit binary row error vector s.t. \(He^{T}=s\), with weight\((e)=t\) Data:\(P\): an \(n\times n\) permutation matrix \(\widehat{e}=eP\): the error vector permuted by \(P\) \(p\): the weight of the first \(k\) bits of \(\widehat{e}\), \(0\leq p\leq t\), \(\ell\): a free parameter \(0\leq\ell\leq r-(t-p)\) \(s\): an \(r\)-bit long binary column vector, equal to the syndrome of \(e\) through \( \begin{bmatrix}V_{\text{up}}&0_{\ell\times(r-\ell)}\\ V_{\text{down}}&I_{r-\ell}\end{bmatrix} \), \(s= \begin{bmatrix}s_{\text{up}}\\ s_{\text{down}}\end{bmatrix} \) \(V\): an \(r\times(k+\ell)\) binary matrix \(V= \begin{bmatrix}v_{0}&\dots&v_{k-1}\end{bmatrix} = \begin{bmatrix}V_{\text{up} }\\ V_{\text{down}}\end{bmatrix} = \begin{bmatrix}v_{\text{up}\ 0}&\dots&v_{\text{up}\ k+\ell-1}\\ v_{\text{down}\ 0}&\dots&v_{\text{down}\ k+\ell-1}\end{bmatrix}