Cryptanalysis of LEDAcrypt. (English) Zbl 1504.94093
Micciancio, Daniele (ed.) et al., Advances in cryptology – CRYPTO 2020. 40th annual international cryptology conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020. Proceedings. Part III. Cham: Springer. Lect. Notes Comput. Sci. 12172, 389-418 (2020).
Summary: We report on the concrete cryptanalysis of LEDAcrypt, a 2nd Round candidate in NIST’s Post-Quantum Cryptography standardization process and one of 17 encryption schemes that remain as candidates for near-term standardization. LEDAcrypt consists of a public-key encryption scheme built from the McEliece paradigm and a key-encapsulation mechanism (KEM) built from the Niederreiter paradigm, both using a quasi-cyclic low-density parity-check (QC-LDPC) code.
In this work, we identify a large class of extremely weak keys and provide an algorithm to recover them. For example, we demonstrate how to recover 1 in \(2^{47.72}\) of LEDAcrypt’s keys using only \(2^{18.72}\) guesses at the 256-bit security level. This is a major, practical break of LEDAcrypt. Further, we demonstrate a continuum of progressively less weak keys (from extremely weak keys up to all keys) that can be recovered in substantially less work than previously known. This demonstrates that the imperfection of LEDAcrypt is fundamental to the system’s design.
For the entire collection see [Zbl 1499.94001].
In this work, we identify a large class of extremely weak keys and provide an algorithm to recover them. For example, we demonstrate how to recover 1 in \(2^{47.72}\) of LEDAcrypt’s keys using only \(2^{18.72}\) guesses at the 256-bit security level. This is a major, practical break of LEDAcrypt. Further, we demonstrate a continuum of progressively less weak keys (from extremely weak keys up to all keys) that can be recovered in substantially less work than previously known. This demonstrates that the imperfection of LEDAcrypt is fundamental to the system’s design.
For the entire collection see [Zbl 1499.94001].
MSC:
| 94A60 | Cryptography |
References:
| [1] | National Institute of Standards and Technology: Post-quantum cryptography project (2016). https://csrc.nist.gov/projects/post-quantum-cryptography |
| [2] | Alagic, G., et al.: Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process (2019) |
| [3] | Apon, D., Perlner, R.A., Robinson, A., Santini, P.: Cryptanalysis of LEDAcrypt. Cryptology ePrint Archive, Report 2020/455 (2020). https://eprint.iacr.org/2020/455 · Zbl 1504.94093 |
| [4] | 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 |
| [5] | Berlekamp, E.; McEliece, R.; Van Tilborg, H., On the inherent intractability of certain coding problems (corresp.), IEEE Trans. Inf. Theory, 24, 3, 384-386 (1978) · Zbl 0377.94018 · doi:10.1109/TIT.1978.1055873 |
| [6] | Bernstein, DJ; Sendrier, N., Grover vs. McEliece, Post-Quantum Cryptography, 73-80 (2010), Heidelberg: Springer, Heidelberg · Zbl 1284.94053 · doi:10.1007/978-3-642-12929-2_6 |
| [7] | Bernstein, DJ; Lange, T.; Peters, C.; Rogaway, P., Smaller decoding exponents: ball-collision decoding, Advances in Cryptology - CRYPTO 2011, 743-760 (2011), Heidelberg: Springer, Heidelberg · Zbl 1287.94053 · doi:10.1007/978-3-642-22792-9_42 |
| [8] | Melchor, C.A.: et al.: HQC. Technical report, National Institute of Standards and Technology (2019). https://csrc.nist.gove/projects/post-quantum-cryptography/round-2-submission |
| [9] | Bernstein, D.J.: Classic McEliece. Technical report, National Institute of Standards and Technology (2019). https://csrc.nist.gove/projects/post-quantum-cryptography/round-2-submission |
| [10] | Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of 28th Annual ACM Symposium on the Theory of Computing, pp. 212-219, Philadephia, PA, May 1996 · Zbl 0922.68044 |
| [11] | Kachigar, G., Tillich, J.-P.: Quantum Information Set Decoding Algorithms, pp. 69-89, March 2017 · Zbl 1429.94060 |
| [12] | Lee, P.J., Brickell, E.F.: An observation on the security of McEliece’s public-key cryptosystem. In: Barstow, D., et al. (eds.) EUROCRYPT 1988. LNCS, vol. 330, pp. 275-280. Springer, Heidelberg (1988). doi:10.1007/3-540-45961-8_25 · Zbl 0655.94006 |
| [13] | Leon, JS, A probabilistic algorithm for computing minimum weights of large error-correcting codes, IEEE Trans. Inf. Theory, 34, 5, 1354-1359 (1988) · Zbl 0666.94017 · doi:10.1109/18.21270 |
| [14] | Löndahl, C., Squaring attacks on McEliece public-key cryptosystems using quasi-cyclic codes of even dimension, Des. Codes Cryptogr., 80, 2, 359-377 (2016) · Zbl 1402.94064 · doi:10.1007/s10623-015-0099-x |
| [15] | Baldi, M.; Bodrato, M.; Chiaraluce, F.; Ostrovsky, R.; De Prisco, R.; Visconti, I., A new analysis of the McEliece cryptosystem based on QC-LDPC codes, Security and Cryptography for Networks, 246-262 (2008), Heidelberg: Springer, Heidelberg · Zbl 1180.94046 · doi:10.1007/978-3-540-85855-3_17 |
| [16] | Baldi, M., Barenghi, A., Chiaraluce, F., Pelosi, G., Santini, P.: LEDAcrypt. Technical report, National Institute of Standards and Technology (2019). https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions |
| [17] | Albrecht, M., Cid, C., Paterson, K.G., Tjhai, C.J., Tomlinson, M.: NTS-KEM. Technical report, National Institute of Standards and Technology (2019). https://csrc.nist.gove/projects/post-quantum-cryptography/round-2-submission |
| [18] | 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 |
| [19] | 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 |
| [20] | McEliece, R.: A public-key cryptosystem based on algebraic coding theory. Deep Space Netw. (DSN) Prog. Rep. 44, 114-116 (1978) |
| [21] | Moody, D.; Perlner, R.; Takagi, T., Vulnerabilities of “McEliece in the World of Escher”, Post-Quantum Cryptography, 104-117 (2016), Cham: Springer, Cham · Zbl 1405.94077 · doi:10.1007/978-3-319-29360-8_8 |
| [22] | Aragon, N., et al.: BIKE. Technical report, National Institute of Standards and Technology (2019). https://csrc.nist.gove/projects/post-quantum-cryptography/round-2-submission |
| [23] | Niederreiter, H., Knapsack-type cryptosystems and algebraic coding theory, Prob. Control Inf. Theory, 15, 2, 159-166 (1986) · Zbl 0611.94007 |
| [24] | Perlner, R.; Mosca, M., Optimizing information set decoding algorithms to attack cyclosymmetric MDPC codes, Post-Quantum Cryptography, 220-228 (2014), Cham: Springer, Cham · Zbl 1383.94059 · doi:10.1007/978-3-319-11659-4_13 |
| [25] | 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 |
| [26] | Sendrier, N.; Yang, B-Y, 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 |
| [27] | Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science (FOCS), pp. 124-134 (1994) |
| [28] | Jacques Stern. A method for finding codewords of small weight. In Coding Theory and Applications, 3rd International Colloquium, Toulon, France, November 2-4, 1988, Proceedings, pages 106-113, 1988 · Zbl 0678.94006 |
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.
