Degree of regularity for HFE-

Jintai Ding Southern Chinese University of Technology, Guangzhou, China; Department of Mathematical Sciences, University of Cincinnati, USA Thorsten Kleinjung EPFL IC LACAL, Lausanne, Switzerland

TBD mathscidoc:2207.43109

IACR Cryptol. ePrint Arch., 2011.10
In this paper, we prove a closed formula for the degree of regularity of the family of HFE- (HFE Minus) multivariate public key cryptosystems over a finite field of size q. The degree of regularity of the polynomial system derived from an HFE- system is less than or equal to \begin{eqnarray*} \frac{(q-1)(\lfloor \log_q(D-1)\rfloor +a)}2 +2 & & \text{if is even and is odd,} \\ \frac{(q-1)(\lfloor \log_q(D-1)\rfloor+a+1)}2 +2 & & \text{otherwise.} \end{eqnarray*} Here q is the base field size, D the degree of the HFE polynomial, r=\lfloor \log_q(D-1)\rfloor +1 and a is the number of removed equations (Minus number). This allows us to present an estimate of the complexity of breaking the HFE Challenge 2: \begin{itemize} \item the complexity to break the HFE Challenge 2 directly using algebraic solvers is about 2^{96}. \end{itemize}
No keywords uploaded!
[ Download ] [ 2022-07-21 15:03:36 uploaded by dingjt ] [ 16 downloads ] [ 0 comments ]
@inproceedings{jintai2011degree,
  title={Degree of regularity for HFE-},
  author={Jintai Ding, and Thorsten Kleinjung},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220721150336707304691},
  booktitle={IACR Cryptol. ePrint Arch.},
  year={2011},
}
Jintai Ding, and Thorsten Kleinjung. Degree of regularity for HFE-. 2011. In IACR Cryptol. ePrint Arch.. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220721150336707304691.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved