# zbMATH — the first resource for mathematics

Structural cryptanalysis of McEliece schemes with compact keys. (English) Zbl 1361.94039
Summary: A very popular trend in code-based cryptography is to decrease the public-key size by focusing on subclasses of alternant/Goppa codes which admit a very compact public matrix, typically quasi-cyclic (QC), quasi-dyadic (QD), or quasi-monoidic (QM) matrices. We show that the very same reason which allows to construct a compact public-key makes the key-recovery problem intrinsically much easier. The gain on the public-key size induces an important security drop, which is as large as the compression factor $$p$$ on the public-key. The fundamental remark is that from the $$k\times n$$ public generator matrix of a compact McEliece, one can construct a $$k/p \times n/p$$ generator matrix which is – from an attacker point of view – as good as the initial public-key. We call this new smaller code the folded code. Any key-recovery attack can be deployed equivalently on this smaller generator matrix. To mount the key-recovery in practice, we also improve the algebraic technique of Faugère, Otmani, Perret and Tillich (FOPT). In particular, we introduce new algebraic equations allowing to include codes defined over any prime field in the scope of our attack. We describe a so-called “structural elimination” which is a new algebraic manipulation which simplifies the key-recovery system. As a proof of concept, we report successful attacks on many cryptographic parameters available in the literature. All the parameters of CFS-signatures based on QD/QM codes that have been proposed can be broken by this approach. In most cases, our attack takes few seconds (the hardest case requires less than 2 h). In the encryption case, the algebraic systems are harder to solve in practice. Still, our attack succeeds against several cryptographic challenges proposed for QD and QM encryption schemes. We mention that some parameters that have been proposed in the literature remain out of reach of the methods given here. However, regardless of the key-recovery attack used against the folded code, there is an inherent weakness arising from Goppa codes with QM or QD symmetries. Indeed, the security of such schemes is not relying on the bigger compact public matrix but on the small folded code which can be efficiently broken in practice with an algebraic attack for a large set of parameters.

##### MSC:
 94A60 Cryptography
