Inverting square systems algebraically is exponential

DOI10.1016/j.ffa.2013.10.004zbMath1288.94058OpenAlexW2067802270MaRDI QIDQ2637324

Jintai Ding, Roberto Araujo, Crystal Clough

Publication date: 11 February 2014

Published in: Finite Fields and their Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ffa.2013.10.004

zbMATH Keywords

squaredegree of regularityHFE

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Applications to coding theory and cryptography of arithmetic geometry (14G50) Solving polynomial systems; resultants (13P15) Quantum cryptography (quantum-theoretic aspects) (81P94)

Related Items (2)

Efficient key recovery for all HFE signature variants ⋮ A Multivariate Encryption Scheme with Rainbow

Uses Software

• MXL3

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Degree of Regularity of HFE Systems
• Algebraic Attack on HFE Revisited
• Secure Variants of the Square Encryption Scheme
• MXL3: An Efficient Algorithm for Computing Gröbner Bases of Zero-Dimensional Ideals
• Square, a New Multivariate Encryption Scheme
• Cryptanalysis of the Square Cryptosystems
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Inverting HFE Systems Is Quasi-Polynomial for All Fields
• Information Security and Privacy
• Advances in Cryptology - CRYPTO 2003
• Inverting HFE Is Quasipolynomial

This page was built for publication: Inverting square systems algebraically is exponential