# 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}{c c c c c c c c} \hline \hline \multicolumn{2}{c}{**Category 1—Security Level Equivalent to Break AES-128 on a Classical Machine**} & \multicolumn{1}{c}{} & & & & \\ \multicolumn{2}{c}{**Problem**} & **Cipher** & **Variant** & **St** & **FS** & **MMT** & **BJMM** \\ \hline \multirow{6}{*}{Codeword Finding Problem (CFP)} & \multirow{3}{*}{BIKE-2} & CPA & 40.72 & 40.74 & 53.47 & 52.59 \\  & & CCA & 41.38 & 41.40 & 54.34 & 53.08 \\  & & \(n_{0}=2\) & 42.46 & 42.48 & 55.74 & 55.48 \\  & & \(n_{0}=3\) & 39.81 & 39.83 & 52.26 & 50.51 \\  & & LEDAcrypt & \(n_{0}=4\) & 39.40 & 39.43 & 51.73 & 50.59 \\  & & LT, \(n_{0}=2\) & 46.40 & 46.40 & 48.41 & 61.44 \\  & & XT, \(n_{0}=2\) & 48.06 & 48.07 & 50.08 & 64.26 \\ \hline \multirow{6}{*}{Syndrome Decoding Problem (SDP)} & Classic McEliece & & 34.68 & 34.76 & 78.03 & 68.19 \\  & & NTS-KEM & & 35.60 & 35.65 & 80.29 & 70.36 \\  & & CPA & 40.72 & 40.74 & 53.47 & 52.59 \\  & & CCA & 41.38 & 41.40 & 54.34 & 53.08 \\  & & \(n_{0}=2\) & 42.46 & 42.48 & 55.74 & 55.48 \\  & & \(n_{0}=3\) & 42.80 & 42.91 & 56.33 & 55.51 \\  & & LEDAcrypt & \(n_{0}=4\) & 44.31 & 44.32 & 69.63 & 58.72 \\  & & LT, \(n_{0}=2\) & 46.40 & 46.40 & 48.41 & 61.44 \\  & & XT, \(n_{0}=2\) & 48.06 & 48.07 & 50.08 & 64.26 \\ \hline \multicolumn{2}{c}{**Category 3—Security Level Equivalent to Break AES-192 on a Classical Machine**} & \multicolumn{1}{c}{} & & & \\ \multicolumn{2}{c}{**Problem**} & **Cipher** & **Variant** & **St** & **FS** & **MMT** & **BJMM** \\ \hline \multirow{6}{*}{Codeword Finding Problem (CFP)} & \multirow{3}{*}{BIKE-2} & CPA & 43.67 & 43.68 & 79.51 & 57.23 \\  & & CCA & 44.74 & 44.75 & 81.58 & 58.66 \\  & & \(n_{0}=2\) & 44.90 & 44.90 & 81.89 & 59.01 \\  & & \(n_{0}=3\) & 42.80 & 42.81 & 77.78 & 56.22 \\  & & \(n_{0}=4\) & 42.30 & 42.31 & 76.79 & 55.07 \\  & & LT, \(n_{0}=2\) & 48.54 & 48.54 & 76.54 & 65.32 \\  & & XT, \(n_{0}=2\) & 50.81 & 50.81 & 66.74 & 68.52 \\ \hline \multirow{6}{*}{Syndrome Decoding Problem (SDP)} & Classic McEliece & & 35.66 & 35.71 & 80.41 & 70.51 \\  & & NTS-KEM & & 77.63 & 77.74 & 88.99 & 80.42 \\  & & CPA & 43.67 & 43.68 & 79.51 & 57.23 \\  & & CCA & 44.74 & 44.75 & 81.58 & 58.66 \\  & & \(n_{0}=2\) & 44.90 & 44.90 & 81.89 & 59.01 \\  & & \(n_{0}=3\) & 45.88 & 45.89 & 83.84 & 61.30 \\  & & LEDAcrypt & \(n_{0}=4\) & 47.18 & 47.18 & 98.20 & 63.29 \\  & & LT, \(n_{0}=2\) & 48.54 & 48.54 & 63.74 & 65.32 \\  & & XT, \(n_{0}=2\) & 50.81 & 50.81 & 66.74 & 68.52 \\ \hline \multicolumn{2}{c}{**Category 5—Security Level Equivalent to Break AES-256 on a Classical Machine**} & \multicolumn{1}{c}{} & & & \\ \multicolumn{2}{c}{**Problem**} & **Cipher** & **Variant** & **St** & **FS** & **MMT** & **BJMM** \\ \hline \multirow{6}{*}{Codeword Finding Problem (CFP)} & \multirow{3}{*}{BIKE-2} & CPA & 45.98 & 45.98 & 106.61 & 61.50 \\  & & CCA & 46.95 & 46.96 & 109.11 & 62.69 \\  & & \(n_{0}=2\) & 46.51 & 46.52 & 108.00 & 61.71 \\  & & \(n_{0}=3\) & 45.20 & 45.21 & 104.56 & 59.68 \\  & & LEDAcrypt & \(n_{0}=4\) & 44.35 & 44.36 & 102.36 & 58.74 \\  & & LT, \(n_{0}=2\) & 50.46 & 50.46 & 92.80 & 68.73 \\  & & XT, \(n_{0}=2\) & 52.86 & 52.86 & 83.64 & 72.22 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Memory costs expressed as \(\log_{2}\)(memory_size_in_bits), for each list-based ISDs (i.e., St [13], FS [14], MMT [15], and BJMM [16]) applied to NIST round-2 code-based cryptosystems. Information Set Decoding (ISD) variants are labeled as: [PERSON] (ST), Finiasz and Sendrier (FS), May–Meurer-Thomae (MMT), and Becker–Joux–May–Meurer (BJMM)

## 5 Conclusions

In this work, we survey the current approaches to solve efficiently the Information Set Decoding (ISD) problem, providing a complete procedural description of the algorithms at hand. We provide finite regime expressions to estimate both the computational demand and the space requirements of the different Information Set Decoding (ISD) alternatives.