## JMI2012B-3 Degree of regularity for HFE Minus (HFE-) (pp.97-104)

Author(s)： Jintai Ding and Thorsten Kleinjung

J. Math-for-Ind. **4B** (2012) 97-104.

- File： JMI2012B-3.pdf (141KB)

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{array}{rl}

\dfrac{(q-1)(\lfloor \log_q(D-1)\rfloor +a)}2 +2 &

\text{if $q$ is even and $r+a$ is odd,}

\\

\dfrac{(q-1)(\lfloor \log_q(D-1)\rfloor+a+1)}2 +2 &

\text{otherwise.}

\end{array}

\]

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:

$\bullet\ $ the complexity to break the HFE Challenge 2 directly using algebraic solvers is about $2^{97}$.

Keyword(s). HFE, degree of regularity, Minus