Abstract
In this paper we propose a new approach to investigate the security of the McEliece cryptosystem. We recall that this cryptosystem relies on the use of error-correcting codes. Since its invention thirty years ago, no efficient attack had been devised that managed to recover the private key. We prove that the private key of the cryptosystem satisfies a system of bi-homogeneous polynomial equations. This property is due to the particular class of codes considered which are alternant codes. We have used these highly structured algebraic equations to mount an efficient key-recovery attack against two recent variants of the McEliece cryptosystems that aim at reducing public key sizes. These two compact variants of McEliece managed to propose keys with less than 20,000 bits. To do so, they proposed to use quasi-cyclic or dyadic structures. An implementation of our algebraic attack in the computer algebra system Magma allows to find the secret-key in a negligible time (less than one second) for almost all the proposed challenges. For instance, a private key designed for a 256-bit security has been found in 0.06 seconds with about 217.8 operations.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Adams, W., Loustaunau, P.: An Introduction to Gröbner Bases. American Mathematical Society, Providence (July 1994)
Avanzi, R.: Lightweight asymmetric cryptography and alternatives to rsa, ecrypt european network of excellence in cryptology (2005), http://www.ecrypt.eu.org/ecrypt1/documents/D.AZTEC.2-1.2.pdf
Baldi, M., Bodrato, M., Chiaraluce, G.F.: A new analysis of the McEliece cryptosystem based on QC-LDPC codes. In: Ostrovsky, R., De Prisco, R., Visconti, I. (eds.) SCN 2008. LNCS, vol. 5229, pp. 246–262. Springer, Heidelberg (2008)
Baldi, M., Chiaraluce, G.F.: Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes. In: IEEE International Symposium on Information Theory, Nice, France, March 2007, pp. 2591–2595 (2007)
Berger, T.P., Cayrel, P.L., Gaborit, P., Otmani, A.: Reducing key length of the McEliece cryptosystem. In: Preneel, B. (ed.) AFRICACRYPT 2009. LNCS, vol. 5580, pp. 77–97. Springer, Heidelberg (2009)
Berger, T.P., Loidreau, P.: How to mask the structure of codes for a cryptographic use. Designs Codes and Cryptography 35(1), 63–79 (2005)
Berger, T.P., Loidreau, P.: Designing an efficient and secure public-key cryptosystem based on reducible rank codes. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 218–229. Springer, Heidelberg (2004)
Bernstein, D.J., Lange, T., Peters, C.: Attacking and defending the McEliece cryptosystem. In: Buchmann, J., Ding, J. (eds.) PQCrypto 2008. LNCS, vol. 5299, pp. 31–46. Springer, Heidelberg (2008)
Bernstein, D.J., Lange, T., Peters, C., van Tilborg, H.: Explicit bounds for generic decoding algorithms for code-based cryptography. In: Pre-proceedings of WCC 2009, pp. 168–180 (2009)
Biswas, B., Sendrier, N.: McEliece cryptosystem implementation: Theory and practice. In: Buchmann, J., Ding, J. (eds.) PQCrypto 2008. LNCS, vol. 5299, pp. 47–62. Springer, Heidelberg (2008)
Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. PhD thesis, Innsbruck (1965)
Cox, D.A., Little, J.B., O’Shea, D.: Ideals, Varieties, and algorithms: an Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics. Springer, New York (2001)
Faugère, J.-C.: A new efficient algorithm for computing gröbner bases (f4). Journal of Pure and Applied Algebra 139(1-3), 61–88 (1999)
Faugère, J.-C.: A new efficient algorithm for computing gröbner bases without reduction to zero: F5. In: ISSAC 2002, pp. 75–83. ACM press, New York (2002)
Faugère, J.-C., Levy-dit Vehel, F., Perret, L.: Cryptanalysis of minrank. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 280–296. Springer, Heidelberg (2008)
Faugère, J.-C., El Din, M.S., Spaenlehauer, P.-J.: Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1,1): Algorithms and complexity. CoRR, abs/1001.4004 (2010)
Faugère, J.-C., Gianni, P.M., Lazard, D., Mora, T.: Efficient computation of zero-dimensional gröbner bases by change of ordering. J. Symb. Comput. 16(4), 329–344 (1993)
Faure, C., Minder, L.: Cryptanalysis of the McEliece cryptosystem over hyperelliptic curves. In: Proceedings of the eleventh International Workshop on Algebraic and Combinatorial Coding Theory, Pamporovo, Bulgaria, June 2008, pp. 99–107 (2008)
Finiasz, M., Sendrier, N.: Security bounds for the design of code-based crypto systems. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 88–105. Springer, Heidelberg (2009)
Gabidulin, E., Paramonov, A.V., Tretjakov, O.V.: Ideals over a non-commutative ring and their applications to cryptography. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 482–489. Springer, Heidelberg (1991)
Gaborit, P.: Shorter keys for code based cryptography. In: Ytrehus, Ø. (ed.) WCC 2005. LNCS, vol. 3969, pp. 81–91. Springer, Heidelberg (2006)
Gibson, J.K.: Severely denting the Gabidulin version of the McEliece public key cryptosystem. Design Codes and Cryptography 6(1), 37–45 (1995)
Janwa, H., Moreno, O.: McEliece public key cryptosystems using algebraic-geometric codes. Designs Codes and Cryptography 8(3), 293–307 (1996)
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes, 5th edn. North-Holland, Amsterdam (1986)
McEliece, R.J.: A Public-Key System Based on Algebraic Coding Theory, pp. 114–116. Jet Propulsion Lab. (1978); DSN Progress Report 44
Minder, L., Shokrollahi, A.: Cryptanalysis of the Sidelnikov cryptosystem. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 347–360. Springer, Heidelberg (2007)
Misoczki, R., Barreto, P.S.L.M.: Compact McEliece keys from Goppa codes. In: Jacobson Jr., M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 376–392. Springer, Heidelberg (2009)
Niederreiter, H.: A public-key cryptosystem based on shift register sequences. In: Pichler, F. (ed.) EUROCRYPT 1985. LNCS, vol. 219, pp. 35–39. Springer, Heidelberg (1985)
Otmani, A., Tillich, J.P., Dallot, L.: Cryptanalysis of McEliece cryptosystem based on quasi-cyclic ldpc codes. In: Proceedings of First International Conference on Symbolic Computation and Cryptography, Beijing, China, April 28-30, pp. 69–81. LMIB Beihang University (2008)
Overbeck, R.: Structural attacks for public key cryptosystems based on Gabidulin codes. J. Cryptology 21(2), 280–301 (2008)
Sidelnikov, V.M.: A public-key cryptosytem based on Reed-Muller codes. Discrete Mathematics and Applications 4(3), 191–207 (1994)
Sidelnikov, V.M., Shestakov, S.O.: On the insecurity of cryptosystems based on generalized Reed-Solomon codes. Discrete Mathematics and Applications 1(4), 439–444 (1992)
Stern, J.: A method for finding codewords of small weight. In: Wolfmann, J., Cohen, G. (eds.) Coding Theory 1988. LNCS, vol. 388, pp. 106–113. Springer, Heidelberg (1988)
Gauthier Umana, V., Leander, G.: Practical key recovery attacks on two McEliece variants (2009), http://eprint.iacr.org/2009/509
Wieschebrink, C.: Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes. eprint 452 (2009), http://eprint.iacr.org/2009/452.pdf
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Faugère, JC., Otmani, A., Perret, L., Tillich, JP. (2010). Algebraic Cryptanalysis of McEliece Variants with Compact Keys. In: Gilbert, H. (eds) Advances in Cryptology – EUROCRYPT 2010. EUROCRYPT 2010. Lecture Notes in Computer Science, vol 6110. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13190-5_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-13190-5_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13189-9
Online ISBN: 978-3-642-13190-5
eBook Packages: Computer ScienceComputer Science (R0)