# A Finite Regime Analysis of Information Set Decoding Algorithms
## 3 A Finite Regime Analysis of Information Set Decoding Techniques
### Lee-Brickell
\begin{table}
\begin{tabular}{l l l} \hline \hline \multicolumn{1}{c}{**Name**} & \multicolumn{1}{c}{**No.of Iterations**} & \multicolumn{1}{c}{**Parameters to Optimize**} \\  & \multicolumn{1}{c}{(i.e., 1/Prsucc)} & \multicolumn{1}{c}{} & \\ \hline [PERSON] [10] & \(\frac{(\frac{r}{r})}{(\frac{r}{r})}\) & none \\ [PERSON] [11] & \(\frac{(\frac{r}{r})}{(\frac{r}{r})(\frac{r}{r})}\) & \(0\leq p\leq t\) (\(p=2\) is asymp. optimal) \\ [PERSON] [12] & \(\frac{(\frac{r}{r})}{(\frac{r}{r})(\frac{r}{r})}\) & \(0\leq p\leq t,0\leq\ell\leq r-(t-p)\) \\ [PERSON] [13] & \(\frac{(\frac{r}{r})}{(\frac{r}{r})^{2}(\frac{r}{r}-\ell)}\) & \(0\leq p\leq t,0\leq\ell\leq r-(t-p)\) \\ Finiasz–Sendrier [14] & \(\frac{(\frac{r}{r})}{(\frac{r}{r})^{2}(\frac{r}{r}-\ell)}\) & \(0\leq p\leq t,0\leq\ell\leq r-(t-p)\) \\ MMT [15] & \(\frac{(\frac{r}{r})}{(\frac{r}{r})^{4}(\frac{r}{r}-\ell)}\) & \(0\leq p\leq t,\ell_{1}+\ell_{2}=\ell,0\leq\ell\leq r-(t-p)\), \(\ell_{2}\approx\log_{2}\left(\frac{t\frac{kt}{r}}{p/4}\right)\) \\  & & \(\ell_{2}\approx\log_{2}\left(\frac{(p_{1/2}^{\ell_{1}})(k+\ell-p_{1})}{\ell_{ 2}}\right),\) \\ BJMM [16] & \(\frac{(\frac{r}{r})}{(\frac{r}{r})^{4}(\frac{t-p}{r})}\left(\frac{(\frac{kt}{r })}{(\frac{r}{r})}\right)^{-4}\) & \(\ell_{1}\approx\log_{2}\left(\frac{(p_{2}^{\ell_{1}})(k+\ell-p_{1})}{\ell_{ 2}}\right),\)\(0\leq p\leq t,\) \\  & \(0\leq\ell\leq r,\)\(0\leq\ell_{2}\leq\ell_{1}\leq\ell,\) \\  & & \(0\leq\ell_{1}\leq t-p,\)\(0\leq\varepsilon_{2}\leq t-p_{1},\) \\  & & \(p_{3}=\frac{p_{2}}{2},\)\(p_{2}=\frac{p_{1}}{2}+\varepsilon_{2},\)\(p_{1}=\frac{p}{2}+\varepsilon_{1}\) \\ \hline \multicolumn{1}{c}{**Name**} & \multicolumn{1}{c}{**Single Iteration Cost**} \\ \hline Prange [10] & \(C_{\text{IS}}(n,r)+\mathcal{O}(n)\) \\ Lee–Brickellell [11] & \(C_{\text{IS}}(n,r)+\binom{k}{p}(pr)\) \\ Leon [12] & \(C_{\text{IS}}(n,r)+\binom{k}{p}(pr)\) \\ Stern [13] & \(C_{\text{IS}}(n,r)+\binom{k}{p}\left(p\ell+\frac{\binom{r}{p}}{2^{\ell}}p(r- \ell)\right)\) \\ Finasz-Sendrier [14] & \(C_{\text{IS}}(n,r)+\binom{k/2}{p/2}\left(p\ell+\frac{\binom{k/2}{2}}{2^{\ell /2}}p(r-\ell)\right)\) \\ MMT [15] & \(\left\{\begin{array}{l}C_{\text{IS}-\text{IS}}(n,r,\ell)+\min\left((\binom{k +\ell/2}{p/4},\frac{\binom{k+\ell/2}{p/2}}{p/2})\cdot\left(\frac{p}{r}\ell_{2} +\frac{\binom{k+\ell/2}{p/4}}{2^{\ell_{1}}}\right)\cdot\left(\frac{p}{r}\ell_ {2}+\frac{\binom{k+\ell/2}{p/4}}{2^{\ell_{1}}}\frac{p}{2}\ell_{1}\right)\\ +(\binom{k+\ell/2}{p/4})\frac{p}{2}\ell_{2}+\binom{(k+\ell/2)}{p/4}\left(\frac{p }{2}\ell_{2}+\frac{\binom{k+\ell/2}{p/4}}{2^{\ell_{2}}}\frac{p}{2}\ell_{1}+ \frac{\binom{k+\ell/2}{p/4}}{2^{\ell_{1}+2}(p_{2}^{\ell_{2}})}p(r-\ell) \right)\\ \end{array}\right.\) \\ BJMM [16] & \(\left\{\begin{array}{l}C_{\text{IS}-\text{IS}}(n,r,\ell)\\ +4\left(k+\ell+2(\frac{kt}{p/5})+\ell_{2}+\binom{kt}{p/5}^{2}\right)^{2}(2p_{3} \ell_{2})\end{array}\right.\right\}+2\left(\left(\frac{\binom{p_{1}}{2^{\ell_{ 1}}}(k+\ell-p_{1})}{2^{\ell_{1}}}(\frac{kt^{2}}{p_{3}})^{2}\right)^{2}(2p_{2} \ell_{1})\right)\\ +\left(\frac{1}{2^{\ell_{1}}}(p_{2}^{\ell})(k+\ell-p)\left(\frac{1}{2^{\ell_{ 1}}}(p_{1/2})(k+\ell-p_{1})(\frac{kt^{2}}{p_{3}})^{2}\right)^{2}\right)^{2}(2p _{1}\ell)\\ +\frac{1}{2^{\ell}}\left(\frac{1}{2^{\ell_{1}}}(p_{p/2}^{\ell})(k+\ell-p)\left( \frac{1}{2^{\ell_{1}}}(p_{1/2})(k+\ell-p_{1})(\frac{kt^{2}}{p_{3}})^{2}\right)^{ 2}\right)^{2}(p(r-\ell))\\ \end{array}\right.\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Overview of ISDs costs in terms of execution time complexities, considering a constant access memory cost model, expressed as: \(\texttt{Cost}=\texttt{NumberOfIterations}\times\texttt{Cost}_{\texttt{single iteration}}\). all the aforementioned candidates in Table 2. Furthermore, for the cryptosystems relying on low- or moderate-density parity check codes, we also report the weight of the codeword to be found, \(w\), in the case of a Codeword Finding Problem (CFP).