[Resource Topic] 2004/072: Asymmetric Cryptography: Hidden Field Equations

Welcome to the resource topic for 2004/072

Asymmetric Cryptography: Hidden Field Equations

Authors: Christopher Wolf, Bart Preneel


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.

ePrint: https://eprint.iacr.org/2004/072

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .