### Degree of regularity for HFE-

Jintai Ding and 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}

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
multivariatedegree of regularity
Contact author(s)
jintai ding @ gmail com
History
Short URL
https://ia.cr/2011/570

CC BY

BibTeX

@misc{cryptoeprint:2011/570,
author = {Jintai Ding and Thorsten Kleinjung},
title = {Degree of regularity for HFE-},
howpublished = {Cryptology ePrint Archive, Paper 2011/570},
year = {2011},
note = {\url{https://eprint.iacr.org/2011/570}},
url = {https://eprint.iacr.org/2011/570}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.