# A Finite Regime Analysis of Information Set Decoding Algorithms
## 3 A Finite Regime Analysis of Information Set Decoding Techniques
### Lee-Brickell
We took into account the advantage provided by a quasi cyclic code in both the Syndrome Decoding Problem (SDP) and the Codeword Finding Problem (CFP) solution complexity, reducing it by a factor equal to \(\sqrt{p}\), the square root of the cyclic block size for the Syndrome Decoding Problem (SDP), and \(p\) for the Codeword Finding Problem (CFP), in accordance with the point raised in Section 3.9. Table 4 reports the computational costs of solving both Syndrome Decoding Problem (SDP) and Codeword Finding Problem (CFP) by means of the described variants of the Information Set Decoding (ISD). In addition to the computational complexities obtained, the value of a simple asymptotic cost criterion for the Information Set Decoding (ISD)s, described in [34], is reported. Such a criterion states that the asymptotic complexity of an ISD is \(2^{-\log_{2}(1-\frac{k}{n})t}\), for the case of the use in solving a Syndrome Decoding Problem (SDP). A noteworthy point to observe is that, considering the finite regime value of the complexities, the May-Meurer-Thomae algorithm attains a lower time complexity than the Becker-Joux-May-Meurer algorithm in most cases. Indeed, while the Becker-Joux-May-Meurer Information Set Decoding (ISD) variant has a lower asymptotic cost, considering a worst-case-scenario for the solution of the Syndrome Decoding Problem (SDP), i.e., code rate close to 0.5, and a large enough value for \(n\), a finite regime estimate of its cost reports that employing the May-Meurer-Thomae approach should result in a faster computation. Concerning the space complexities of the approaches with exponential (in the code length \(n\)) space requirements, we report the obtained values in Table 5. We note that the Information Set Decoding (ISD) variants proposed by [PERSON] and [PERSON] and [PERSON] have an overall lower memory consumption that their more advanced counterparts. In particular, the space complexities of the aforementioned variants start as low as 16 Gib for Category 1 parameters, and are thus amenable to an implementation which keeps the entire lists in main memory on a modern desktop. By contrast, the May-Meurer-Thomae and Becker-Joux-May-Meurer Information Set Decoding (ISD) variants require a significantly higher amount of memory, with the latter being less demanding than the former in all cases but the one of LEDAcrypt in its \(n_{0}=2\) parameterization for extremely long term keys (LEDAcrypt-XT). In all cases, the space complexities of May-Meurer-Thomae and Becker-Joux-May-Meurer exceed \(2^{50}\), pointing strongly to the need of a significant amount of mass storage to implement a practical attack. Such a requirement is even more stringent in the case of higher security levels, where the memory requirements exceed \(2^{100}\) for most parameter choices. \begin{table}
\begin{tabular}{l c} \hline \hline
**ISD Variant** & **Parameter Range** \\ \hline Prange [10] & none \\ [PERSON] [11] & \(1\leq p\leq 12\) (\(p=2\) is asymp. optimal) \\ [PERSON] [12] & \(1\leq p\leq 12\), \(0\leq\ell\leq\min(100,r-(t-p))\) \\ [PERSON] [13] & \(2\leq p\leq 18\), \(0\leq\ell\leq\min(100,r-(t-p))\) \\ [PERSON] [14] & \(2\leq p\leq 18\), \(0\leq\ell\leq\min(100,r-(t-p))\) \\ \hline \multirow{4}{*}{MMT [15]} & \(4\leq p\leq 34\), \(110\leq\ell\leq\min(350,r-(t-p))\) \\  & \(\ell_{1}+\ell_{2}=\ell,\ell_{2}=\lfloor\log_{2}(\frac{t+\ell}{p/4})\rceil\) \\ \hline \multirow{4}{*}{BJMM [16]} & \(10\leq p\leq 24,90\leq\ell\leq\min(330,r-(t-p))\), \\  & \(\ell_{2}=\log_{2}\lfloor((\frac{p_{1}}{p_{1}/2})^{(k+\ell-p_{1})}],\ell_{1}= \log_{2}\lfloor(\frac{p}{p/2})^{(k+\ell-p)}\rceil\), \\  & \(0\leq\epsilon_{1}\leq 4\), \(0\leq\epsilon_{2}\leq 4\), \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Explored parameter range for the different ISD variants.