Cryptanalysis of MinRank

Abstract : In this paper, we investigate the difficulty of one of the most relevant problems in multivariate cryptography - namely MinRank - about which no real progress has been reported since [9, 19]. Our starting point is the Kipnis-Shamir attack [19]. We first show new properties of the ideal generated by Kipnis-Shamir's equations. We then propose a new modeling of the problem. Concerning the practical resolution, we adopt a Gröbner basis approach that permitted us to actually solve challenges A and B proposed by Courtois in [8]. Using the multi-homogeneous structure of the algebraic system, we have been able to provide a theoretical complexity bound reflecting the practical behavior of our approach. Namely, when r ′ the dimension of the matrices minus the rank of the target matrix in the MinRank problem is constant, then we have a polynomial time attack O(ln(q)n3r′2) . For the challenge C [8], we obtain a theoretical bound of 266.3 operations.
Type de document :
Communication dans un congrès
CRYPTO 2008 - 28th Annual International Cryptology Conference, Aug 2008, Santa Barbara, CA, United States. Springer, Advances in Cryptology – CRYPTO 2008, 5157, pp.280-296, 2008, Lecture Notes in Computer Science. 〈10.1007/978-3-540-85174-5_16〉
Liste complète des métadonnées

https://hal-ensta.archives-ouvertes.fr/hal-00976374
Contributeur : Aurélien Arnoux <>
Soumis le : mercredi 9 avril 2014 - 17:41:17
Dernière modification le : vendredi 25 mai 2018 - 12:02:04

Lien texte intégral

Identifiants

Collections

Citation

Jean-Charles Faugère, Françoise Levy-Dit-Vehel, Ludovic Perret. Cryptanalysis of MinRank. CRYPTO 2008 - 28th Annual International Cryptology Conference, Aug 2008, Santa Barbara, CA, United States. Springer, Advances in Cryptology – CRYPTO 2008, 5157, pp.280-296, 2008, Lecture Notes in Computer Science. 〈10.1007/978-3-540-85174-5_16〉. 〈hal-00976374〉

Partager

Métriques

Consultations de la notice

239