The overall idea of cryptography is described briefly in the first chapter of this thesis. Moreover, this chapter gives a short explanation about the RSA system (Rivest, Shamir, Adleman) and also the ElGamal system. Both can be used for encryption/decryption and signature generation/verification.

The same is true for the HFE system which is explained in the next chapter. This chapter
describes how *n* polynomials (*p1, ..., pn*) in
*n* variables over a small finite field *F* can be
used as a public key. The corresponding problem is called "MQ" (i.e., multivariable quadratic).
Recommended values for the public key are *n* = 80, ..., 129 and *F* = GF(2).
In addition, a trapdoor (private key) for this public key is described. This trapdoor consists of
two affine transformations, denoted *S* and *T*, and also one private polynomial, denoted
*P*, over
an extension field *E*. Using this trapdoor, both encryption and signature generation
can be performed. The second chapter also considers the speed of HFE, its security
parameters, and which difficulties arise for non-surjective versions of HFE.

In Chapter 3, the complexity of HFE in terms of **NP**-completeness
is discussed. It contains a proof that MQ problem over finite fields is **NP**-complete.
In addition, attacks against HFE are discussed. These attacks are classified as either structural
(i.e., revealing the private key) or inversion (i.e., computing signatures or
decrypting messages for eavesdropper) attacks.

To increase the security of HFE, it is possible to vary the system. Some of these possible modifications are discussed in the forth chapter. Unfortunately, some of the variations investigated are proven to be less secure than HFE itself. On the other hand, some of them can reduce the public key size or decrease the time for private key computations, which makes them worthwhile in some application domains.

Chapter 5 shows some real world applications of HFE for signature and outlines how HFE can be used for encryption. These real world applications include the two signature algorithms Quartz and SFlash which are currently under consideration in the European cryptographic project NESSIE.

In its last chapter, this thesis is summarised and some fields of possible further research are discussed.

- Postscript (PS) (651 kB) or
- Portable Data Format (PDF) (877 kB).

Its BibTeX-Entry is:

@MastersThesis{Wolf:02:Thesis, author = {Christopher Wolf}, title = {``Hidden Field Equations" {(HFE)} - Variations and Attacks}, school = {Universit{\"a}t Ulm}, year = {2002}, month = dec, note = {\url{http://www.christopher-wolf.de/dpl}}} }

Christopher Wolf, 2003-02-03. eMail: `hfe@christopher-wolf .de`