One of the central notions to understand how Hidden Field Equations work is to see that for two extension fields ${\displaystyle \mathbb {F} _{q^{n}}}$  ${\displaystyle \mathbb {F} _{q^{m}}}$  over the same base field ${\displaystyle \mathbb {F} _{q}}$  one can interpret a system of ${\displaystyle m}$  multivariate polynomials in ${\displaystyle n}$  variables over ${\displaystyle \mathbb {F} _{q}}$  as a function ${\displaystyle \mathbb {F} _{q^{n}}\to \mathbb {F} _{q^{m}}}$  by using a suitable basis of ${\displaystyle \mathbb {F} _{q^{n}}}$  over ${\displaystyle \mathbb {F} _{q}}$ . In almost all applications the polynomials are quadratic, i.e. they have degree 2.^[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 ${\displaystyle \mathbb {F} _{q}}$ , where ${\displaystyle q}$  is a power of 2, and an extension field ${\displaystyle K}$ . Let ${\displaystyle 0<h<q^{n}}$  such that ${\displaystyle h=q^{\theta }+1}$  for some ${\displaystyle \theta }$  and gcd${\displaystyle (h,q^{n}-1)=1}$ . The condition gcd${\displaystyle (h,q^{n}-1)=1}$  is equivalent to requiring that the map ${\displaystyle u\to u^{h}}$  on ${\displaystyle K}$  is one to one and its inverse is the map ${\displaystyle u\to u^{h'}}$  where ${\displaystyle h'}$  is the multiplicative inverse of ${\displaystyle h\ {\bmod {q}}^{n}-1}$ .

Take a random element ${\displaystyle u\in \mathbb {F} _{q^{n}}}$ . Define ${\displaystyle w\in \mathbb {F} _{q^{n}}}$  by

${\displaystyle w=u^{h}=u^{q^{\theta }}u\ \ \ \ (1)}$ 

Let ${\displaystyle \beta _{1},...,\beta _{n}}$  to be a basis of ${\displaystyle K}$  as an ${\displaystyle \mathbb {F} _{q}}$  vector space. We represent ${\displaystyle u}$  with respect to the basis as ${\displaystyle u=(u_{1},...,u_{n})}$  and ${\displaystyle w=(w_{1},...,w_{n})}$ . Let ${\displaystyle A^{(k)}={a_{ij}^{(k)}}}$  be the matrix of the linear transformation ${\displaystyle u\to u^{q^{k}}}$  with respect to the basis ${\displaystyle \beta _{1},...,\beta _{n}}$ , i.e. such that

${\displaystyle \beta _{i}^{q^{k}}=\sum _{j=1}^{n}a_{ij}^{k}\beta _{j},\ \ a_{ij}^{k}\in \mathbb {F} _{q}}$ 

for ${\displaystyle 1\leq i,k\leq n}$ . Additionally, write all products of basis elements in terms of the basis, i.e.:

${\displaystyle \beta _{i}\beta _{j}=\sum _{l=1}^{n}m_{ijl}\beta _{l},\ \ m_{ijl}\in \mathbb {F} _{q}}$ 

for each ${\displaystyle 1\leq i,j\leq n}$ . The system of ${\displaystyle n}$  equations which is explicit in the ${\displaystyle w_{i}}$  and quadratic in the ${\displaystyle u_{j}}$  can be obtained by expanding (1) and equating to zero the coefficients of the ${\displaystyle \beta _{i}}$ .

Choose two secret affine transformations ${\displaystyle S}$  and ${\displaystyle T}$  , i.e. two invertible ${\displaystyle n\times n}$  matrices ${\displaystyle M_{S}=\{S_{ij}\}}$  and ${\displaystyle M_{T}=\{T_{ij}\}}$  with entries in ${\displaystyle \mathbb {F} _{q}}$  and two vectors ${\displaystyle v_{S}}$  and ${\displaystyle v_{T}}$  of length ${\displaystyle n}$  over ${\displaystyle \mathbb {F} _{q}}$  and define ${\displaystyle x}$  and ${\displaystyle y}$  via:

${\displaystyle u=Sx=M_{S}x+v_{S}\ \ \ \ w=Ty=M_{T}y+v_{T}\ \ \ \ (2)}$ 

By using the affine relations in (2) to replace the ${\displaystyle u_{j},w_{i}}$  with ${\displaystyle x_{k},y_{l}}$ , the system of ${\displaystyle n}$  equations is linear in the ${\displaystyle y_{l}}$  and of degree 2 in the ${\displaystyle x_{k}}$ . Applying linear algebra it will give ${\displaystyle n}$  explicit equations, one for each ${\displaystyle y_{l}}$  as polynomials of degree 2 in the ${\displaystyle x_{k}}$ .^[3]

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

${\displaystyle {\text{input}}x\to x=(x_{1},...,x_{n}){\overset {{\text{secret}}:S}{\to }}x'{\overset {{\text{secret}}:P}{\to }}y'{\overset {{\text{secret}}:T}{\to }}{\text{output}}y}$ 

The private polynomial ${\displaystyle P}$  with degree ${\displaystyle d}$  over ${\displaystyle \mathbb {F} _{q^{n}}}$  is an element of ${\displaystyle \mathbb {F} _{q^{n}}[x]}$ . If the terms of polynomial ${\displaystyle P}$  have at most quadratic terms over ${\displaystyle \mathbb {F} _{q}}$  then it will keep the public polynomial small.^[1] The case that ${\displaystyle P}$  consists of monomials of the form ${\displaystyle x^{q^{s_{i}}+q^{t_{i}}}}$ , i.e. with 2 powers of ${\displaystyle q}$  in the exponent is the basic version of HFE, i.e. ${\displaystyle P}$  is chosen as

${\displaystyle P(x)=\sum c_{i}x^{q^{s_{i}}+q^{t_{i}}}}$ 

The degree ${\displaystyle d}$  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 ${\displaystyle d}$  slows down the deciphering. Since ${\displaystyle P}$  is a polynomial of degree at most ${\displaystyle d}$  the inverse of ${\displaystyle P}$ , denoted by ${\displaystyle P^{-1}}$  can be computed in ${\displaystyle d^{2}(\ln d)^{O(1)}n^{2}\mathbb {F} _{q}}$  operations.^[5]

The public key is given by the ${\displaystyle n}$  multivariate polynomials ${\displaystyle (p_{1},...,p_{n})}$  over ${\displaystyle \mathbb {F} _{q}}$ . It is thus necessary to transfer the message ${\displaystyle M}$  from ${\displaystyle \mathbb {F} _{q^{n}}\to \mathbb {F} _{q}^{n}}$  in order to encrypt it, i.e. we assume that ${\displaystyle M}$  is a vector ${\displaystyle (x_{1},...,x_{n})\in \mathbb {F} _{q}^{n}}$ . To encrypt message ${\displaystyle M}$  we evaluate each ${\displaystyle p_{i}}$  at ${\displaystyle (x_{1},...,x_{n})}$ . The ciphertext is ${\displaystyle (p_{1}(x_{1},...,x_{n}),p_{2}(x_{1},...,x_{n}),...,p_{n}(x_{1},...,x_{n}))\in \mathbb {F} _{q}^{n}}$ .

To understand decryption let us express encryption in terms of ${\displaystyle S,T,P}$ . Note that these are not available to the sender. By evaluating the ${\displaystyle p_{i}}$  at the message we first apply ${\displaystyle S}$ , resulting in ${\displaystyle x'}$ . At this point ${\displaystyle x'}$  is transferred from ${\displaystyle \mathbb {F} _{q^{n}}\to \mathbb {F} _{q^{n}}}$  so we can apply the private polynomial ${\displaystyle P}$  which is over ${\displaystyle \mathbb {F} _{q^{n}}}$  and this result is denoted by ${\displaystyle y'\in \mathbb {F} _{q^{n}}}$ . Once again, ${\displaystyle y'}$  is transferred to the vector ${\displaystyle (y_{1}',...,y_{n}')}$  and the transformation ${\displaystyle T}$  is applied and the final output ${\displaystyle y\in \mathbb {F} _{q^{n}}}$  is produced from ${\displaystyle (y_{1},...,y_{n})\in \mathbb {F} _{q}^{n}}$ .

To decrypt ${\displaystyle y}$ , the above steps are done in reverse order. This is possible if the private key ${\displaystyle (S,P,T)}$  is known. The crucial step in the deciphering is not the inversion of ${\displaystyle S}$  and ${\displaystyle T}$  but rather the computations of the solution of ${\displaystyle P(x')=y'}$ . Since ${\displaystyle P}$  is not necessary a bijection, one may find more than one solution to this inversion (there exist at most d different solutions ${\displaystyle X'=(x_{1}',...,x_{d}')\in \mathbb {F} _{q^{n}}}$  since ${\displaystyle P}$  is a polynomial of degree d). The redundancy denoted as ${\displaystyle r}$  is added at the first step to the message ${\displaystyle M}$  in order to select the right ${\displaystyle M}$  from the set of solutions ${\displaystyle X'}$ .^[1][3][6] The diagram below shows the basic HFE for encryption.

${\displaystyle M{\overset {+r}{\to }}x{\overset {{\text{secret}}:S}{\to }}x'{\overset {{\text{secret}}:P}{\to }}y'{\overset {{\text{secret}}:T}{\to }}y}$ 

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 ${\displaystyle f}$  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.^[1][2]

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 ${\displaystyle \mathbb {F} _{q^{n}}}$ . 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.^[1]

• 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, ISBN 3-540-00324-X