Hidden Field Equations Public Key Crypto System

HFE stands for Hidden Fields Equations.

It is a public key cryptosystem using polynomial operations over finite fields. It has been proposed by Jacques Patarin at Eurocrypt 96 [IP1] following the ideas of Matsumoto and Imai [MCL,MG,MI,OBS]. It has long been regarded as the most promising cryptosystem of the kind. Recently Shamir with Kipnis and independently Courtois showed several advanced attacks on HFE. (later studied by Faugère and Joux, see below). Still, it is a promising public key cryptosystem with many practical applications: very fast or very short digital signatures, fast public key encryption, etc.

The principle of HFE is the following:

1. It is possible to find a solution of a univariate polynomial over a big finite field provided the degree d of the polynomial is not too big.

2. For some polynomial functions it is possible to represent them as n quadratic equations with n variables which hide the polynomial structure and makes it look quite as (almost) any other polynomial of any degree. In addition we make an initial and final affine variable changes. This idea is called ``Obscure Representation'' [OBS,DEA]. In follows the principle of ``disguising'' known from the Merkle and Hellman knapsacks and McEliece cryptosystem [MOV,SCH].