On the last fall degree of zero-dimensional Weil descent systems

DOI10.1016/J.JSC.2017.08.002MaRDI QIDQ1690789zbMATH OpenOpenAlexFDO

Authors Ming-Deh A. Huang, Michiel Kosters, Yun Yang, Sze Ling Yeo

Publication date 12 January 2018

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

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

zbMATH Keywords

zero-dimensionalpolynomial systemcryptographic protocolsfirst fall degreeWeil descentECDLPHFElast fall degreeGröbner basis

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Cryptography (94A60) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Solving polynomial systems; resultants (13P15)

Abstract: In this article we will discuss a new, mostly theoretical, method for solving (zero-dimensional) polynomial systems, which lies in between Gr"obner basis computations and the heuristic first fall degree assumption and is not based on any heuristic. This method relies on the new concept of last fall degree. Let $k$ be a finite field of cardinality $q^n$ and let $k^{\prime }$ be its subfield of cardinality $q$. Let $mathcalFsubsetk[X_0,ldots,X_{m-1}]$ be a finite subset generating a zero-dimensional ideal. We give an upper bound of the last fall degree of the Weil descent system of $mathcalF$, which depends on $q$, $m$, the last fall degree of $mathcalF$, the degree of $mathcalF$ and the number of solutions of $mathcalF$, but not on $n$. This shows that such Weil descent systems can be solved efficiently if $n$ grows. In particular, we apply these results for multi-HFE and essentially show that multi-HFE is insecure. Finally, we discuss that the degree of regularity (or last fall degree) of Weil descent systems coming from summation polynomials to solve the elliptic curve discrete logarithm problem might depend on $n$, since such systems without field equations are not zero-dimensional.

Recommendations

• On the last fall degree of Weil descent polynomial systems
• On polynomial systems arising from a Weil descent
• On the algebraic structure of Weihrauch degrees
• Weil descent of Jacobians
• First fall degree and Weil descent
• Solving degree, last fall degree, and related invariants
• Descent identities, Hessenberg varieties, and the Weil conjectures
• Zeros of systems of 𝔭-adic quadratic forms
• Constructive and destructive facets of Weil descent on elliptic curves
• Descent on elliptic surfaces and arithmetic bounds for the Mordell-Weil rank

Cites work

• scientific article; zbMATH DE number 3857249 (Why is no real title available?)
• scientific article; zbMATH DE number 2151220 (Why is no real title available?)
• A new efficient algorithm for computing Gröbner bases (F₄)
• Advances in Cryptology - CRYPTO 2003
• Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic
• Efficient algorithms for solving overdefined systems of multivariate polynomial equations
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Factoring polynomials over finite fields: A survey
• Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Inverting HFE Is Quasipolynomial
• Inverting HFE systems is quasi-polynomial for all fields
• Last fall degree, HFE, and Weil descent attacks on ECDLP
• On polynomial systems arising from a Weil descent
• On the discrete logarithm problem in elliptic curves
• On the relation between the MXL family of algorithms and Gröbner basis algorithms
• Polynomial maps on vector spaces over a finite field

Cited in

(11)

• Recent progress on the elliptic curve discrete logarithm problem
• First fall degree and Weil descent
• Stronger bounds on the cost of computing Gröbner bases for HFE systems
• Last fall degree, HFE, and Weil descent attacks on ECDLP
• Computing coupled border bases
• High-rank attack on HMFEv
• On the last fall degree of Weil descent polynomial systems
• Solving degree, last fall degree, and related invariants
• On product decomposition
• Recent developments in multivariate public key cryptosystems
• The complexity of solving Weil restriction systems

Describes a project that uses

Uses Software

• MutantXL

This page was built for publication: On the last fall degree of zero-dimensional Weil descent systems

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