McEliece needs a break – solving McEliece-1284 and quasi-cyclic-2918 with modern ISD. (English) Zbl 1497.94086
Dunkelman, Orr (ed.) et al., Advances in cryptology – EUROCRYPT 2022. 41st annual international conference on the theory and applications of cryptographic techniques, Trondheim, Norway, May 30 – June 3, 2022. Proceedings. Part III. Cham: Springer. Lect. Notes Comput. Sci. 13277, 433-457 (2022).
Summary: With the recent shift to post-quantum algorithms it becomes increasingly important to provide precise bit-security estimates for code-based cryptography such as McEliece and quasi-cyclic schemes like BIKE and HQC. While there has been significant progress on information set decoding (ISD) algorithms within the last decade, it is still unclear to which extent this affects current cryptographic security estimates.
We provide the first concrete implementations for representation-based ISD, such as May-Meurer-Thomae (MMT) or Becker-Joux-May-Meurer (BJMM), that are parameter-optimized for the McEliece and quasi-cyclic setting. Although MMT and BJMM consume more memory than naive ISD algorithms like Prange, we demonstrate that these algorithms lead to significant speedups for practical cryptanalysis on medium-sized instances (around 60 bit). More concretely, we provide data for the record computations of McEliece-1223 and McEliece-1284 (old record: 1161), and for the quasi-cyclic setting up to code length 2918 (before: 1938).
Based on our record computations we extrapolate to the bit-security level of the proposed BIKE, HQC and McEliece parameters in NIST’s standardization process. For BIKE/HQC, we also show how to transfer the Decoding-One-Out-of-Many (DOOM) technique to MMT/BJMM. Although we achieve significant DOOM speedups, our estimates confirm the bit-security levels of BIKE and HQC.
For the proposed McEliece round-3 192 bit and two out of three 256 bit parameter sets, however, our extrapolation indicates a security level overestimate by roughly 20 and 10 bits, respectively, i.e., the high-security McEliece instantiations may be a bit less secure than desired.
For the entire collection see [Zbl 1493.94003].
We provide the first concrete implementations for representation-based ISD, such as May-Meurer-Thomae (MMT) or Becker-Joux-May-Meurer (BJMM), that are parameter-optimized for the McEliece and quasi-cyclic setting. Although MMT and BJMM consume more memory than naive ISD algorithms like Prange, we demonstrate that these algorithms lead to significant speedups for practical cryptanalysis on medium-sized instances (around 60 bit). More concretely, we provide data for the record computations of McEliece-1223 and McEliece-1284 (old record: 1161), and for the quasi-cyclic setting up to code length 2918 (before: 1938).
Based on our record computations we extrapolate to the bit-security level of the proposed BIKE, HQC and McEliece parameters in NIST’s standardization process. For BIKE/HQC, we also show how to transfer the Decoding-One-Out-of-Many (DOOM) technique to MMT/BJMM. Although we achieve significant DOOM speedups, our estimates confirm the bit-security levels of BIKE and HQC.
For the proposed McEliece round-3 192 bit and two out of three 256 bit parameter sets, however, our extrapolation indicates a security level overestimate by roughly 20 and 10 bits, respectively, i.e., the high-security McEliece instantiations may be a bit less secure than desired.
For the entire collection see [Zbl 1493.94003].
MSC:
| 94A60 | Cryptography |
| 94B05 | Linear codes (general theory) |
| 81P94 | Quantum cryptography (quantum-theoretic aspects) |
References:
| [1] | Albrecht, M., Bard, G.: The M4RI Library. The M4RI Team (2021). http://m4ri.sagemath.org |
| [2] | Albrecht, MR; Player, R.; Scott, S., On the concrete hardness of learning with errors, J. Math. Cryptol., 9, 3, 169-203 (2015) · Zbl 1352.94023 · doi:10.1515/jmc-2015-0016 |
| [3] | Aragon, N., Lavauzelle, J., Lequesne, M.: decodingchallenge.org (2019). http://decodingchallenge.org |
| [4] | Baldi, M.; Barenghi, A.; Chiaraluce, F.; Pelosi, G.; Santini, P., A finite regime analysis of information set decoding algorithms, Algorithms, 12, 10, 209 (2019) · doi:10.3390/a12100209 |
| [5] | Bard, GV, Algorithms for Solving Linear and Polynomial Systems of Equations Over Finite Fields, with Applications to Cryptanalysis (2007), College Park: University of Maryland, College Park |
| [6] | Becker, A.; Joux, A.; May, A.; Meurer, A.; Pointcheval, D.; Johansson, T., Decoding random binary linear codes in 2^n/20: how 1 + 1 = 0 improves information set decoding, Advances in Cryptology - EUROCRYPT 2012, 520-536 (2012), Heidelberg: Springer, Heidelberg · Zbl 1291.94206 · doi:10.1007/978-3-642-29011-4_31 |
| [7] | Bernstein, DJ; Lange, T.; Peters, C.; Buchmann, J.; Ding, J., Attacking and defending the McEliece cryptosystem, Post-Quantum Cryptography, 31-46 (2008), Heidelberg: Springer, Heidelberg · Zbl 1177.94128 · doi:10.1007/978-3-540-88403-3_3 |
| [8] | Both, L.; May, A.; Lange, T.; Steinwandt, R., Decoding linear codes with high error rate and its impact for LPN security, Post-Quantum Cryptography, 25-46 (2018), Cham: Springer, Cham · Zbl 1425.94077 · doi:10.1007/978-3-319-79063-3_2 |
| [9] | Chou, T., et al.: Classic McEliece: conservative code-based cryptography, 10 October 2020 (2020) |
| [10] | Dumer, I.: On minimum distance decoding of linear codes. In: Proceedings of the 5th Joint Soviet-Swedish International Workshop Information Theory, pp. 50-52 (1991) |
| [11] | Esser, A.; Bellini, E., Syndrome decoding estimator, IACR Cryptol. ePrint Arch., 2021, 1243 (2021) |
| [12] | Howgrave-Graham, N.; Joux, A.; Gilbert, H., New generic algorithms for hard knapsacks, Advances in Cryptology - EUROCRYPT 2010, 235-256 (2010), Heidelberg: Springer, Heidelberg · Zbl 1280.94069 · doi:10.1007/978-3-642-13190-5_12 |
| [13] | Kleinjung, T.; Rabin, T., Factorization of a 768-bit RSA modulus, Advances in Cryptology - CRYPTO 2010, 333-350 (2010), Heidelberg: Springer, Heidelberg · Zbl 1196.11167 · doi:10.1007/978-3-642-14623-7_18 |
| [14] | Landais, G.: Code of Grégory Landais (2012). https://gforge.inria.fr/projects/collision-dec/ |
| [15] | May, A.; Meurer, A.; Thomae, E.; Lee, DH; Wang, X., Decoding random linear codes in \(\tilde{\cal{O}}(2^{0.054n})\), Advances in Cryptology - ASIACRYPT 2011, 107-124 (2011), Heidelberg: Springer, Heidelberg · Zbl 1227.94055 · doi:10.1007/978-3-642-25385-0_6 |
| [16] | May, A.; Ozerov, I.; Oswald, E.; Fischlin, M., On computing nearest neighbors with applications to decoding of binary linear codes, Advances in Cryptology - EUROCRYPT 2015, 203-228 (2015), Heidelberg: Springer, Heidelberg · Zbl 1365.94597 · doi:10.1007/978-3-662-46800-5_9 |
| [17] | Peters, C.: Information-set decoding for linear codes over \(\text{F}_q\). In: Sendrier, N. (ed.) PQCrypto 2010. LNCS, vol. 6061, pp. 81-94. Springer, Heidelberg (2010). doi:10.1007/978-3-642-12929-2_7 · Zbl 1284.94101 |
| [18] | Prange, E., The use of information sets in decoding cyclic codes, IRE Trans. Inf. Theory, 8, 5, 5-9 (1962) · doi:10.1109/TIT.1962.1057777 |
| [19] | Sendrier, Nicolas; Yang, Bo-Yin, Decoding one out of many, Post-Quantum Cryptography, 51-67 (2011), Heidelberg: Springer, Heidelberg · Zbl 1290.94167 · doi:10.1007/978-3-642-25405-5_4 |
| [20] | Strassen, V., Gaussian elimination is not optimal, Numer. Math., 13, 4, 354-356 (1969) · Zbl 0185.40101 · doi:10.1007/BF02165411 |
| [21] | Canto Torres, R.; Sendrier, N.; Takagi, T., Analysis of information set decoding for a sub-linear error weight, Post-Quantum Cryptography, 144-161 (2016), Cham: Springer, Cham · Zbl 1405.94049 · doi:10.1007/978-3-319-29360-8_10 |
| [22] | Various: PQC-forum: Round 3 official comment: classic McEliece (2021). https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/EiwxGnfQgec |
| [23] | Various: PQC-forum: security strength categories for code based crypto (and trying out crypto stack exchange) (2021). https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/6XbG66gI7v0 |
| [24] | Vasseur, V.: Code of Valentin Vasseur (2020). https://gitlab.inria.fr/vvasseur/isd |
| [25] | Wagner, D.; Yung, M., A generalized birthday problem, Advances in Cryptology — CRYPTO 2002, 288-304 (2002), Heidelberg: Springer, Heidelberg · Zbl 1026.94541 · doi:10.1007/3-540-45708-9_19 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
