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

DOI10.1016/J.JSC.2020.07.011zbMATH Open1473.94100arXiv2011.01050OpenAlexW3041626971MaRDI QIDQ820971FDOQ820971

Authors: Elisa Gorla, Daniela Mueller, Christophe Petit 

Publication date: 29 September 2021

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

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.

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

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

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)

Cites Work

• The Magma algebra system. I: The user language
• 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
• Title not available (Why is that?)
• Advances in Cryptology - CRYPTO 2003
• A criterion for detecting m-regularity
• Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms
• Inverting HFE systems is quasi-polynomial for all fields
• On the last fall degree of zero-dimensional Weil descent systems
• Last fall degree, HFE, and Weil descent attacks on ECDLP

Cited In (4)

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

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)