Key Recovery Attack for All Parameters of HFE-

Recently, by an interesting confluence, multivariate schemes with the minus modifier have received attention as candidates for multivariate encryption. Among these candidates is the twenty year old HFE\(^-\) scheme originally envisioned as a possible candidate for both encryption and digital signatures, depending on the number of public equations removed.

HFE has received a great deal of attention and a variety of cryptanalyses over the years; however, HFE\(^-\) has escaped these assaults. The direct algebraic attack that broke HFE Challenge I is provably more complex on HFE\(^-\), and even after two decades HFE Challenge II is daunting, though not achieving a security level we may find acceptable today. The minors modeling approach to the Kipnis-Shamir (KS) attack is very efficient for HFE, but fails when the number of equations removed is greater than one. Thus it seems reasonable to use HFE\(^-\) for encryption with two equations removed.

This strategy may not be quite secure, however, as our new approach shows. We derive a new key recovery attack still based on the minors modeling approach that succeeds for all parameters of HFE\(^-\). The attack is polynomial in the degree of the extension, though of higher degree than the original minors modeling KS-attack. As an example, the complexity of key recovery for HFE\(^-(q=31,n=36,D=1922,a=2)\) is \(2^{52}\). Even more convincingly, the complexity of key recovery for HFE Challenge-2, an HFE\(^-(16,36,4352,4)\) scheme, is feasible, costing around \(2^{67}\) operations. Thus, the parameter choices for HFE\(^-\) for both digital signatures and, particularly, for encryption must be re-examined.

Authors and Affiliations

1. Department of Mathematics, University of Louisville, Louisville, KY, USA

   Jeremy Vates & Daniel Smith-Tone

2. National Institute of Standards and Technology, Gaithersburg, MD, USA

   Daniel Smith-Tone

Corresponding author

Correspondence to Daniel Smith-Tone .

Editors and Affiliations

1. Technische Universiteit Eindhoven, Eindhoven, The Netherlands

   Tanja Lange

2. Kyushu University , Fukuoka, Japan

   Tsuyoshi Takagi

A Toy Example

To illustrate the attack, we present a complete key recovery for a small odd prime field instance of HFE\(^-\). We simplify the exposition by considering a homogeneous key.

Let \(q=7\), \(n=8\), \(D=14\) and \(a=2\). We construct the degree n extension \(\mathbb {K}=\mathbb {F}_7[x]/\langle x^8+4x^3+6x^2+2x+3 \rangle \) and let \(b\in \mathbb {K}\) be a fixed root of this irreducible polynomial.

We randomly select \(f:\mathbb {K}\rightarrow \mathbb {K}\) of degree D,

and two invertible linear transformations T and U:

Since \(b^{1093971}/2=b^{4937171}\), we have

We fix \(\varPi :\mathbb {F}_q^8\rightarrow \mathbb {F}_q^6\), the projection onto the first 6 coordinates. Then the public key \(P=\varPi \circ T\circ F\circ U\) in matrix form over \(\mathbb {F}_q\) is given by:

1.1 A.1 Recovering a Related HFE Key

This step in key recovery is a slight adaptation of the program of [11]. First, we recover the related private key of Theorem 2. To do this, we solve the MinRank instance on the above \(6=n-2\) \(n\times n\) matrices with target rank \(\lceil log_q(D)\rceil +a=2+2=4\). We may fix one variable to make the ideal generated by the \(5\times 5\) minors zero-dimensional. There are \(n=8\) solutions, each of which consists of the Frobenius powers of the coordinates of

The combination \(L=\sum _{i=0}^5v_i\mathbf {P_i}\) is now a rank 4 matrix with entries in \(\mathbb {K}\).

We next form \(\widehat{v}\) from v by appending \(a=2\) random nonzero values from \(\mathbb {K}\) to v. Now we compute

Next we let \(K_i\) be the left kernel matrix of the \(n-i\)th Frobenius power of L for \(i=0,1,\ldots ,a+1\). We then recover a vector w simultaneously in the right kernel of \(K_i\) for all i. For this example, each such element is a multiple in \(\mathbb {K}\) of

Then we may compute

At this point we can recover \(\phi ^{-1}\circ f'\circ \phi =T'^{-1}\circ P\circ U'^{-1}\), and have a full private key for the related instance HFE(7, 8, 686). The transformations \(T'\) and \(U'\) and the matrix representation of \(f'\) as a quadratic form over \(\mathbb {K}\) are given by

1.2 A.2 Recovery of Equivalent HFE\(^-\) Key

Now we describe the full key recovery given the related HFE key. We know that there exists a degree \(D=14\) map \(f''(x)=f''_{0,0}x^2+2f''_{0,1}x^8+f''_{1,1}x^{14}\) with associated quadratic form

and a polynomial \(\pi (x)=x+p_1x^7+p_2x^{49}\) such that \(f'=\pi \circ f''\). Thus we obtain the bilinear system of equations by equating \(\mathbf {F'}\) to:

We clearly have the values of \(f''_{0,0}\) and \(f''_{0,1}\). Then the equations on the highest diagonal are linear in \(p_i\). We obtain \(\pi =x+b^{1948142}x^7+b^{398370}x^{49}\) and continue to solve the now linear system to recover \(f''(x)=b^{416522}x^2+b^{1559326}x^8+b^{1121420}x^{14}\).

We then obtain the matrix form of \(\pi \) over \(\mathbb {F}_q\) and compose with \(T'\):

Replacing the last two rows of \(T'\circ \widehat{\pi }\) to make a full rank matrix produces \(T''\). Then the original public key P is equal to \(\varPi \circ T''\circ \phi ^{-1}\circ f''\circ \phi \circ U'\).

Reprints and permissions

© 2017 Springer International Publishing AG (outside the US)

Policies and ethics