On the complexity of the generalized MinRank problem

DOI10.1016/j.jsc.2013.03.004zbMath1302.13026arXiv1112.4411OpenAlexW1985924702MaRDI QIDQ390388

Jean-Charles Faugère, Mohab Safey El Din, Pierre-Jean Spaenlehauer

Publication date: 8 January 2014

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1112.4411

zbMATH Keywords

Gröbner basisbi-homogeneousdeterminantalMinRankstructured algebraic systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Determinantal varieties (14M12) Cryptography (94A60) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Vector spaces, linear dependence, rank, lineability (15A03)

Related Items

Gröbner bases and critical values: the asymptotic combinatorics of determinantal systems, The Complexity of MinRank, A Secure Variant of the SRP Encryption Scheme with Shorter Private Key, Checking strict positivity of Kraus maps is NP-hard, Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic, Practical post-quantum signature schemes from isomorphism problems of trilinear forms, Real root finding for low rank linear matrices, Refined F5 Algorithms for Ideals of Minors of Square Matrices, Improvement of algebraic attacks for solving superdetermined MinRank instances, Real root finding for determinants of linear matrices, Algebraic relation of three MinRank algebraic modelings, Solving determinantal systems using homotopy techniques, Solving multivariate polynomial systems and an invariant from commutative algebra, Block-Krylov techniques in the context of sparse-FGLM algorithms, A new encryption scheme for multivariate quadratic systems, Exact Algorithms for Linear Matrix Inequalities, Solving parametric systems of polynomial equations over the reals through Hermite matrices

Uses Software

• Kronecker
• Magma

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Global optimization of polynomials restricted to a smooth variety using sums of squares
• Variant quantifier elimination
• Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree \((1,1)\): algorithms and complexity
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• The computational complexity of some problems of linear algebra
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• The Magma algebra system. I: The user language
• New technique for decoding codes in the rank metric and its cryptography applications
• On the geometry of polar varieties
• Polynomial evaluation and interpolation on special sets of points
• Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology
• Cryptanalysis of MinRank
• An inequality for Hilbert series of graded algebras.
• On the Hilbert Function of Determinantal Rings and Their Canonical Module
• Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices
• Introduction to Singularities and Deformations
• A class of perfect determinantal ideals
• Cohen-Macaulay Rings, Invariant Theory, and the Generic Perfection of Determinantal Loci
• A Gröbner free alternative for polynomial system solving
• Common tangents to four unit balls in \(\mathbb{R}^3\)