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 (only 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].

The HFE polynomial is of the form

f(a)=\sum_i \alpha_{i} a^{q^{s_i}+q^{t_i}. (why ?)

given K=GF(q),
the \alpha_i are random coefficients in K^n taken for all possible powers of the form
a^{q^{s_i}+q^{t_i} are not greater than a given maximum power a^d.

d is one of security parameters. Greater is better (reasons 1,2,) but it slows down the deciphering. It seems optimal to choose d of the form 2^k+1 (see why). Recommended values.

Example: a+a^3+a^5 is such a polynomial for p=2, d=5.

A nice introduction to finite fields exists on the web. A simple book is [ROS].

The simplest finite field is a prime field K=GF(q) with q prime. It is implemented with integers 0..q-1, addition and multiplication are made modulo q. Division can be made using the formula x^{-1}=x^{q-2} or (better) with the extended Euclidean algorithm.
The extended Euclidean algorithm can be found in any book with integer algorithms, see for example [ROS] or [MOV].

Let K=GF(q) be a finite field. Therefore q=p^m and p is the field characteristic. We see K^n=GF(p^mn) operations as a vector space of dimension mn over GF(p).

Let P(X) be a irreducible polynomial of degree nm over GF(p). Then the polynomial ring GF(p) [X]/P(X) is a field (isomorphic to GF(q^n)). It is also a vector space of dimension nm over GF(p), and we simply write K^n=GF(p)[X]/P(X). We denote the elements of K^n by polynomials of degree at most nm-1 on which we implement addition/multiplication operations modulo P(X). Such polynomial is simply written as a string of nm elements of GF(p). This representation allow us to see K^n as a vector space of dimension n over K, decomposing it into m-element substrings of the nm-long string. Internal subfield K operations are unique and obvious if m=1, otherwise they can be implemented using any irreducible polynomial of degree m over GF(p).

How to find an irreducible polynomial ?
It's explained in any book about finite fields, coding, or cryptography. Florent Chabaud made a web page about it. We can also use the MAPLE command Randprime(degree,X) mod p, however it's nice to pick up a trinomial in order to speed up the finite field operations, see [MOV], page 158.

Example: We put q=p=2 (m=1) and K=GF(2)={0,1,+,x} which makes algebraic operations on K elements very simple. Let n=3. We pick up P(X)=X^3+X^2+1. The polynomial ring GF(p)[X]/P(X) can be represented as the set of polynomials of degree at most 2 over K with the addition and multiplication made modulo X^3+X^2+1 . Such polynomials can be represented written as binary strings of length 3. and we identify frequently GF(p)[X]/P(X) and K^3.

Remarks: The fact that X^3+X^2+1 has no proper dividers implies that 0 has no dividers in GF(p)[X]/P(X) and it makes GF(p)[X]/P(X) a field. It is isomorphic to GF(2^3) as all finite fields of given cardinal are isomorphic.

Speed-up: For all finite fields, if q is small we can achieve an ultimate speed-up if we precompute the complete multiplication table (and eventually multiplicative inverses).

If you are lost, try this book [ROS]. It includes all the maths you need here in an accessible form with a lot of ready C-programs (!), especially for the Galois fields GF(2^n).

Now we consider polynomials over the extension field K^n. Let b=f(a) be a polynomial of degree d.
We call this degree the univariate degree. f can also be written as multivariate set of polynomials. We write
b = b_(n-1)X^(n-1) +.. + b_1X + b_0 =
=f(a) = f( a_(n-1)X^(n-1) +.. + a_1X + a_0 )
and then we express each b_i as polynomial equations of the a_i written in K:

b_i=f_i(a_n-1,..a_0)

These equations have a distinct degree, in general not greater than d, which is called the multivariate degree or the nonlinear order of f. It comes from the fact that in a field of characteristic p some powers are linear transformations. For instance we have
(a+b)^(p^t) = (a)^(p^t)+(b)^(p^t)
for all a,b in K^n. Therefore for all the polynomials of the form
f(a)=a^(p^t)
the b_i=f_i(a_1..a_n) are additive functions.
However we need to take
f(a)=a^(q^t)
and only then they become K-linear functions of the a_i.
Then for all the monomials of the form
f(a)=a^(q^s+q^t)
the f_i are quadratic (over K ). HFE polynomial is a sum of such terms:

f(a)=\sum_i \alpha_{i} a^{q^{s_i}+q^{t_i}, with \alpha_{i} in K^n.

Example: Let's have a look at the function a -> a+a^3+a^5. We have
b=f(a)=a+a^3+a^5=(a_2X^2+a_1X+a_0)+(a_2X^2+a_1X+a_0)^3+(a_2X^2+a_1X+a_0)^5 mod (X^3+X^2+1)=
(a_2+a_2a_1+a_2a_0+a_1)X^2+(a_2a_1+a_1a_0+a_2)X+(a_0+a_2+a_1a_0+a_2a_0)

As promised by the theory, the b_i are quadratic in the a_i:

b_2=a_2+a_2a_1+a_2a_0+a_1
b_1=a_2a_1+a_1a_0+a_2
b_0=a_0+a_2+a_1a_0+a_2a_0

f has the univariate degree 5 and multivariate degree (nonlinear order) 2.

We use the polynomial f generated as above.
We generate 2 random affine variable changes with coefficients in K:

input transformation:
S: {a_i = \gamma_ij x_i + \beta

output transformation:
T: {y_i = \gamma'_ij b_i + \beta'

Then we compose g = T o f o S.

Our public key is g (it's expression as quadratic multivariate forms). Size considerations.

The secret key is the triplet (S,f,T). It allows to compute g^{-1}.

We simply use the public quadratic forms g.
Some redundancy must be added before encryption, so we could chose the good solution, as the HFE polynomial is not one-to-one in general (why ?).
As always in public key cryptography it is possible to use a secret key cryptosystem with a session key and encrypt this session key with the public key. This solution is advised for the HFE if we need to speed the decryption. However the HFE encryption is very fast alone. It can be used to encrypt the text blocks directly in either ECB, CBC mode. The CFB and OFB modes are obviously not suitable as they use only g, not g^{-1}. In ECB/CBC modes, the fact the decryption process is slow can be an advantage as it can slows down the attacks too.

We have put g = T o f o S.

It allows to compute g^{-1} = S^{-1} o f^{-1} o T^{-1}.

Therefore for the holder of the secret key it's enough to know how to compute f^{-1}.
This is possible as long as d is not too big.
Many algorithms exist [GSF,IP4,MOVF,OVF,IP1], or [MOV] pages 122-124.
The complexity in d of these algorithms is par example mn^3d^2log(d) in GF(q) operations.
The operations are not very fast but can still be implemented on a PC. We run various experiments using the library NTL by Victor Shoup. Here is my code using NTL that proved to be the fastest way to find a root (it finds only one).

With this program I've been able to get on a Pentium-III-500 the following results:
HFE GF(2) n=80, d=96, 1.20 s
HFE GF(2) n=128, d=25, 0.17 s, HFE GF(2) n=128, d=129, 3.40 s
HFE GF(2) n=256, d=25, 0.44 s, HFE GF(2) n=256, d=96, 7.42 s
more results

The simplest way to do it is to have a message digest a bit shorter that the HFE block size n. Padding with 4-8 bits is fairly enough as the probability of a value not being an HFE possible output is very close to 1/e for a random quadratic form and quite close to it in real cases [DEA]. If there are few possible signatures we choose one at random.
To verify the signature we simply use the public forms and cast the padding.

Some more advanced methods of signing are described in [IP1]. They use several HFE decryptions and allow to produce signatures as short as 128, 100 and even 80 bits. HFE gives the shortest (unbroken) signatures known except with the recent McEliece signature scheme.

The Quartz signature scheme applies HFE with many improvements in order to give 128 bit long signatures with a security that is expected to last for 20 years.
In a recent paper Generic attacks and provable security of Quartz, to be presented at the Nessie workshop, September 13th 2001, 09h40, Queen's Building Lecture Theatre, Royal Holloway, University of London, partial security proofs for Quartz are given. Download the full paper.

The public key size for basic HFE is n (1+n+n(n-1)/2+n(q>2)).
Examples for q=2:

• n=80 - 31.6 kb
• n=128 - 129 kb
• n=256 - 1 Mb
• n=1024 - 64 Mb

The key size for a fixed block length (nlog(q)) can be reduced about (log_2 q)^2 times if we consider bigger q.
Examples with q=16:

• 80 bits - 2310 bytes
• 128 bits - 9 kb
• 256 bits - 67 kb
• 1024 bits - 4 Mb

The secret key size is about 2n^2 and it is not a problem compared to the public key.
It could be reduced, but some kind of boosting attack might work then...

Bigger q, as explained above allows to reduce the key size with a fixed block size. The computations made by the author ([CHFE]) show that it increases the degree d of the polynomial needed to achieve the same level of security. Therefore for the same the security level d increases and secret key operations are slower.

In the light of recent attacks on HFE we do not recommend any such improvement. Even if d is quite big, if public equations can be expressed as a smaller number of quadratic equations over a bigger field, there is a very serious threat of the relinearization attack. The complexity of relinearization depends on the number of unknowns and equations not on the size of inputs or outputs.

1. Public key is quite big, but who knows ... it could turn out to be an advantage.

For the McEliece cryptosystem [MOV,SCH] it is even worse, and the recent McEliece signature scheme key size is as big as 1.125 Mb compared to 70 kb for Quartz.

2. Secret key operations are quite slow. They can be carried on a PC but hardly on a low-end smart card.

3. Finally, a somewhat technical problem is that in general the encryption function is not surjective and can have few pre-images. The first is a problem for signing, the second for encryption. Both problems can be solved by adding some random bits. There is little hope to construct a one-to-one HFE encryption that resist to attacks.

1. Complexity theory: the encryption function of the HFE tends to a random quadratic system if d is big enough (folklore theorem).
The problem of solving a random quadratic form is NP-complete. (which has been showed in the appendix of [IPC] and means nothing in particular).

In practice there is no method considerably faster that the exhaustive search known to solve it.

2. Now several very advanced attacks are known on HFE. All of them seem to have about the same subexponential asymptotic complexity, and it seems unlikely to become polynomial.

3. In practice the HFE Challenge 1 is nearly broken. However even for small n values HFE attacks are still very difficult. HFE gives one of the shortest unbroken signatures available that can only be compared to the recent McEliece signature scheme.

4. Other arguments in favour of the HFE: 1/2/3 ..

Probably not.

I have never seen a one-to-one polynomial over a finite field with big degree and with many monomials and in addition having small non-linear degree as 2 or 3. Big degree polynomials with little monomials behave the same way as small degree polynomials for the reasons that become obvious if we use normal bases described in [MOV] p.642.

Some argumentation against the existence of one-to-one strong functions is also developed in [appendix of IP4] and [BRA].

1. One can try to recover f first and then try to find S and T (IP problem [IP6]). No way to recover f or any part of it is known.
However Shamir and Kipnis have observed that if f univariate degree d is small, that in a way most of it is known, as all the higher degree coefficients are 0.
This is a starting point of the Shamir-Kipnis attack. See this paper to see if it really works.

2. Other attacks hope to compute g^{-1} without recovering the secret key:
2.1. So does the Implicit Equations attack and it's improved versions. They are realistic for d<=24 and experimented up to d=96 (more details or [CHFE]).
2.2. Algorithms to do that based on the Grobner bases and their generalizations doesn't work for big n (folklore).
2.3. Interpolation. One can try to approximate g or g^{-1} directly by an univariate polynomial over K^n and hope one of them has a small degree. This attack can be further generalized and still it fails [CHFE]. Even for the weakest existing HFE polynomial x->x^3 [DEA,IPC,IP1,IP1].

3. An attack on the message schedule is possible in special circumstances, see below.

4. Attacks on the key schedule are very likely, at least if parts of the secret key have small entropy. See below.

5. Bogus attack: It is easy to find collisions on the HFE encryption [DEA,IP6]. However it is not a weakness at all as it does not allow to counterfeit anything at all. This is the decryption and not the encryption function which is used to compute a signature.

Attacks that do not use the internal structure: XL algorithm and versions, Grobner bases, etc... [Courtois, Patarin, Shamir and Klimov 2000]

Shamir-Kipnis attack [Shamir and Kipnis 99]

The attack is described in the paper [SHFK] that can be be directly downloaded. See this paper to see if it really works.

WARNING: this text is out of date, see this paper.

Shamir-Kipnis attack consistst of 2 components A, B:
A. We transform a small system of marginally defined quadratic equations into a huge system with much more equations that unknowns.
B. This can of systems can be solved (but producing even more astronomic size equations).
Some remarks (outdated):
A. First transform HFE to a huge but overdefined system of quadratic equations.

Adi Shamir came to France and give us a very nice talk about their attack. The reason why the main weak point of the HFE has not been understood so far is that nobody has tried to write the public equations in the form a single sparse equations over the big field K^n. When we write such a representation, we may represent a system of n quadratic equations with n variables over K as a nxn symmetric matrix over K^n.
It is called a non standard representation of a quadratic system and is fully described in [SHFK]. The authors study the effect of the linear S and T transformations on this particular representation. They prove that for any transformation S the matrix has a low rank that comes form the fact that the secret univariate polynomial f has a small degree. The conclusion is that T^{-1} has a special property that makes the rank of the matrix representation of T^{-1}(g) suddenly collapse.
This property is used to write linear equations in the t_i that give in a matrix of a small rank. Then the condition of a small rank is expressed as an existence of large space of kernel elements that are also variables to be find. All this combined gives an immense set of n*(n-r) quadratic equations over the r(n-r)+n variables.
It is still a system of quadratic equations to solve, but this one is overdefined, i.e. it has much more equations that unknowns.

B. Solve..

Initially the paper [SHFK] proposed to solve the equations by so called linearization. It proved to be a bad idea. In a recent paper it has been shown that the relinearization technique can be improved and leads to an algorithm called XL. XL itslef can be considered to be a simple version of Gröbner bases and is the kind of techniques that are widely used for at least 20 years. As for the HFE attacks, it gives still 2^152 to break the challenge 1 while the exhaustive search is in 2^80. Still, linearization was a breaktrough discovery, because it has shown that overdefined systems are likely to be solved in subexponential time.It seems that people who has been programming Gröbner bases has never tried how it works on a finite filed when the number of equations exceeds slightly the number of unknowns.
A better idea to implement the Shamir-Kipnis attack is the following:

Shamir-Kipnis attack revisited by Courtois. [99]

It is possible to break HFE only with A part and without B (relinearization part or XL).
Instead we express the rank condition of the matrix in terms of determinants of it's submatrices and observe that the system is largely overdefined and easily solved, for more details see [CHFE] or the Courtois PhD thesis (quite out of date now). This simple remark behaves dramatically better that the relinearization: 2^82 to break the Challenge 1 instead of 2^152.

Implicit Equations Attacks. [Patarin, Courtois 1996-99]
It is series of attacks that generalize one another:

Affine Multiple attack. [Patarin 1996] Works for HFE degree d<=4.

An amazing cryptanalysis of the Matsumoto-Imai cryptosystem [DEA,MG,MI,MCL,IP1] by Jacques Patarin uses bilinear equations in the input and output bits x_i and y_i. One such equation, if exists, can be found out, and when substituted with an output y value, it gives linear equations on the unknowns x_i.

Higher degree implicit equations [Patarin, Courtois]. Works for HFE degree d<=4.
Naturally, equations of higher degrees have been studied then. However it does not work better, because there are never enough such independent equations. [CHFE,IP1]

Boosting attack using implicit equations. [Courtois 98] Works for HFE degrees d<=16, and more in theory.
The idea is to use the above equations is to iterate the attack. It works better, but is not very practical [CHFE] and lead to very huge equations. It was the first complete attack on HFE that seems to work for any degree (provided unrealistic resources).

Biased equations attack. [Courtois 99]. Feasible for about d<=24.
The next idea was to go back to one-pass attack and use bigger equations at the beginning.
We can then show that existence of a big number of equations, implies the existence of a small number of so called ``biased'' equations that have nice properties.
The most important property of these equations is that even few of them are directly used to break the cryptosystem, see [CHFE].

Reconciliation attack. [Courtois 99]. More practical for d<=24 and more.
The ``biased'' equations have other nice properties. They can be used in cryptanalysis without computing them, we only need to recover parts of them. It helped to reduce the complexity of attacks, especially in memory. For details see [CHFE].

Distillation attack. [Courtois 99] Tested to work up to d<=96 provided important computing power (see below ).

In this attack not only we use parts of the ``biased'' equations, but we manage to use parts so small that the parts of the equations are not well defined. It is possible to eliminate such interferences. In this way we further reduce the complexity of the attacks. It allowed us to propose;

New (not really)attacks by Faugère and Joux.
A new paper was presented at Crypto 2003, see [FaugJouxHfe].
The authors did not discover any new attack and the paper does not go beyond the reconcilliation attack described above. However, this paper is the first to explain WHY the equations discovered first by Courtois [CHFE] do exist, and to show how to predict their number (only approximatively). It is an important breakthrough in attacking HFE.

The first realistic attack on the 500 $ HFE Challenge 1.

It requires a 1-2 Gigabytes of RAM, 390 Gb of disk space, and about C*2^{50}CPU clocks. For details see [CHFE]. We have implemented this attack and tested it to work on smaller examples.

Boosting Attack [Courtois 1997]. Knowing parts of the secret key proves to be insecure in most cases. It is certainly insecure if f univariate representation is completely known. Several ``boosting'' phenomena has been discovered (see [DEA] and [IP6]). Boosting consists of starting with some initial knowledge of a part of S or T and allows to get more information on it. The problem of recovering completely S and T knowing only f and g is called IP and has been studied carefully in [DEA] then in [IP6]. It can be done in q^{n/2} which makes an 80 bits HFE with known (public) f insecure.

Multiple-user single-message attack [Courtois 1997]. This attack allows to recover a message which is encrypted by at least n/2 users using different public keys, see [DEA] . It is really obvious, we do simple linearization of all the public equations: they are linear in the new variables y_ij=x_i x_j. And it is serious because even if the above condition of n/2 does not happen very often, if a message is encrypted by a smaller number of public keys, we still may expect that the Shamir-Kipnis relinearization technique could recover the message on a big computer.

Both Shamir-Kipnis-Courtois attack (does it work? see this paper) and the best implicit equations attacks [Courtois] (that works) appear to have the same asymptotic complexity:

O(n^log d)

which, knowing that d is polynomial in n
is about
e^(log^2 n)
See [CHFE] and [SHFK] for details.

We can compare it to the NFS complexity for breaking RSA, which is about e^(n^{1/3}) with n being the input size. Obviously the complexity of RSA is better in theory, still in practice HFE 80 bits is about as secure as RSA 512 bits.

q We recommend to use q=2.

n In general we recommend at least n=127 not so much to avoid meet-in-the middle attacks on n, as they can be avoided by the signature scheme alone [IP1], but the distillation attack threatens smaller values [CHFE].We also recommend for n to be a prime to avoid attacks that might be found using a subfield.

d In general we recommend d of the form (2^k)+1. The simulations made in [CHFE,IP1] show that there is a security ``bond'' between 2^k and (2^k)+1 whereas the speed of the secret key operations remains quite the same.

Other simulations has shown that it's better to increase n rather than to increase d, in order to keep secret key operations not too slow. So we recommend d>=129. if n is small, e.g. n=64. However if n>= 127 even d=25-33 is big enough.

For basic HFE, a secure implementation, quite out-of-range of all known attacks, and still not too slow should have q=2, n=251, d=25.

The modified versions of HFE such as HFEv or HFEv-, are expected to be much more secure and with much smaller parameters. For example for the Quartz signature scheme that has a claimed security level of 2^80, there is no method known to distinguish the underlying system of quadratic equations from a randomly selected system without a trapdoor in less than 2^(n^2) >> 2^80. All attacks known on Quartz are generic attacks on any function that are in 2^80 because of the output size.

If there are no major breaktroughs, we expect that MOST of the modified versions of HFE will NEVER be broken by anything better that the exhaustive search.

Now, with all the advanced attacks, we see that even basic HFE has some security (modified versions are much better).
In [SCH] Bruce SCHNEIER writes: ``Any algorithm that gets it's security from the composition of polynomials over the finite field should be looked upon with skepticism, if not outright suspicion.'' These words seem motivated by methods for factoring polynomials and were written before the HFE proposal in 1996.
The HFE has not been broken for 4 years now and we recommend the challenges to everyone.
In the same book [SCH], on the next page we read: ``This narrowness in the mathematical foundations of public-key cryptography is worrisome.'' Instead of worrying try to adopt HFE (possibly a strengthened version), or try to break it ...

With the current knowledge on HFE and it's reduction to a very difficult decoding problem MinRank we believe that HFE will never be broken in polynomial time. We also expect that at least some modified versions of HFE will never be broken faster that the exhaustive search.

These challenges has been proposed by Jacques Patarin in June 1998 with a price of $500 each
(extended version of [IP1], last pages). Only the first challenge have been broken (the second is still not broken, see below).

Challenge 1.

Challenge 1 can be a 80-bit signature or/and encryption scheme. We have K=GF(2), n=80, d=96. We have 80 equations with 80 binary unknowns. The challenge is simply to solve these equations for a given output y. The initial Patarin's challenge in [IP1] require to break a particular signature scheme based on each of them. It requires several computations of g^{-1}. If someone manages to recover a plaintext x for a given y he can certainly break the initial challenge. We have chosen the y as y=g(x) for a random x. Download: challenge1.txt (1.5 Mb)/ challenge1.zip (207 kb).

On April 10th 2002, at the crypto seminar of Versailles university, Jean-Charles Faugère from Paris 6 university have presented an implementation of his recent Gröbner bases algorithm F5/2 that managed to break the HFE Challenge 1 in 96 hours on a 833 MHz Alpha workstation with 4 Gbytes of memory. The first HFE challenge is therefore closed. This attack is done with the F5/2 algotihm and can be seen as optimized (but also very general) version of the Courtois attack on Challenge 1. The paper by Faugère and Joux presented at Crypto 2003 explanis why these attacks work (but forgets to quote the contributions of four other papers on HFE: almost none of the results are new, except the explanation why such do work on HFE).

In August 2004, Allan Steel from the Magma project in Sydney, Australia, implemented the Faugère's F4 algorithm that is now included in Magma 2.11, and solved the HFE Challenge 1 again, in 25 hours, using 15 Gbytes of memory. It seems that this implementation was about 3 times faster than the original Faugère's implementation.

Challenge 2.

Challenge 2 gives 144-bit signatures. We have K=GF(16), n=36, d=4352, 4 of 36 public equations have been removed . The challenge is to find (at least one) solution to these equations.

This HFE challenge 2 has been claimed to be broken by Nicolas Courtois at PKC 2004: see Nicolas Courtois: Algebraic Attacks over GF(2^k), Application to HFE Challenge 2 and Sflash-v2, in PKC 2004, March 1-4 2004, Singapore. However the complexity was quite underestimated, see Jiun-Ming Chen, Nicolas Courtois and Bo-Yin Yang: On Asymptotic Security Estimates in XL and Gröbner Bases-Related Algebraic Cryptanalysis, will be presented at ICICS'04, 27-29 October 2004, Malaga, Spain. To appear in LNCS, Springer. 
Therefore this challenge status is still ongoing (best known attack: 2^93). 

1. One possible way to make it more secure is to consider HFE of nonlinear order 3 [IP1,ISA]. It is not practical because of the public key size (n=128 - 10 Mb).

2. A simple idea (initially due to Shamir) is to remove some public equations. If the number of removed equations is small, it can still be used for encryption otherwise it's only suitable for signature.

3. HFEv (due to Patarin) is a trapdoor function that even for the owner or the secret key is solvable only when the values of some variables are fixed, see [IP2,CHFE,DEA,IP7,Quartz]. If the number of additional variables is small, it can still be used for encryption, otherwise it's only suitable for signature

4. HFE+ consists of adding some random equations to HFE, see [IP2,DEA,IP7]. If the number of added equations is small, it can still be used for signature, otherwise it's only suitable for sencryption.

5. HFEf consists of fixing the values of some entries of the public key, see [IP2,DEA].If the number of fixed variables is small, it can still be used for signature, otherwise it's only suitable for sencryption.

All the 2-5 can be combined in any order and are believed to prevent very efficietly any kind of attack that uses the trapdoor of HFE and even for the weakest HFE cases [CHFE,DEA,IP7].

6. For encryption, it is easy to convert HFE into a ciphertext-secure cryptosystem (semantic security and non-malleability against adaptative adversaries), by applying a standard technique REACT by Pointcheval-Okamoto.

In theory: HFE cryptosystem is much less known that the RSA. It means that RSA could be secure (in theory) but not HFE.
But on the other hand ...
Practice: HFE attacks are much less studied (and implemented) that the RSA. It means that HFE could be secure in practice and not RSA.
The fact is that the RSA-130 challenge (about 430 bits) is broken now.
The HFE challenge 1 (80 bits) is almost broken too.

Some people pretend that it is easy to break ... The challenges from this page allow them to prove it without revealing how.

Another argument can be put forward in favour of HFE:
I've heard that a quantum computer breaking the 512 bit RSA is estimated to be as big as about 10^3 quantum bits. Breaking a 512 bit RSA is only a bit more that what we can achieve today with classical computers. For the HFE, the entropy of the public key is huge (and it's size even more). It is obvious that the quantum computer for HFE would be huge. It should have millions of quantum bits. The latest computer that I've heard of had 7 quantum bits, and most people believe that it will be increasingly difficult (and costly) to built bigger quantum computers because of the instability problems (decoherence). 

Implementing HFE

• Implementing Hidden Field Equations in Java, by Christopher Wolf.
  Again, using this requires to pay royalties for the HFE patent.
• Key Generation for Hidden Field Equations in Java, by Christopher Wolf.
  Again, using this requires to pay royalties for the HFE patent.

Papers about HFE implementation and related stuff:

• Efficient Public Key Generation for Multivariate Cryptosystems, by Christopher Wolf.
• Mehdi-Laurent Akkar, Nicolas Courtois, Louis Goubin, Romain Duteuil, A Fast and Secure Implementation of Slash, PKC 2003, LNCS 2567, pp. 267-278. See also the Sflash web page.

HFE has been patented by Jacques Patarin.
The US patent is untitled ``Method for cryptographic communications'',
number 5 790 675, issued on August 4th 98. It expires on July 24th 2016.
It belongs currently to Axalto, 36-38 rue de la Princessse, BP45, 78431 Louveciennes Cedex, France. Entensions to this patent have been filed in many countries (Europe, US, Israel, Taiwan, etc..).

[BRA] BRASSARD Gilles:
``A note on the complexity''; IEEE Tran. Information Theory, Vol. IT-25, 1979, pp. 232-233.

[CHFE] Nicolas Courtois:
``The security of Hidden Field Equations (HFE)'', Cryptographers' Track Rsa Conference 2001,
LNCS 2020, pp. 266-281, Springer-Verlag.
Donwload the paper hfesec.dvi / hfesec.ps.
The slides from RSA2001: hfesecsl.dvi / hfesecsl.ps / hfesecsl.pdf

[DEA] COURTOIS Nicolas: Extensive study of
``Isomorphism of Polynomials and Asymmetric Cryptography''; Rapport du Magistère MMFAI, Paris 6 University, Ecole Normale Supérieure, November 1997, Download it's abstract (English/French).
Or the whole work in French (quite out of date now).

[HFEMR] Nicolas Courtois:
HFE and MinRank, the PKC&CNT conference. hfemr.dvi/hfemr.ps/hfemr.pdf

[BATZ] Nicolas Courtois:
Transparents (en français) sur HFE et polynômes multivariables (Batz-sur-Mer, 1er Juin 1999). Corrigé.

[HFEPL] Nicolas Courtois: Presentation at the Enigma 2000 conference (in Polish),
Algorytm klucza publicznego HFE, corrected and extended, hfepl.ps.

[KURS] Nicolas Courtois: An introduction to multivariate cryptography, first presented at the Enigma 2000 conference (in Polish):
Kryptografia Wielu Zmiennych , corrected and extended, kurs.pdf

[Quartz] Nicolas Courtois, Louis Goubin, Jacques Patarin:
``Quartz, 128-bit long digital signatures'': in Cryptographers' Track Rsa Conference 2001, LNCS 2020, pp. 282-297, Springer-Verlag. Also submitted to Nessie European Call for Primitives

Here is the Quartz signature scheme homepage.

[Flash] Nicolas Courtois, Louis Goubin, Jacques Patarin:
``Flash, a fast multivariate signature algorithm'' : published in Cryptographers' Track Rsa Conference 2001, LNCS 2020, pp. 298-307, Springer. Also submitted to Nessie European Call for Primitives

Here is the Flash signature scheme homepage.

[GCTTM] Nicolas Courtois, Louis Goubin:
``The Cryptanalysis of TTM'': To be presented at Asiacrypt 2000 conference, 3-9 December 2000, Kyoto, Japan, to appear in Springer-Verlag LNCS.

Unoffical homepage for TTM.

[FaugJouxHfe] Jean-Charles Faugère, Antoine Joux: Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases, in Crypto 2003, LNCS 2729, pp. 44-60, Springer, August 2003.

[GSF] J. von zur GATHEN and Victor SHOUP:
``Computing Frobenius maps and factoring polynomials''; Proceedings of the 24th Annual ACM Symposium in Theory of Computation, ACM Press, 1992.

[IP1] PATARIN Jacques:
``Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt'88''; CRYPTO'95, Springer-Verlag, pp. 248-261.

[IP2] PATARIN Jacques:
``Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of Asymmetric Algorithms''; Eurocrypt'96, Springer Verlag, pp. 33-48. Extended and up-to-date version is maintained by Jacques Patarin. You can download it here (.dvi / .ps / .pdf)

[IP3] PATARIN Jacques:
``Asymmetric Cryptography with a Hidden Monomial''; CRYPTO'96, Springer Verlag, pp. 45-60.

[IP4] Louis Goubin, Jacques Patarin:
``Asymmetric cryptography with S-boxes''; june 1997, to appear ISICS'97, Springer-Verlag.

[IP5] Louis Goubin, Jacques Patarin:
``Trapdoor one-way permutations and multivariate polynomials''; june 1997, to appear in ISICS'97, Springer-Verlag.

[IP6] Nicolas Courtois, Louis Goubin, Jacques Patarin:
``Improved Algorithms for Isomorphism of Polynomials''; Eurocrypt'98, Springer-Verlag.
Download the extended version of the paper .dvi / .ps / .pdf or the slides from my talk at Eurocrypt.

[IP7] Nicolas Courtois, Louis Goubin, Jacques Patarin:
``C*-+ and HM - Variations around two schemes of T. Matsumoto and H. Imai'';
Asiacrypt'98, Springer-Verlag. Download the extended version of the paper dvi / ps / pdf.

[IP8] Jacques Patarin: Aviad KIPNIS, Louis Goubin:
``Unbalanced Oil and Vinegar Signature Schemes''; Eurocrypt 1999, Prague, Czechoslovakia, Springer-Verlag.Download the extended version .ps.

[IP9] Adi Shamir, Nicolas Courtois, JacquesPatarin, Alexander Klimov:
``Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations'', presented at Eurocrypt 2000 conference.
The extended version of the paper is available here.

[IPC] Nicolas Courtois, Louis Goubin, Jacques Patarin:
``Asymmetric Cryptography with Multivariate Polynomials over Finite Fields'': known as (orange book/poly orange),a kind of compilation of different papers and some unpublished work. Ask for it Jacques Patarin.

[SFBREAK] Nicolas Courtois: Algebraic Attacks over GF(2^k), Cryptanalysis of HFE Challenge 2 and Sflash-v2. Will be presented at PKC 2004, March 1-4 2004, Singapore.

[ISA] Isabelle GUERIN-LASSOUS:
``Rapport de Stage-Etude et attaque de l'algorithme de Matsumoto-Imai et de ses généralisations'', DEA Intelligence Artificielle et Algorithmique, Université de Caen.

[KOB] Neal KOBLITZ:
``Algebraic aspects of cryptography''; Springer-Verlag, ACM3, 1998, Chapter 4 ``Hidden Monomial Cryptosystems'', pp. 80-102.

[FF] R. LIDL, H. NIEDERREITER:
``Finite Fields''; Encyclopedia of Mathematics and its applications, Volume 20, Cambridge University Press.

[MCL] Tsutomu MATSUMOTO, Hideki IMAI:
``A class of asymmetric cryptosystems based on polynomials over finite rings''; 1983 IEEE International Symposium on Information Theory, Abstract of Papers, pp.131-132, September 1983.

[MG] Tsutomu MATSUMOTO, Hideki IMAI:
``Algebraic Methods for Construction of Asymmetric Cryptosystems''; AAECC-3, Grenoble, France, 15-19 of June 1985.

[MI] Tsutomu MATSUMOTO, Hideki IMAI:
``Public Quadratic Polynomial-tuples for efficient signature-verification and message-encryption'', EUROCRYPT'88, Springer-Verlag 1998, pp. 419-453.

[MOV] Alfred J. MENEZES, Paul C. van OORSHOT, Scott A. VANSTONE:
``Handbook of Applied Cryptography''; CRC Press. Also available on the internet in pdf format.

[MOVF] Alfred J. MENEZES, Paul C. van OORSHOT, Scott A. VANSTONE:
``Some computational aspects of root finding in GF(q^{m})''; Symbolic and Algebraic Computation, Lecture Notes in Computer Science, 358 (1989), pp. 259-270.

[OBS] T. MATSUMOTO, H. IMAI, H. HARASHIMA, H. MIYAKAWA:
``Asymmetric cryptosystems using obscure representations of enciphering functions''; 1983 Natl. Conf. Rec. On Inf. Syst., IECE Japan, S8-5, September 1983 (in japanese).

[OVF] Paul van OORSCHOT, Scott VANSTONE:
``A geometric approach to root finding in GF(q^{m})'';
IEEE Trans. Info. Th., 35 (1989), pp. 444-453.

[ROS] Michael ROSING:
``Elliptic Curve Cryptography''; Manning Publications, USA. The book can be ordered at it's web site, which contains also it's preface, index, the chapter 5, etc. with all the C-programs from the book.

[SCH] SCHNEIER Bruce:
``Applied Cryptography''; Wiley and sons.

[SHB] SHAMIR Adi:
``Efficent signature schemes based on birational permutations''; CRYPTO 93, Springer-Verlag, pp. 1-12.

[SHFK] SHAMIR Adi, KIPNIS Aviad:
``Cryptanalysis of the HFE public key cryptosystem''; Crypto'99. Exclusive: Download it ! And here is an (quite outdated) comment on this paper by Jacques Patarin.

[SVC] Don Coppersmith , Jacques Stern , Serge Vaudenay:
``Attacks on the birational permutation signature schemes''; CRYPTO 93, Springer-Verlag, pp. 435-443.