# A Finite Regime Analysis of Information Set Decoding Algorithms
## 3 A Finite Regime Analysis of Information Set Decoding Techniques
### Lee-Brickell
### Leon

The algorithm proposed by [PERSON] in Leon (1999), reported in Algorithm 4, improves the [PERSON] and Brickell's Information Set Decoding (ISD) assuming that the contribution to the value of the first \(\ell\) bits of the syndrome \(\bar{s},\bar{s}_{\mathrm{up}}\), comes only from columns in \(V\), i.e., there is a run of zeroes of length \(\ell\) leading the final \(r\) bits of the permuted error vector \(\widehat{e}\), i.e., \(\widehat{e}=[\widehat{e}_{1}0_{1\times(\widehat{e}_{2})}]\), where \(\widehat{e}_{1}\) is \(k\) bits long and \(\widehat{e}_{2}\) is \(r-\ell\) bits long. We thus have that the expected situation after the permutation and RREF computation is

\[\hat{H}\widehat{e}^{T}= \begin{bmatrix}V_{\mathrm{up}}&I_{\mathrm{up}}\\ V_{\mathrm{down}}&I_{\mathrm{down}}\end{bmatrix}\begin{bmatrix}\widehat{e}_{1} ^{T}\\ 0_{1\times\ell}^{T}\\ \widehat{e}_{\mathrm{down}}^{T}\end{bmatrix} = \begin{bmatrix}\bar{s}_{ \mathrm{up}}\\ \bar{s}_{\mathrm{down}}\end{bmatrix} =\bar{s}\]

where \(\widehat{e}_{\mathrm{down}}\) is assumed to have a run of \(\ell\) zeroes in its first bits. Such an assumption will clearly reduce the success rate of an iteration, as not all the randomly chosen permutations will select columns having this property. However, making such an assumption allows performing a preliminary check of the value of the sum of the \(\ell\) topmost bits only of each column of \(V\). Indeed, such a sum should match the value of the corresponding \(\ell\) topmost bits of \(\bar{s}\), \(s_{\mathrm{up}}\), because the \(\ell\) leading null bits in \(\widehat{e}_{\mathrm{down}}\) in turn nullify the contribution of the columns in the topmost \(\ell\) rows \(I_{\mathrm{up}}\) of the identity matrix. Such a check (Line 5 in Algorithm 4) allows discarding a selection of the \(p\) columns from the ones of \(V\), earlier, saving addition instructions with respect to a full column check. The length \(\ell\) of the run of zeroes should be picked so that the trade-off between the reduction in success probability is compensated by the gain in the speed of a single iteration. ```
Input:\(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 \(\textsc{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\): length of the run of zeroes in \(\widehat{e}=[\widehat{e}_{1\times k}^{\prime}\,0_{1\times\ell}\,\widehat{e}_{ 1\times r-\ell}^{\prime}]\) \(\widehat{s}\): an \(r\)-bit long binary column vector, equal to the syndrome of \(e\) through \([V\,I_{r}]\), \(\widehat{s}= \begin{bmatrix}\tilde{s}_{\text{up}}\\ \tilde{s}_{\text{down}}\end{bmatrix} \) \(V\): an \(r\times k\) binary matrix \(V= \begin{bmatrix}v_{0}&\ldots&v_{k-1}\end{bmatrix} = \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} \)
1 repeat\(\langle P_{r},[V\,I_{r}],\widehat{s}\rangle\leftarrow\textsc{IS Extract}(H,s)\)for\(j\gets 1\)to\(\binom{k}{p}\)do \(\mathcal{I}\leftarrow\textsc{IntegerToCombination}(j)\)// \(\mathcal{I}\) is a set of \(p\) distinct integers in \(\{0,\ldots,k-1\}\) if\(\textsc{weight}(\tilde{s}_{\text{up}}+\sum_{i\in\mathcal{I}}v_{\text{up}\;i})=0\)then if\(\textsc{weight}(\tilde{s}_{\text{down}}+\sum_{i\in\mathcal{I}}v_{\text{down}\;i})=t-p\)then \(\widehat{e}\leftarrow[0_{1\times(k+\ell)}\,(\tilde{s}_{\text{down}}+\sum_{i \in\mathcal{I}}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-\ell)}]\)breakbreakbreak until\(\widehat{e})=t\) return\(\widehat{e}p^{T}\)
```
**Algorithm 4**Syndrome decoding formulation of [PERSON]'s ISD. **Proposition 3** (Computational complexity of Algorithm 4).