MathSciDoc: An Archive for Mathematician ∫

 
Log In
Sign Up
Help
Go
 

Inverting HFE Systems Is Quasi-Polynomial for All Fields

Jintai Ding South China University of Technology, Guangzhou, China; Department of Mathematical Sciences, University of Cincinnati, Cincinnati, OH 45221-0025, USA Timothy J. Hodges Department of Mathematical Sciences, University of Cincinnati, Cincinnati, OH 45221-0025, USA

TBD mathscidoc:2207.43057

CRYPTO 2011, 724–742, 2011.8
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.
No keywords uploaded!
[ Download ] [ 2022-07-14 13:54:19 uploaded by dingjt ] [ 206 downloads ] [ 0 comments ] 
@inproceedings{jintai2011inverting,
  title={Inverting HFE Systems Is Quasi-Polynomial for All Fields},
  author={Jintai Ding, and Timothy J. Hodges},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220714135419674735634},
  booktitle={CRYPTO 2011},
  pages={724–742},
  year={2011},
}
Jintai Ding, and Timothy J. Hodges. Inverting HFE Systems Is Quasi-Polynomial for All Fields. 2011. In CRYPTO 2011. pp.724–742. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220714135419674735634.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved