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

DOI10.1016/J.JSC.2017.08.002zbMATH Open1391.13052arXiv1505.02532OpenAlexW1764529246MaRDI QIDQ1690789FDOQ1690789

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)

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.

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

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

zbMATH Keywords

[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Gr%EF%BF%BD%EF%BF%BDbner+basis&go=Go Gr��bner basis]zero-dimensionalpolynomial systemcryptographic protocolsfirst fall degreeWeil descentECDLPHFElast fall degree

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)

Cites Work

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

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

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)