**A Family of Weak Keys in HFE (and the Corresponding Practical Key-Recovery)**

*Charles Bouillaguet and Pierre-Alain Fouque and Antoine Joux and Joana Treger*

**Abstract: ** The HFE (Hidden Field Equations) cryptosystem is one of the most
interesting public-key multivariate scheme. It has been proposed
more than 10 years ago by Patarin and seems to withstand the attacks
that break many other multivariate schemes, since only
subexponential ones have been proposed. The public key is a system
of quadratic equations in many variables. These equations are
generated from the composition of the secret elements: two linear
mappings and a polynomial of small degree over an extension field.
In this paper we show that there exist weak keys in HFE when the
coefficients of the internal polynomial are defined in the ground
field. In this case, we reduce the secret key recovery problem to an
instance of the Isomorphism of Polynomials (IP) problem between the
equations of the public key and themselves. Even though for schemes
such as SFLASH or $C^*$ the hardness of key-recovery relies on the
hardness of the IP problem, this is normally not the case for HFE,
since the internal polynomial is kept secret. However, when a weak
key is used, we show how to recover all the components of the secret
key in practical time, given a solution to an instance of the IP
problem. This breaks in particular a variant of HFE proposed by
Patarin to reduce the size of the public key and called the
``subfield variant''.

**Category / Keywords: **public-key cryptography / Cryptanalysis, multivariate cryptography, HFE, weak keys, Gröbner Bases

**Date: **received 15 Dec 2009

**Contact author: **charles bouillaguet at ens fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20091217:090005 (All versions of this report)

**Short URL: **ia.cr/2009/619

[ Cryptology ePrint archive ]