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

and exploiting their form to build two lists of candidate values for \(\mathcal{I}\) and \(\mathcal{J}\), \(\mathcal{I}\) and \(\mathcal{J}\), such that for the elements of the first list, it holds that \(0_{\ell_{2}\times 1}+\sum_{i\in\mathcal{I}_{1}}\tilde{v}_{\text{up}-\ell_{2}\ i}= \sum_{i\in\mathcal{I}_{2}}\tilde{v}_{\text{up}-\ell_{2}\ i}\), and for the elements of the second list it holds that \(\tilde{s}_{\text{up}-\ell_{2}}+\sum_{j\in\mathcal{J}_{1}}\tilde{v}_{\text{up} -\ell_{2}\ j}=\sum_{j\in\mathcal{J}_{2}}\tilde{v}_{\text{up}-\ell_{2}\ j}\). We note that, through a straightforward implementation optimization, the one employed in [PERSON]'s algorithm, only the first list needs to be materialized (appearing as \(\mathcal{L}\) in Algorithm 7). The second observation made in the MMT algorithm relates to the possibility of reducing the size of the list involved in [PERSON]'s algorithm to compute the value of the sought error vector via a meet-in-the-middle strategy. The observation relies on the fact that it is possible to obtain the first \(k+\ell\) bits of the permuted error vector \(\widehat{\epsilon}\), \(\widehat{\epsilon}[k+\ell]\) as the sums of two \(k+\ell\) long bit vectors, \(\widehat{\epsilon}_{1}\), \(\widehat{\epsilon}_{2}\) with weight \(\frac{p}{2}\) each. [PERSON]'s algorithm limits the positions of the ones in \(\widehat{\epsilon}_{1}\), \(\widehat{\epsilon}_{2}\) to be in the first half of the bits for \(\widehat{\epsilon}_{1}\) and in the second half for \(\widehat{\epsilon}_{2}\), yielding a single valid pair \(\widehat{\epsilon}_{1}\), \(\widehat{\epsilon}_{2}\) for a given \(\widehat{\epsilon}\). By contrast May-Meurer-Thomae does not constrain the positions of the two sets of \(\frac{p}{2}\) positions to be picked from different halves of the \(k+\ell\) region of the error vector, but instead it only constrains the choice to non-overlapping positions. In such a fashion, considering the correct guess of \(p\) positions, we have that they can be split into the two \(\frac{p}{2}\) sets in \(\binom{p}{p/2}\) possible valid ways, in turn increasing the likelihood of a correct guess. If this choice is made, it is possible to reduce the size of the lists employed to compute the man in the middle approach by a factor of \(\binom{p}{p/2}\), while retaining (on average), at least a solution. To this end, the authors suggested picking the value of \(l_{2}\) as \(\binom{\frac{k+\ell}{2}}{\frac{\ell}{4}}\), in a way to reduce the size of the lists by the proper factor. **Proposition 6** (Computational complexity of Algorithm 7). : _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 7 requires three additional parameters \(0\leq p\leq t\), \(\ell_{1}\) and \(\ell_{2}\) such that \(\ell_{1}+\ell_{2}=\ell,0\leq\ell\leq(k-p)\)._

_The time complexity of May-Meurer-Thomae is_

\[ \begin{array}{l}C_{\text{ISD}}(n,r,t,p,\ell_{1},\ell_{2})=\\ \frac{\binom{n}{t}}{\binom{k+\ell}{p}(t-\ell)}\begin{pmatrix}C_{\text{IS}- \text{FS}}(n,r,\ell)+(\binom{k+\ell/2}{p/4})\frac{p}{2}\ell_{2}+\min\left(( \binom{(k+\ell)/2}{p/2}),\frac{(\binom{k+\ell/2}{p/2})}{p/2}\right)\cdot \left(\frac{p}{4}\ell_{2}+\frac{(\binom{k+\ell/2}{p/4})}{2^{2}}\frac{p}{2} \ell_{1}\right)+\\ +(\binom{(k+\ell)/2}{p/4})\frac{p}{4}\ell_{2}+(\frac{k+\ell/2}{p/4})\left( \frac{p}{4}\ell_{2}+\frac{(\binom{k+\ell/2}{p/4})}{2^{2}}\left(\frac{p}{2}\ell_ {1}+\frac{(\binom{k+\ell}{p/2})(\frac{p}{p/2})}{2^{2}}p(r-\ell)\right)\right) \end{pmatrix}.\end{array} \]

_The spatial complexity of May-Meurer-Thomae is_

\[ \begin{array}{l}S_{\text{ISD}}(n,r,t,p,\ell)=\\ \mathcal{O}\left(rn+(\binom{(k+\ell)/2}{p/4})(\frac{p}{4}\log_{2}(\frac{k+l}{2} )+\ell_{2})+\min\left((\binom{(k+\ell)/2}{p/4},\frac{(\binom{k+\ell/2}{p/2})}{ (\frac{p}{p/2})}\right)(\frac{p}{2}\log_{2}(k+\ell)+\ell)\right).\end{array} \]

**Proof.