Cryptology ePrint Archive: Report 2019/731
On the Complexity of ``Superdetermined'' Minrank Instances
Javier Verbel and John Baena and Daniel Cabarcas and Ray Perlner and Daniel Smith-Tone
Abstract: 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.
Category / Keywords: foundations / Minrank problem and Multivariate and Cryptanalysis and HFE
Original Publication (with minor differences): PQC2019
Date: received 19 Jun 2019
Contact author: javerbelh at unal edu co
Available format(s): PDF | BibTeX Citation
Version: 20190620:115230 (All versions of this report)
Short URL: ia.cr/2019/731
[ Cryptology ePrint archive ]