Paper 2019/731 Original: eprint.iacr.org/2019/731 ↗
On the Complexity of ``Superdetermined'' Minrank Instances
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.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2019-06-20: last updated
- 2019-06-20: published
- Short URL
- https://ia.cr/2019/731
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2019/731,
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},
url = {https://eprint.iacr.org/2019/731}
}