# A Finite Regime Analysis of Information Set Decoding Algorithms
## 3 A Finite Regime Analysis of Information Set Decoding Techniques
### Lee-Brickell
In the complete algorithm, the aforementioned line of reasoning is applied twice, as the list-building strategy is recursively applied, leading to two different reduction factors depending on the recursion depth itself. We now come to the second improvement of the BJMM algorithm, the recursive application of the meet-in-the-middle strategy employed by all the ISDs since [PERSON]'s. [PERSON]'s meet-in-the-middle approach starts from rewriting \(V_{\text{up}[l]}e_{1}+V_{\text{up}[l]}e_{2}=s_{\text{up}}\) as \(V_{\text{up}[l]}e_{1}=V_{\text{up}[l]}e_{2}+s_{\text{up}}\). The original BJMM proceeds to build two lists of pairs. The first list contains, for all possible \(e_{1}\), the pairs \((V_{\text{up}[l]}e_{1},e_{1})\). The second list contains, for all possible \(e_{2}\), the pairs \((V_{\text{up}[l]}e_{2}+s_{\text{up}},e_{2})\). The BJMM algorithm sorts lexicographically the two lists on the first elements of the pairs and then checks for the matching pairs in essentially linear time in the length of the lists. We note that a more efficient (memory saving) way of performing the same computation involves inserting in a (open hash) hashmap which employs as the key \(V_{\text{up}[l]}e_{1}\) for the value \(e_{1}\). Subsequently, computing on the fly \(V_{\text{up}[l]}e_{2}+s_{\text{up}}\), and looking it up in the hashmap, yields all the matching pairs for \(e_{2}\). Let \(N\) be the number of possible pairs and \(M\) the number of matching pairs, the original strategy requires \(\mathcal{O}(2\sqrt{N}+2\sqrt{N}\log_{2}2\sqrt{N}+M)\) vector sized operations, while the modified one requires \(\mathcal{O}(\sqrt{N}+\sqrt{N}+M)\). The BJMM algorithm employs the meet-in-the-middle strategy to generate the values for the candidate vectors \(e\) more than once. In particular, a candidate for \(e\), \(e^{(0)}\), weight \(p\), length \(k+\ell\)is generated from two vectors \(e_{1}^{(1)},e_{2}^{(1)}\), weight \(p_{1}=\frac{p}{2}+\varepsilon_{1}\), length \(k+\ell\). The \(e_{1}^{(1)},e_{2}^{(1)}\) vectors are in turn generated by pairs \(e_{1}^{(2)},e_{2}^{(2)}\) and \(e_{3}^{(2)},e_{4}^{(2)}\), which all have weight \(p_{2}=p_{1}+\varepsilon_{2}\). Finally, \(e_{1}^{(2)},e_{2}^{(2)},e_{3}^{(2)},e_{4}^{(2)}\), are generated by pairs \(e_{1+2i}^{(3)},e_{2+2i}^{(3)},i\in\{0,1,2,3\}\), which have length \(k+\ell\), and weight \(p_{3}=\frac{p_{2}}{2}+0\), i.e., no extra ones which will cancel out are allowed when generating \(e^{(2)}\)'s. In adopting this approach, two issues must be coped with: no overlapping positions for the ones should be present between any \(e_{1+2i}^{(3)},e_{2+2i}^{(3)}\) pair, and the values all the \(V_{\text{up}[l]}e_{i}^{(1)}\), \(V_{\text{up}[l]}e_{i}^{(2)}\), \(V_{\text{up}[l]}e^{(1)}\) are matched against should be unrelated, so that the sampling of pairs during the merge action of two lists is indeed picking items independently from another list merger on the same level. This allows a list merger at a lower level to consider the elements from above to be picked at random. The first issue is solved picking the positions of the ones for a \(e_{1+2i}^{(3)},e_{2+2i}^{(3)}\) pair from disjoint sets. Since the independence among the inputs of two level-3 list mergers should still hold, a pair of disjoint sets is generated for each level-3 list pair. In other words, for a given \(e_{1+2i}^{(3)},e_{2+2i}^{(3)}\) pair, the position of the ones of \(e_{1+2i}^{(3)}\) belong to a \(\frac{k+\ell}{2}\) sized set which has null intersection with the set of positions from which the ones of \(e_{2+2i}^{(3)}\) are picked. This constraint may cause a given target permuted error not to be representable as a combination of the aforementioned pairs. Indeed, consider the fact that the aforementioned strategy implies that there are possible \(\binom{\frac{k+\ell}{2}}{p_{3}}^{2}\) pairs, while the vectors to be represented are \(\binom{k+\ell}{2p_{3}}\).