Paper 2019/731

On the Complexity of ``Superdetermined'' Minrank Instances

Javier Verbel, John Baena, Daniel Cabarcas, Ray Perlner, and Daniel Smith-Tone


The Minrank (MR) problem is a computational problem closely related to attacks on code- and multivariate-based schemes. In this paper we revisit the so-called Kipnis-Shamir (KS) approach to this problem. We extend previous complexity analysis by exposing non-trivial syzygies through the analysis of the Jacobian of the resulting system, with respect to a group of variables. We focus on a particular set of instances that yield a very overdetermined system which we refer to as ``superdetermined''. We provide a tighter complexity estimate for such instances and discuss its implications for the key recovery attack on some multivariate schemes. For example, in HFE the speedup is roughly a square root.

Available format(s)
Publication info
Published elsewhere. Minor revision. PQC2019
Contact author(s)
javerbelh @ unal edu co
2019-06-20: received
Short URL
Creative Commons Attribution


      author = {Javier Verbel and John Baena and Daniel Cabarcas and Ray Perlner and Daniel Smith-Tone},
      title = {On the Complexity of ``Superdetermined'' Minrank Instances},
      howpublished = {Cryptology ePrint Archive, Paper 2019/731},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.