Inverting HFE Systems is Quasipolynomial for all Fields

Jintai Ding and Timothy Hodges
South China University of Technology, Guangzhou, China + Department of Mathematical Sciences, University of Cincinnati, Ohio, USA; and Department of Mathematical Sciences, University of Cincinnati, Ohio, USA

Abstract. In this paper, we present and prove the first closed formula bounding the degree of regularity of an HFE system over an arbitrary finite field. Though these bounds are not necessarily optimal, they can be used to deduce

  1. if D, the degree of the corresponding HFE polynomial, and q, the size of the corresponding finite field, are fixed, inverting HFE system is polynomial for all fields;
  2. if D is of the scale O(nα) where n is the number of variables in an HFE system, and q is fixed, inverting HFE systems is quasi-polynomial for all fields.
We generalize and prove rigorously similar results by Granboulan, Joux and Stern in the case when q=2 that were communicated at Crypto 2006.