Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleCryptanalysis of MinRank.
Author(s) Faug`ere Jean-Charles, Franc coise Levy-Dit-Vehel, Ludovic Perret
TypeBook, Chapter in Book, Conference Proceeding
AbstractIn 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 (ln(q)n3r′2). For the challenge C [8], we obtain a theoretical bound of 266.3 operations.
URL http://link.springer.com/chapter/10.1007%2F978-3-540-85174-5_16
PublisherBerlin: Springer
Translation No
Refereed No