Solving multivariate polynomial systems and an invariant from commutative algebra

DOI10.1007/978-3-030-68869-1_1zbMath1478.13045arXiv1706.06319MaRDI QIDQ2232206

Elisa Gorla, Alessio Caminata

Publication date: 4 October 2021

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

zbMATH Keywords

Gröbner basis; Castelnuovo-Mumford regularity; multivariate cryptography; post-quantum cryptography; degree of regularity; generic coordinates; solving degree

Mathematics Subject Classification ID

68W30: Symbolic computation and algebraic computation

94A60: Cryptography

13P10: Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)

Related Items

The Complexity of MinRank, Self-dual Hadamard bent sequences, Quantum algorithm for Boolean equation solving and quantum algebraic attack on cryptosystems, Solving degree, last fall degree, and related invariants, Quantum security of grain-128/grain-128a stream cipher against HHL algorithm, The complexity of solving Weil restriction systems

Uses Software

• Magma
• MutantXL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of the generalized MinRank problem
• SimpleMatrix -- a multivariate public key cryptosystem (MPKC) for encryption
• A criterion for detecting m-regularity
• Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem
• Index calculus in the trace zero variety
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• The Magma algebra system. I: The user language
• Hilbert functions of irreducible arithmetically Gorenstein schemes.
• On the complexity of the \(F_5\) Gröbner basis algorithm
• Computational Linear and Commutative Algebra
• Solving Degree and Degree of Regularity for Polynomial Systems over a Finite Fields
• Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology
• The Degree of Regularity of HFE Systems
• Ideals defined by matrices and a certain complex associated with them
• The Geometry of Syzygies
• Degree of Regularity for HFEv and HFEv-
• Simple Matrix Scheme for Encryption
• The Complexity of MinRank
• Universal Gröbner Bases and Cartwright–Sturmfels Ideals
• Ideals, Varieties, and Algorithms
• Universal Grobner Bases for Maximal Minors