Structural cryptanalysis of McEliece schemes with compact keys
详细信息 查看全文
- 作者：Jean-Charles Faugère ; Ayoub Otmani ; Ludovic Perret…
- 关键词：Public ; key cryptography ; McEliece cryptosystem ; Algebraic cryptanalysis ; Folded code
- 刊名：Designs, Codes and Cryptography
- 出版年：2016
- 出版时间：April 2016
- 年：2016
- 卷：79
- 期：1
- 页码：87-112
- 全文大小：702 KB
- 参考文献：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)
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)
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)
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)
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)
8.Berger T.P.: Goppa and related codes invariant under a prescribed permutation. IEEE Trans. Inf. Theory 46(7), 2628 (2000)
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)
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
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)
12.Bernstein D.J., Lange T., Peters C.: Attacking and defending the McEliece cryptosystem. In: PQCrypto, pp. 31–46. (2008)
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)
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)
16.Buchberger B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. PhD thesis, Innsbruck (1965)
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)
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)
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)
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)
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)
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)
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]
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)
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)
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)
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)
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)
35.Loidreau P., Sendrier N.: Weak keys in the McEliece public-key cryptosystem. IEEE Trans. Inf. Theory 47(3), 1207–1211 (2001)
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)
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)
39.MacWilliams F.J., Sloane N.J.A.: The Theory of Error-Correcting Codes, 5th edn. Amsterdam, North-Holland (1986)
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)
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
43.Misoczki R., Barreto P.S.L.M.: Compact McEliece keys from Goppa codes. IACR Cryptology ePrint Archive, 2009:187 (2009)
44.Patterson N.: The algebraic decoding of Goppa codes. IEEE Trans. Inf. Theory 21(2), 203–207 (1975)
45.Persichetti E.: Compact McEliece keys based on quasi-dyadic Srivastava codes. J. Math. Cryptol. 6(2), 149–169 (2012)
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)
47.Sendrier N.: Finding the permutation between equivalent linear codes: the support splitting algorithm. IEEE Trans. Inf. Theory 46(4), 1193–1203 (2000)
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)
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) - 作者单位：Jean-Charles Faugère (1)
Ayoub Otmani (2)
Ludovic Perret (1)
Frédéric de Portzamparc (1) (3)
Jean-Pierre Tillich (4)
1. Sorbonne Universités, UPMC Univ Paris 06, POLSYS, CNRS, UMR 7606, LIP6, Inria, Paris-Rocquencourt Center, 75005, Paris, France
2. Normandie Univ, France, UR, LITIS, 76821, Mont-Saint-Aignan, France
3. Gemalto, 6 rue de la Verrerie, 92190, Meudon, France
4. Inria, Paris-Rocquencourt Center, 75005, Paris, France - 刊物类别：Mathematics and Statistics
- 刊物主题：Mathematics
Combinatorics
Coding and Information Theory
Data Structures, Cryptology and Information Theory
Data Encryption
Discrete Mathematics in Computer Science
Information, Communication and Circuits - 出版者：Springer Netherlands
- ISSN：1573-7586
文摘
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 (\(\mathrm{QC}\)), quasi-dyadic (\(\mathrm{QD}\)), or quasi-monoidic (\(\mathrm{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 \(\mathrm{QD}\)/\(\mathrm{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 \(\mathrm{QD}\) and \(\mathrm{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 \(\mathrm{QM}\) or \(\mathrm{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.