Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleThe degree of regularity of HFE systems.
Author(s) Vivien Dubois, Nicolas Gama
TypeBook, Chapter in Book, Conference Proceeding
AbstractHFE is a public key scheme introduced by Patarin in 1996. An HFE public key is a large system of polynomials in many variables over a small finite field. This system results from some secret composition, based on which the owner can solve it to any arbitrary vector. While the security of the cryptosystem relies on the difficulty of solving the public system without the trapdoor information, in 2002 Faugére found experimentally that Gröbner basis computations perform much better on certain HFE instances than on random systems. More specifically, Faugére observed that the regular behaviour of the Gröbner basis computation collapses at a much lower degree than expected for random systems, letting the computation finish much earlier. Accounting for this distinctive property, Faugére and Joux showed in 2003 that mapping HFE systems to some other multivariate ring exhibits the particular algebraic structure of these systems. Nevertheless, they did not offer the actual computation of the degree of regularity of HFE systems. Later, in 2006, Granboulan, Joux and Stern showed an asymptotic upper bound on the degree of regularity of HFE systems over GF(2) using independent results on overdetermined systems of equations. The case of larger ground fields has remained however completely unsolved. In this paper, we exhibit an additional property of HFE systems that is increasingly significant as the size of the ground field grows. Using this property with a standard combinatorial calculation yields an arguably tight numerical bound on the degree of regularity of HFE systems for any parameters.
Keywordsmultivariate polynomials, HFE, algebraic cryptanalysis
URL http://link.springer.com/chapter/10.1007%2F978-3-642-17373-8_32
PublisherBerlin: Springer
Translation No
Refereed No