Details:
Title  The degree of regularity of HFE systems.  Author(s)  Vivien Dubois, Nicolas Gama  Type  Book, Chapter in Book, Conference Proceeding  Abstract  HFE 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.  Keywords  multivariate polynomials, HFE, algebraic cryptanalysis  ISBN  9783642173721/pbk 
URL 
http://link.springer.com/chapter/10.1007%2F9783642173738_32 
Language  English  Pages  557576  Publisher  Berlin: Springer  Year  2010  Edition  0  Translation 
No  Refereed 
No 
