Semi-Regular Sequences and Other Random Systems of Equations

DOI10.1007/978-3-030-77700-5_3zbMATH Open1504.13033arXiv2011.01032OpenAlexW4285540167MaRDI QIDQ5048628FDOQ5048628

Manuela Muzika Dizdarević, Emanuela De Negri, Sulamithe Tsakou, Romy Minko, Mina Bigdeli, Elisa Gorla

Publication date: 16 November 2022

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

Abstract: The security of multivariate cryptosystems and digital signature schemes relies on the hardness of solving a system of polynomial equations over a finite field. Polynomial system solving is also currently a bottleneck of index-calculus algorithms to solve the elliptic and hyperelliptic curve discrete logarithm problem. The complexity of solving a system of polynomial equations is closely related to the cost of computing Groebner bases, since computing the solutions of a polynomial system can be reduced to finding a lexicographic Groebner basis for the ideal generated by the equations. Several algorithms for computing such bases exist: We consider those based on repeated Gaussian elimination of Macaulay matrices. In this paper, we analyze the case of random systems, where random systems means either semi-regular systems, or quadratic systems in n variables which contain a regular sequence of n polynomials. We provide explicit formulae for bounds on the solving degree of semi-regular systems with m > n equations in n variables, for equations of arbitrary degrees for m = n+1, and for any m for systems of quadratic or cubic polynomials. In the appendix, we provide a table of bounds for the solving degree of semi-regular systems of m = n + k quadratic equations in n variables for 2 <= k; n <= 100 and online we provide the values of the bounds for 2 <= k; n <= 500. For quadratic systems which contain a regular sequence of n polynomials, we argue that the Eisenbud-Green-Harris Conjecture, if true, provides a sharp bound for their solving degree, which we compute explicitly.

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

zbMATH Keywords

multivariate cryptographyrandom systemsolving degreeGröbner basissemiregular sequence

Mathematics Subject Classification ID

Cryptography (94A60) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25) Hilbert-Samuel and Hilbert-Kunz functions; Poincaré series (13D40) Solving polynomial systems; resultants (13P15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Magma algebra system. I: The user language
• An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
• Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property
• Algorithmic Cryptanalysis
• Hybrid approach for solving multivariate systems over finite fields
• An inequality for Hilbert series of graded algebras.
• Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem
• The initial ideal of generic sequences and Fröberg's conjecture
• Syzygies of semi-regular sequences
• Generic sequences of polynomials
• Elliptic curve discrete logarithm problem over small degree extension fields
• On the existence of homogeneous semi-regular sequences in \(\mathbb{F}_2[X_1,\ldots,X_n]/(X_1^2,\ldots,X_n^2)\)
• On the minimal free resolution of $n+1$ general forms

Cited In (3)

• Development of hybrid approach for solving MQ problem: Intermediate hybrid approach
• On the first fall degree of summation polynomials
• The complexity of solving Weil restriction systems

Uses Software

• CoCoA
• Macaulay2
• Magma
• Mathematica

This page was built for publication: Semi-Regular Sequences and Other Random Systems of Equations

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