Welcome to the resource topic for
**2004/072**

**Title:**

Asymmetric Cryptography: Hidden Field Equations

**Authors:**
Christopher Wolf, 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.

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