The Complexity of MinRank

DOI10.1007/978-3-030-77700-5_5zbMath1504.94111arXiv1905.02682OpenAlexW4210731756MaRDI QIDQ5048630

Elisa Gorla, Alessio Caminata

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

determinantal idealsGröbner basesCastelnuovo-Mumford regularitysolving degreeMinRank problem

Mathematics Subject Classification ID

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

Related Items (4)

Solving degree, last fall degree, and related invariants ⋮ Cryptanalysis of symmetric primitives over rings and a key recovery attack on \textsf{Rubato} ⋮ The complexity of solving Weil restriction systems ⋮ Solving multivariate polynomial systems and an invariant from commutative algebra

Cites Work

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

This page was built for publication: The Complexity of MinRank