# A Finite Regime Analysis of Information Set Decoding Algorithms
## 3 A Finite Regime Analysis of Information Set Decoding Techniques
### Lee-Brickell
### [PERSON]

The variant of ISD proposed by [PERSON], [PERSON] and [PERSON] in [15] improves [PERSON] and [PERSON]'s variant by introducing two tweaks, resulting in Algorithm 7. The first tweak changes the way in which the \(p\) error positions in the permuted error vector \(\widehat{e}\) are chosen. Instead of splitting them equally as \(\frac{p}{2}\) in the leftmost \(\frac{k+\ell}{2}\) columns and \(\frac{p}{2}\) in the subsequent \(\frac{k+\ell}{2}\) ones, the selection is made picking two disjoint sets of indexes \(\mathcal{I},\mathcal{J}\subset\{0,\ldots,k+\ell-1\}\). Such an approach increases the number of possible permutations which respect this constraint. The second tweak considers \(V_{\mathrm{up}}\) as logically split into two submatrices \(V_{\mathrm{up}}= \begin{bmatrix}V_{\mathrm{up}-\ell_{1}}\\ V_{\mathrm{up}-\ell_{2}}\end{bmatrix} \) dividing it row-wise into two parts, the first one with \(\ell_{1}\) rows and the second one with \(\ell_{2}=\ell-\ell_{1}\) rows. After performing the same partial RREF, as it is done in the [PERSON]'s ISD, we obtain \(U\widehat{H}= \begin{bmatrix}V_{\mathrm{up}-\ell_{1}}&0_{\ell_{1}\times(r- \ell)}\\ V_{\mathrm{up}-\ell_{2}}&0_{\ell_{2}\times(r-\ell)}\\ V_{\mathrm{down}}&I_{r-\ell}\end{bmatrix} \) and the corresponding \(\widehat{s}= \begin{bmatrix}\tilde{s}_{\mathrm{up}-\ell_{1}}\\ \tilde{s}_{\mathrm{up}-\ell_{2}}\\ \tilde{s}_{\mathrm{down}}\end{bmatrix} \). Such a subdivision is employed to further enhance the efficiency of the checks on the columns of \(V\) with respect to the idea of matching bit strings with a precomputed set introduced by [PERSON]. To this end, the sets \(\mathcal{I}\) and \(\mathcal{J}\) are in turn obtained as the disjoint union of a pair subsets with cardinality \(\frac{p}{4}\). Let \(\mathcal{I}\) be \(\mathcal{I}_{1}\cup\mathcal{I}_{2}\) and \(\mathcal{J}\) be \(\mathcal{J}_{1}\cup\mathcal{J}_{2}\). For the sake of simplicity, the disjoint union is realized picking the elements of \(\mathcal{I}_{1},\mathcal{J}_{1}\) in \(\{0,\ldots,\frac{k+\ell}{2}-1\}\) and the ones of \(\mathcal{I}_{2},\mathcal{J}_{2}\) in \(\{\frac{k+\ell}{2},\ldots,k+\ell-1\}\). The May-Meurer-Thomae (MMT) algorithm thus proceeds to exploit a time to memory trade-off deriving from the same equation employed by [PERSON], applying twice the precomputation strategy. The derivation from the test equality on the syndrome is done as follows

\[\tilde{s}_{\mathrm{up}}=\sum_{i\in\mathcal{I}}v_{\mathrm{up}\ i}+\sum_{j\in \mathcal{J}}v_{\mathrm{up}\ j}\Leftrightarrow\]\[ \begin{bmatrix}\tilde{s}_{\text{up}-\ell_{1}}\\ \tilde{s}_{\text{up}-\ell_{2}}\end{bmatrix} = \begin{bmatrix}a_{\text{up}-\ell_{1 }}\\ \tilde{s}_{\text{up}-\ell_{2}}\end{bmatrix} + \begin{bmatrix}b_{\text{up}-\ell_{1 }}\\ 0_{\ell_{2}\times 1}\end{bmatrix} ,\quad \begin{bmatrix}a_{\text{up}-\ell_{1}}\\ \tilde{s}_{\text{up}-\ell_{2}}\end{bmatrix} =\sum_{j\in\mathcal{J}}\begin{bmatrix }v_{\text{up}-\ell_{1}\ j}\\ \tilde{v}_{\text{up}-\ell_{2}\ j}\end{bmatrix},\quad \begin{bmatrix}b_{\text{up }-\ell_{1}}\\ 0_{\ell_{2}\times 1}\end{bmatrix} =\sum_{i\in\mathcal{I}} \begin{bmatrix}v_{\text{up }-\ell_{1}\ i}\\ \tilde{v}_{\text{up}-\ell_{2}\ i}\end{bmatrix} .\]

[PERSON], [PERSON] and [PERSON] exploited the strategy described by [PERSON] to derive candidate values for the elements of \(\mathcal{I}\) and \(\mathcal{J}\), rewriting the last two equalities as

\[ \begin{bmatrix}a_{\text{up}-\ell_{1}}\\ \tilde{s}_{\text{up}-\ell_{2}}\end{bmatrix} +\sum_{j\in\mathcal{J}_{1}} \begin{bmatrix}v_{\text{up}-\ell_{1}\ j}\\ \tilde{v}_{\text{up}-\ell_{2}\ j}\end{bmatrix} =\sum_{j\in\mathcal{J}_{2}} \begin{bmatrix}v_{\text{up}-\ell_{1}\ j}\\ \tilde{v}_{\text{up}-\ell_{2}\ j}\end{bmatrix} ,\quad \begin{bmatrix}b_{\text{ up}-\ell_{1}}\\ 0_{\ell_{2}\times 1}\end{bmatrix} +\sum_{i\in\mathcal{I}_{2}} \begin{bmatrix}v_{ \text{up}-\ell_{1}\ i}\\ \tilde{v}_{\text{up}-\ell_{2}\ i}\end{bmatrix} =\sum_{i\in\mathcal{I}_{2}} \begin{bmatrix}v_{\text{up}-\ell_{1}\ i}\\ \tilde{v}_{\text{up}-\ell_{2}\ i}\end{bmatrix}