##### Software:
FGb; Magma; McEliece
Full Text:
##### References:
 [1] Baldi M., Bianchi M., Chiaraluce F.: Security and complexity of the McEliece cryptosystem based on QC-LDPC codes. IET Inf. Secur. 7(3), 212-220 (2013). See also arXiv:1109.5827v6[cs.CR] [2] Baldi M., Bodrato M., Chiaraluce F.: A new analysis of the McEliece cryptosystem based on QC-LDPC codes. In: Proceedings of the 6th International Conference on Security and Cryptography for Networks SCN ’08, pp. 246-262. Springer, Berlin (2008) · Zbl 1180.94046 [3] Barbier M.: Key reduction of McEliece’s cryptosystem using list decoding. CoRR, arXiv:1102.2566 (2011) [4] Barreto P.S.L.M., Cayrel P.-L., Misoczki R., Niebuhr R.: Quasi-dyadic CFS signatures. In: Lai X., Yung M., Lin D. (eds.) Inscrypt. Lecture Notes in Computer Science, vol. 6584, pp. 336-349. Springer, Heidelberg (2010) · Zbl 1295.94016 [5] Barreto P.S.L.M., Lindner R., Misoczki R.: Monoidic codes in cryptography. In: Yang B.Y. (ed.) PQCrypto. Lecture Notes in Computer Science, vol. 7071, pp. 179-199. Springer, Heidelberg (2011) · Zbl 1298.94078 [6] Becker A., Joux A., May A., Meurer A.: Decoding random binary linear codes in $$2^{n/20}$$: how 1 + 1 = 0 improves information set decoding. In: Pointcheval D., Johansson T. (eds.) EUROCRYPT. Lecture Notes in Computer Science, vol. 7237, pp. 520-536. Springer, Heidelberg (2012) · Zbl 1291.94206 [7] Berger T.P.: Cyclic alternant codes induced by an automorphism of a GRS code. In: Mullin R., Mullen G. (eds.) Finite Fields: Theory, Applications and Algorithms. Contemporary Mathematics, vol. 225, pp. 143-154. AMS, Waterloo, Canada (1999) · Zbl 0914.94014 [8] Berger T.P.: Goppa and related codes invariant under a prescribed permutation. IEEE Trans. Inf. Theory 46(7), 2628 (2000) · Zbl 1001.94049 [9] Berger T.P.: On the cyclicity of Goppa codes, parity-check subcodes of Goppa codes and extended Goppa codes. Finite Fields Appl. 6, 255-281 (2000) · Zbl 0965.94025 [10] Berger T.P., Cayrel P.L., Gaborit P., Otmani A.L.: Reducing key length of the McEliece cryptosystem. In: Preneel B. (ed.) Progress in Cryptology—Second International Conference on Cryptology in Africa (AFRICACRYPT 2009). Lecture Notes in Computer Science, vol. 5580, pp. 77-97, 21-25 June 2009, Gammarth, Tunisia · Zbl 1246.94022 [11] Bernstein D.J., Lange T., Peters C.: Attacking and defending the McEliece cryptosystem. In : PQCrypto. Lecture Notes in Computer Science, vol. 5299. pp. 31-46. Springer, Heidelberg (2008) · Zbl 1177.94128 [12] Bernstein D.J., Lange T., Peters C.: Attacking and defending the McEliece cryptosystem. In: PQCrypto, pp. 31-46. (2008) · Zbl 1177.94128 [13] 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) [14] Bernstein D.J., Lange T., Peters C.: Smaller decoding exponents: ball-collision decoding. In: Phillip R. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 6841, pp. 743-760. Springer, Heidelberg (2011) · Zbl 1287.94053 [15] Bosma W., Cannon J.J., Playoust C.: The Magma algebra system I: the user language. J. Symb. Comput. 24(3-4), 235-265 (1997) · Zbl 0898.68039 [16] Buchberger B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. PhD thesis, Innsbruck (1965) · Zbl 1245.13020 [17] Canteaut A., Chabaud F.: A new algorithm for finding minimum-weight words in a linear code: application to McEliece’s cryptosystem and to narrow-sense BCH codes of length 511. IEEE Trans. Inf. Theory 44(1), 367-378 (1998) · Zbl 1053.94558 [18] 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) [19] Faugère J.-C.: A new efficient algorithm for computing Gröbner bases (F4). J. Pure Appl. Algebra 139(1-3), 61-88 (1999) · Zbl 0930.68174 [20] Faugère J.-C.: A new efficient algorithm for computing Gröbner bases without reduction to zero: F5. In: ISSAC’02, pp. 75-83. ACM Press, New York (2002) · Zbl 1072.68664 [21] Faugère, J.-C.: FGb: a library for computing Gröbner bases. In: Fukuda K., Hoeven J., Joswig M., Takayama N. (eds.) Mathematical Software—ICMS 2010. Lecture Notes in Computer Science, vol. 6327, pp. 84-87. Springer, Berlin (2010) · Zbl 1294.68156 [22] Faugère J.-C., Gauthier V., Otmani A., Perret L., Tillich J.-P.: A distinguisher for high rate McEliece cryptosystems. IEEE Trans. Inf. Theory 59(10), 6830-6844 (2013) · Zbl 1364.94536 [23] Faugère J.-C., Gauthier-Umana V., Otmani A., Perret L., Tillich J.-P.: A distinguisher for high rate McEliece cryptosystems. In: Information Theory Workshop (ITW), 2011 IEEE, pp. 282-286 (2011) · Zbl 1364.94536 [24] Faugère J.-C., Otmani A., Perret L., de Portzamparc F., Tillich J.-P.: Folding alternant and Goppa codes with non-trivial automorphism groups. (2014). arXiv:1405.5101 [cs.IT] · Zbl 1359.94876 [25] Faugère J.-C., Otmani A., Perret L., de Portzamparc L., Tillich J.-P.: Structural weakness of compact variants of the McEliece cryptosystem. In: Proceedings of the IEEE International Symposium Information Theory—ISIT 2014, Honolulu, HI, USA, pp. 1717-1721 (2014) [26] Faugère J.-C., Otmani A., Perret L., Tillich J.-P.: Algebraic cryptanalysis of McEliece variants with compact keys. In: Gilbert H. (ed.) Advances in Cryptology—EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30-June 3, 2010. Proceedings. Lecture Notes in Computer Science, vol. 6110, pp. 279-298. Springer, Berlin (2010) · Zbl 1280.94051 [27] Faugère J.-C., Otmani A., Perret L., Tillich J.-P.: Algebraic cryptanalysis of McEliece variants with compact keys—toward a complexity analysis. In: SCC ’10: Proceedings of the 2nd International Conference on Symbolic Computation and Cryptography, pp. 45-55. RHUL (2010) [28] Finiasz M., Sendrier N.: Security bounds for the design of code-based cryptosystems. In: Matsui M. (ed.) Asiacrypt 2009. Lecture Notes in Computer Science, vol. 5912, pp. 88-105. Springer, Heidelberg (2009) · Zbl 1267.94058 [29] Gaborit P.: Shorter keys for code based cryptography. In: Proceedings of the 2005 International Workshop on Coding and Cryptography (WCC 2005), Bergen, Norway, pp. 81-91 (2005) [30] Gauthier U.V., Leander G.: Practical key recovery attacks on two McEliece variants. In: International Conference on Symbolic Computation and Cryptography-SCC, vol. 2010, p. 62 (2010) [31] Gilbert H., (ed.) Advances in Cryptology—EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30-June 3, 2010. Proceedings. Lecture Notes in Computer Science, vol. 6110. Springer, Berlin (2010) [32] Heyse S.: Implementation of McEliece based on quasi-dyadic Goppa codes for embedded devices. In: Yang B.-Y. (ed.) Post-quantum Cryptography. Lecture Notes in Computer Science, vol. 7071, pp. 143-162. Springer, Berlin (2011) · Zbl 1298.94092 [33] Lee P.J., Brickell E.F.: An observation on the security of McEliece’s public-key cryptosystem. In: Advances in Cryptology—EUROCRYPT’88. Lecture Notes in Computer Science, vol. 330/1988, pp. 275-280. Springer, Berlin (1988) · Zbl 0655.94006 [34] Leon J.S.: A probabilistic algorithm for computing minimum weights of large error-correcting codes. IEEE Trans. Inf. Theory 34(5), 1354-1359 (1988) · Zbl 0666.94017 [35] Loidreau P., Sendrier N.: Weak keys in the McEliece public-key cryptosystem. IEEE Trans. Inf. Theory 47(3), 1207-1211 (2001) · Zbl 0994.94029 [36] Loidreau P.: On cellular code and their cryptographic applications. In: Landjev I., Kabatiansky G. (eds.) Proceedings of ACCT14 (Algebraic and Combinatorial Coding Theory). Svetlogorsk, Russia (2014) [37] Löndahl C., Johansson T., Koochak Shooshtari M., Ahmadian-Attari M., Reza Aref M.: A New Attack on McEliece Public-Key Cryptosystems Using Quasi-cyclic Codes of Even Dimension (preprint) (2014) · Zbl 1402.94064 [38] Lyubashevsky L., Peikert C., Regev O.: On ideal lattices and learning with errors over rings. In: Gilbert H. (ed.) Advances in Cryptology—EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30-June 3, 2010. Proceedings. Lecture Notes in Computer Science, vol. 6110, pp. 1-23. Springer, Berlin (2010) · Zbl 1279.94099 [39] MacWilliams F.J., Sloane N.J.A.: The Theory of Error-Correcting Codes, 5th edn. Amsterdam, North-Holland (1986) · Zbl 0369.94008 [40] May A., Meurer A., Thomae E.: Decoding random linear codes in $$\tilde{O}(2^{0.054n})$$. In: Lee D.H., Wang X. (eds.) ASIACRYPT. Lecture Notes in Computer Science, vol. 7073, pp. 107-124. Springer, Berlin (2011) · Zbl 1227.94055 [41] McEliece R.J.: A Public-Key System Based on Algebraic Coding Theory, pp. 114-116. Jet Propulsion Lab. DSN Progress Report 44 (1978) [42] Misoczki R., Barreto P.S.L.M.: Compact McEliece keys from Goppa codes. In: Selected Areas in Cryptography (SAC 2009). Calgary, Canada, 13-14 August 2009 · Zbl 1267.94086 [43] Misoczki R., Barreto P.S.L.M.: Compact McEliece keys from Goppa codes. IACR Cryptology ePrint Archive, 2009:187 (2009) · Zbl 1267.94086 [44] Patterson N.: The algebraic decoding of Goppa codes. IEEE Trans. Inf. Theory 21(2), 203-207 (1975) · Zbl 0301.94016 [45] Persichetti E.: Compact McEliece keys based on quasi-dyadic Srivastava codes. J. Math. Cryptol. 6(2), 149-169 (2012) · Zbl 1277.94037 [46] Peters C.: Information-set decoding for linear codes over F$$_{\text{ q }}$$. In: Nicolas S. (ed.) PQCrypto. Lecture Notes in Computer Science, vol. 6061, pp. 81-94. Springer, Berlin (2010) · Zbl 1284.94101 [47] Sendrier N.: Finding the permutation between equivalent linear codes: the support splitting algorithm. IEEE Trans. Inf. Theory 46(4), 1193-1203 (2000) · Zbl 1002.94037 [48] Stehlé D., Steinfeld R., Tanaka K., Xagawa K.: Efficient public key encryption based on ideal lattices. In: Matsui M. (ed.) ASIACRYPT. Lecture Notes in Computer Science, vol. 5912, pp. 617-635. Springer, Heidelberg (2009) · Zbl 1267.94132 [49] Stern J.: A method for finding codewords of small weight. In: Cohen G.D., Wolfmann J. (eds.) Coding Theory and Applications. Lecture Notes in Computer Science, vol. 388, pp. 106-113. Springer, Heidelberg (1988)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.