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.
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