  The Rank Decoding problem (RD) is at the core of rank-based cryptography.
This problem can also be seen as a structured version of MinRank, which is
ubiquitous in multivariate cryptography. Recently, \cite{BBBGNRT20,BBCGPSTV20}
proposed attacks based on two new algebraic modelings, namely the MaxMinors
modeling which is specific to RD and the Support-Minors modeling which applies
to MinRank in general. Both improved significantly the complexity of algebraic
attacks on these two problems. In the case of RD and contrarily to what was
believed up to now, these new attacks were shown to be able to outperform
combinatorial attacks and this even for very small field sizes.
  However, we prove here that the analysis performed in \cite{BBCGPSTV20} for
one of these attacks which consists in mixing the MaxMinors modeling with the
Support-Minors modeling to solve RD is too optimistic and leads to
underestimate the overall complexity. This is done by exhibiting linear
dependencies between these equations and by considering an $\fqm$ version of
these modelings which turns out to be instrumental for getting a better
understanding of both systems. Moreover, by working over $\Fqm$ rather than
over $\ff{q}$, we are able to drastically reduce the number of variables in the
system and we (i) still keep enough algebraic equations to be able to solve the
system, (ii) are able to analyze rigorously the complexity of our approach.
This new approach may improve the older MaxMinors approach on RD from
\cite{BBBGNRT20,BBCGPSTV20} for certain parameters. We also introduce a new
hybrid approach on the Support-Minors system whose impact is much more general
since it applies to any MinRank problem. This technique improves significantly
the complexity of the Support-Minors approach for small to moderate field
sizes.
