In 1996, Patarin proposed the ``Hidden Field Equations" (HFE) as a base for public key cryptosystems. In a nutshell, they use polynomials over finite fields of different size to disguise the relationship between the private key and the public key. In these systems, the public key consists of multivariate polynomials over finite fields with up to 256 elements for practical implementations. Over finite fields, solving these equations has been shown to be an NP-complete problem. In addition, empirical results show that this problem is also hard on average, i.e., it can be used for a secure public key signature or encryption scheme.
In this article, we outline HFE, and its the variations HFE-, HFEv. Moreover, we describe the signature scheme Quartz, which is based on Hidden Field Equations. In addition, we describe the most recent attacks against HFE and sketch two versions of Quartz which are immune against these attacks.
Category / Keywords: public key cryptography / Short Signatures, Multivariate Quadratic Equations, Hidden Field Equations, HFE, Quartz Publication Info: Preliminary version published at ECCOMAS 2004--- European Congress on Computational Methods in Applied Sciences and Engineering; P. Neittaanm{\"a}ki, T. Rossi, S. Korotov, E. O\~nate, J. P\'eriaux, and D. Kn\"orzer (eds.); Jyv{\"a}skyl{\"a}, 24--28 July 2004, 2004. Date: received 3 Mar 2004, last revised 6 Aug 2005 Contact author: Christopher Wolf at esat kuleuven ac be Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20050806:144437 (All versions of this report) Discussion forum: Show discussion | Start new discussion