On the complexity of “superdetermined” Minrank instances

J Verbel, J Baena, D Cabarcas, R Perlner… - … 2019, Chongqing, China …, 2019 - Springer
J Verbel, J Baena, D Cabarcas, R Perlner, D Smith-Tone
Post-Quantum Cryptography: 10th International Conference, PQCrypto 2019 …, 2019Springer
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 …
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.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果