TY - GEN
T1 - Cryptanalysis of MinRank
AU - Faugère, Jean Charles
AU - Levy-Dit-Vehel, Françoise
AU - Perret, Ludovic
PY - 2008/9/22
Y1 - 2008/9/22
N2 - 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 m3r/2 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 . For the challenge C [8], we obtain a theoretical bound of 266.3 operations.
AB - 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 m3r/2 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 . For the challenge C [8], we obtain a theoretical bound of 266.3 operations.
U2 - 10.1007/978-3-540-85174-5_16
DO - 10.1007/978-3-540-85174-5_16
M3 - Conference contribution
AN - SCOPUS:51849145057
SN - 3540851739
SN - 9783540851738
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 280
EP - 296
BT - Advances in Cryptology - CRYPTO 2008 - 28th Annual International Cryptology Conference, Proceedings
T2 - 28th Annual International Cryptology Conference, CRYPTO 2008
Y2 - 17 August 2008 through 21 August 2008
ER -