Paper 2004/072

Asymmetric Cryptography: Hidden Field Equations

Christopher Wolf and Bart Preneel

Abstract

The most popular public key cryptosystems rely on assumptions from algebraic number theory, e.g., the difficulty of factorisation or the discrete logarithm. The set of problems on which secure public key systems can be based is therefore very small: e.g., a breakthrough in factorisation would make RSA insecure and hence affect our digital economy quite dramatically. This would be the case if quantum-computer with a large number of qbits were available. Therefore, a wider range of candidate hard problems is needed. 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.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Preliminary version published at ECCOMAS 2004--- European Congress on Computational Methods in Applied Sciences and Engineering; P. Neittaanmäki, T. Rossi, S. Korotov, E. Oñate, J. Périaux, and D. Knörzer (eds.); Jyväskylä, 24--28 July 2004, 2004.
Keywords
Short SignaturesMultivariate Quadratic EquationsHidden Field EquationsHFEQuartz
Contact author(s)
Christopher Wolf @ esat kuleuven ac be
History
2005-08-06: last of 9 revisions
2004-03-03: received
See all versions
Short URL
https://ia.cr/2004/072
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/072,
      author = {Christopher Wolf and Bart Preneel},
      title = {Asymmetric Cryptography: Hidden Field Equations},
      howpublished = {Cryptology ePrint Archive, Paper 2004/072},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/072}},
      url = {https://eprint.iacr.org/2004/072}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.