Hidden Field Equations
Hidden Fields Equations (HFE), also known as HFE trapdoor function, is a public key cryptosystem which was introduced at Eurocrypt in 1996 and proposed by  Jacques Patarin following the idea of the Matsumoto and Imai system. It is based on polynomials over finite fields  of different size to disguise the relationship between the private key and public key. HFE is in fact a family which consists of basic HFE and combinatorial versions of HFE. The HFE family of cryptosystems is based on the hardness of the problem of finding solutions to a system of multivariate quadratic equations (the so-called MQ problem) since it uses private affine transformations to hide the extension field and the private polynomials. Hidden Field Equations also have been used to construct digital signature schemes, e.g. Quartz and Sflash.

Mathematical background 
One of the central notions to understand how Hidden Field Equations work is to see that for two  extension fields   over the same base field  one can interpret a system of  multivariate polynomials in  variables over  as a function  by using a suitable basis of  over . In almost all applications the polynomials are quadratic, i.e. they have degree 2. We start with the simplest kind of polynomials, namely monomials, and show how they lead to quadratic systems of equations.

Consider a finite field , where  is a power of 2, and an extension field . Let  such that  for some  and gcd. The condition gcd is equivalent to requiring that the map  on  is one to one and its inverse is the map  where  is the multiplicative inverse of . 

Take a random element . Define  by

Let  to be a basis of  as an  vector space. We represent  with respect to the basis as  and . Let  be the matrix of the linear transformation  with respect to the basis , i.e. such that

for .  Additionally, write all products of basis elements in terms of the basis, i.e.:

for each . The system of  equations which is explicit in the  and quadratic in the  can be obtained by expanding (1) and equating to zero the coefficients of the . 

Choose two secret affine transformations   and  , i.e. two invertible  matrices  and  with entries in  and two vectors  and  of length  over  and define  and  via:

By using the affine relations in (2) to replace the  with , the system of  equations is linear in the  and of degree 2 in the . Applying linear algebra it will give  explicit equations, one for each  as polynomials of degree 2 in the .

Multivariate cryptosystem 

The basic idea of the HFE family of using this as a  multivariate cryptosystem is to build the secret key starting from a polynomial  in one unknown  over some finite field  (normally value  is used). This polynomial can be easily inverted over , i.e. it is feasible to find any solutions to the equation  when such solution exist. The secret transformation either decryption and/or signature is based on this inversion. As explained above  can be identified with a system of  equations  using a fixed basis. To build a cryptosystem the polynomial  must be transformed so that the public information hides the original structure and prevents inversion. This is done by viewing the finite fields  as a vector space over  and by choosing two linear affine transformations  and . The triplet  constitute the private key. The private polynomial  is defined over . The public key is . Below is the diagram for MQ-trapdoor  in HFE

HFE polynomial 

The private polynomial  with degree  over  is an element of . If the terms of polynomial  have at most quadratic terms over  then it will keep the public polynomial small. The case that  consists of monomials of the form , i.e. with 2 powers of  in the exponent
is the basic version of HFE, i.e.  is chosen as

The degree  of the polynomial is also known as security parameter and the bigger its value the better for security since the resulting set of quadratic equations resembles a randomly chosen set of quadratic equations. On the other side large  slows down the deciphering. Since  is a polynomial of degree at most  the inverse of , denoted by  can be computed in  operations.

Encryption and decryption 
The public key is given by the  multivariate polynomials  over . It is thus necessary to transfer the message  from  in order to encrypt it, i.e. we assume that  is a vector . To encrypt message  we evaluate each  at . The ciphertext is .

To understand decryption let us express encryption in terms of . Note that these are not available to the sender. By evaluating the  at the message we first apply , resulting in . At this point  is transferred from  so we can apply the private polynomial  which is over  and this result is denoted by . Once again,  is transferred to the vector  and the transformation  is applied and the final output  is produced from .

To decrypt , the above steps are done in reverse order. This is possible if the private key  is known. The crucial step in the deciphering is not the inversion of  and  but rather the computations of the solution of . Since  is not necessary a bijection, one may find more than one solution to this inversion (there exist at most d different solutions  since  is a polynomial of degree d). The redundancy denoted as  is added at the first step to the message  in order to select the right  from the set of solutions . The diagram below shows the basic HFE for encryption.

HFE variations 

Hidden Field Equations has four basic variations namely +,-,v and f and it is possible to combine them in various way. The basic principle is the following:

01. The + sign consists of linearity mixing of the public equations with some random equations.
02. The - sign is due to Adi Shamir and intends to remove the redundancy 'r' of the public equations.
03. The f sign consists of fixing some  input variables of the public key.
04. The v sign is defined as a construction and sometimes quite complex such that the inverse of the function can be found only if some v of the variables called vinegar variables are fixed. This idea is due to Jacques Patarin.

The operations above preserve to some extent the trapdoor solvability of the function.

HFE- and HFEv are very useful in signature schemes as they prevent from slowing down the signature generation and also enhance the overall security of HFE whereas for encryption both HFE- and HFEv will lead to a rather slow decryption process so neither too many equations can be removed (HFE-) nor too many variables should be added (HFEv). Both HFE- and HFEv were used to obtain Quartz.

For encryption, the situation is better with HFE+ since the decryption process takes the same amount of time, however the public key has more equations than variables.

HFE attacks 

There are two famous attacks on HFE:

Recover the Private Key (Shamir-Kipnis): The key point of this attack is to recover the private key as sparse univariate polynomials over the extension field . The attack only works for basic HFE and fails for all its variations.

Fast Gröbner Bases (Faugère): The idea of Faugère's attacks is to use fast algorithm to compute a Gröbner basis of  the system of polynomial equations. Faugère broke the HFE challenge 1 in 96 hours in 2002, and in 2003 Faugère and Joux worked together on the security of HFE.

References 

 Nicolas T. Courtois, Magnus Daum and Patrick Felke, On the Security of HFE, HFEv- and Quartz
 Andrey Sidorenko, Hidden Field Equations, EIDMA Seminar 2004 Technische Universiteit Eindhoven
 Yvo G. Desmet, Public Key Cryptography-PKC 2003, 

Public-key encryption schemes
Finite fields
Multivariate cryptography