The complexity of MinRank

DOI10.1007/978-3-030-77700-5_5MaRDI QIDQ5048630zbMATH OpenOpenAlexFDO

Authors Alessio Caminata, Elisa Gorla

Publication date 16 November 2022

Published in Association for Women in Mathematics Series (Search for Journal in Brave)

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

zbMATH Keywords

Castelnuovo-Mumford regularitydeterminantal idealsGröbner basesMinRank problemsolving degree

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Solving polynomial systems; resultants (13P15) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25) Applications to coding theory and cryptography of arithmetic geometry (14G50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Cryptography (94A60)

Abstract: In this note, we leverage some of our results from arXiv:1706.06319 to produce a concise and rigorous proof for the complexity of the generalized MinRank Problem in the under-defined and well-defined case. Our main theorem recovers and extends previous results by Faug`ere, Safey El Din, Spaenlehauer (arXiv:1112.4411).

Recommendations

• On the complexity of the generalized MinRank problem
• Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology
• Cryptanalysis of MinRank
• On the complexity of ``Superdetermined minrank instances
• The computational complexity of some problems of linear algebra

Cites work

• An algebraic approach for decoding spread codes
• An Asymptotically Optimal Structural Attack on the ABC Multivariate Encryption Scheme
• Cohen-Macaulay Rings, Invariant Theory, and the Generic Perfection of Determinantal Loci
• Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology
• Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic
• Determinantal rings
• scientific article; zbMATH DE number 1583768 (Why is no real title available?)
• scientific article; zbMATH DE number 1194481 (Why is no real title available?)
• scientific article; zbMATH DE number 1418284 (Why is no real title available?)
• Ideals defined by matrices and a certain complex associated with them
• Improved attacks for characteristic-2 parameters of the cubic ABC Simple Matrix Encryption scheme
• Improved cryptanalysis of HFEv- via projection
• Key recovery attack for all parameters of \(\mathrm{HFE}^-\)
• Key recovery attack for ZHFE
• On the complexity of the generalized MinRank problem
• On the computation of a-invariants
• Solving multivariate polynomial systems and an invariant from commutative algebra

Cited in

(9)

• Solving degree, last fall degree, and related invariants
• Solving multivariate polynomial systems and an invariant from commutative algebra
• On the complexity of ``Superdetermined minrank instances
• The complexity of solving Weil restriction systems
• Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology
• On the complexity of the generalized MinRank problem
• Cryptanalysis of symmetric primitives over rings and a key recovery attack on \textsf{Rubato}
• A new multivariate primitive from CCZ equivalence
• The complexity of the SupportMinors Modeling for the MinRank problem

This page was built for publication: The complexity of MinRank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5048630)