Welcome to the resource topic for 2011/570
Title:
Degree of regularity for HFE-
Authors: Jintai Ding, Thorsten Kleinjung
Abstract: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 q is even and r+a 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: \vskip .1in \begin{itemize} \item the complexity to break the HFE Challenge 2 directly using algebraic solvers is about 2^{96}. \end{itemize}
ePrint: https://eprint.iacr.org/2011/570
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .