# A Finite Regime Analysis of Information Set Decoding Algorithms
## 3 A Finite Regime Analysis of Information Set Decoding Techniques
### Lee-Brickell
We implemented all the complexity formulas from Section 3 employing [PERSON]'s NTL library, representing the intermediate values either as arbitrary precision integers, or as NTL::RR selectable precision floating point numbers. We chose to employ a 128 bit mantissa and the default 64 bit exponent for the selectable precision. To minimize the error in computing a large amount of binomial coefficients, while retaining acceptable performance, we precompute the exact values for all the \(\binom{n}{k}\) binomials for all pairs \(n,\ k\) up to \(\binom{3,000}{200}\). Furthermore, to minimize the error of [PERSON]'s approximation whenever \(n\gg k\) we also precompute all the exact values for the binomials up to \(\binom{10,000}{100}\), and compute the exact value whenever \(k<10\). To provide a fast approximated computation for all the binomials which do not fall in the aforementioned intervals, we compute the binomials employing the logarithm of [PERSON]'s series approximated to the fourth term. We explored the parameter space of each algorithm considering the fact that the different parameters drive different trade-off points in each algorithm. To this end, we explored an appropriately sized region of the parameter space, which we report in Table 3. To determine the explored region, we started from a reasonable choice and enlarged the region until the value of the parameters minimizing the attack complexity was no longer on the region edge for all the involved parameters. We employed, for the choice of the \(\ell_{2}\) parameter in the MMT ISD variant and the \(\ell_{1}\) and \(\ell_{2}\) parameters in the BJMM variant, the choices which were advised in the respective works. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline
**Category** & **Cipher** & **Variant** & \(n\) & \(k\) & \(t\) & \(w\) & \(p\) \\ \hline \multirow{8}{*}{\(1\)} & Classic McEliece & & & 3488 & 2720 & 64 & - & 1 \\  & NTS-KEM & & & 4096 & 3328 & 64 & - & 1 \\  & \multirow{3}{*}{BIKE-2} & KEM-CPA & 20,326 & 10,163 & 134 & 142 & 10,163 \\  & & KEM-CCA & 23,558 & 11,779 & 134 & 142 & 11,779 \\  & & KEM, \(n_{0}=2\) & 29,878 & 14,939 & 136 & 154 & 14,939 \\  & \multirow{3}{*}{LEDAcrypt} & KEM, \(n_{0}=3\) & 24,807 & 16,538 & 86 & 243 & 8269 \\  & & KEM, \(n_{0}=4\) & 30,188 & 22,641 & 69 & 364 & 7547 \\  & & KEM-LT, \(n_{0}=2\) & 71,798 & 35,899 & 136 & 154 & 35,899 \\  & & KEM-XT, \(n_{0}=2\) & 104,294 & 52,147 & 136 & 154 & 52,147 \\ \hline \multirow{8}{*}{\(3\)} & Classic McEliece & & & 4608 & 3360 & 96 & - & 1 \\  & NTS-KEM & & & 8192 & 7152 & 80 & - & 1 \\  & \multirow{3}{*}{BIKE-2} & KEM-CPA & 39,706 & 19,583 & 199 & 206 & 19,583 \\  & & KEM-CCA & 49,642 & 24,821 & 199 & 206 & 24,821 \\  & & KEM, \(n_{0}=2\) & 51,386 & 25,693 & 199 & 210 & 25,693 \\  & \multirow{3}{*}{LEDAcrypt} & KEM, \(n_{0}=3\) & 48,201 & 32,134 & 127 & 363 & 16,067 \\  & & KEM, \(n_{0}=4\) & 57,364 & 43,023 & 101 & 540 & 14,341 \\  & & KEM-LT, \(n_{0}=2\) & 115,798 & 57,899 & 199 & 210 & 57,899 \\  & & KEM-XT, \(n_{0}=2\) & 192,442 & 96,221 & 199 & 210 & 96,221 \\ \hline \multirow{8}{*}{\(5\)} & Classic McEliece & \(n=6688\) & 6688 & 5024 & 128 & - & 1 \\  & \multirow{3}{*}{NTS-KEM} & & \(n=6960\) & 6960 & 5413 & 119 & - & 1 \\  & & \(n=8192\) & 8192 & 6528 & 128 & - & 1 \\  & \multirow{3}{*}{NTS-KEM} & & \(8192\) & 6424 & 136 & - & 1 \\  & & KEM-CPA & 65,498 & 32,749 & 264 & 274 & 32,749 \\  & & KEM-CCA & 81,194 & 40,597 & 264 & 274 & 40,597 \\  & & KEM, \(n_{0}=2\) & 73,754 & 36,877 & 267 & 286 & 36,877 \\  & \multirow{3}{*}{LEDAcrypt} & KEM, \(n_{0}=3\) & 82,311 & 54,874 & 169 & 495 & 27,437 \\  & & KEM, \(n_{0}=4\) & 90,764 & 68,073 & 134 & 676 & 22,691 \\  & & KEM-LT, \(n_{0}=2\) & 178,102 & 89,051 & 267 & 286 & 89,051 \\  & & KEM-XT, \(n_{0}=2\) & 304,534 & 152,267 & 267 & 286 & 152,267 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Summary of the code parameters for the second round submissions: code length \(n\), code redundancy \(n-k=r\), and number of errors expected to be corrected \(t\).