Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Cryptanalysis of MinRank
verfasst von : Jean-Charles Faugère, Françoise Levy-dit-Vehel, Ludovic Perret
Erschienen in: Advances in Cryptology – CRYPTO 2008
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
$\mathcal{O}\left( \ln\left( q\right) \,n^{3\,r^{\prime2}}\right) $
. For the challenge C [8], we obtain a theoretical bound of 2
66.3
operations.