Stronger bounds on the cost of computing Gröbner bases for HFE systems

DOI10.1016/J.JSC.2020.07.011MaRDI QIDQ820971zbMATH OpenOpenAlexFDO

Authors Elisa Gorla, Daniela Mueller, Christophe Petit

Publication date 29 September 2021

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

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

zbMATH Keywords

multivariate cryptography(fake) Weil descentHFElast fall degreesolving degreeGröbner bases

Mathematics Subject Classification ID

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

Abstract: We give upper bounds for the solving degree and the last fall degree of the polynomial system associated to the HFE (Hidden Field Equations) cryptosystem. Our bounds improve the known bounds for this type of systems. We also present new results on the connection between the solving degree and the last fall degree and prove that, in some cases, the solving degree is independent of coordinate changes.

Recommendations

• The degree of regularity of HFE systems
• Advances in Cryptology - CRYPTO 2003
• Inverting HFE systems is quasi-polynomial for all fields
• Solving multivariate polynomial systems and an invariant from commutative algebra
• On the last fall degree of zero-dimensional Weil descent systems

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 criterion for detecting m-regularity
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• Advances in Cryptology - CRYPTO 2003
• Efficient algorithms for solving overdefined systems of multivariate polynomial equations
• Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms
• Inverting HFE systems is quasi-polynomial for all fields
• Last fall degree, HFE, and Weil descent attacks on ECDLP
• On the last fall degree of zero-dimensional Weil descent systems
• The Magma algebra system. I: The user language

Cited in

(4)

• Solving degree, last fall degree, and related invariants
• On product decomposition
• The degree of regularity of HFE systems
• Solving multivariate polynomial systems and an invariant from commutative algebra

Describes a project that uses

Uses Software

• Magma

This page was built for publication: Stronger bounds on the cost of computing Gröbner bases for HFE systems

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