Hidden Field Equations - AbsoluteAstronomy.com

Hidden Fields Equations (HFE) is a public key cryptosystem

Cryptosystem

There are two different meanings of the word cryptosystem. One is used by the cryptographic community, while the other is the meaning understood by the public.- General meaning :...

which was introduced at Eurocrypt

Eurocrypt

Eurocrypt is a conference for cryptography research. The full name of the conference is currently the Annual International Conference on the Theory and Applications of Cryptographic Techniques, but this has not always been its name...

in 1996 and proposed by Jacques Patarin following the idea of the Matsumoto

Matsumoto

Matsumoto is the 16th most common Japanese surname and the name of a city in Nagano Prefecture.-People:* Chizuo Matsumoto, a.k.a...

and Imai

Imai

-People:The Japanese characters link to the Japanese-language Wikipedia*Eriko Imai , artist*Hisae Imai , photographer*Hisashi Imai , Japanese rock musician*Juliana Imai , Brazilian model...

system. HFE is also known as HFE trapdoor function. It is based on polynomials over finite fields

of different size to disguise the relationship between the private key and public key. HFE is in fact a family which consists of basic HFE and combinatorial versions of HFE. The HFE family of cryptosystems is based on the hardness of the problem of finding solutions to a system of multivariate quadratic equations (the so called MQ problem) since it uses private affine transformations to hide the extension field and the private polynomials. Hidden Field Equations also have been used to construct digital signature schemes, e.g. Quartz and Sflash.

Mathematical background

One of the central notions to understand how Hidden Field Equations work is to see that for two extension fields

over the same base field

one can interpret a system of

multivariate polynomials in

variables over

as a function

by using a suitable basis

Basis

Basis may refer to* Cost basis, in income tax law, the original cost of property adjusted for factors such as depreciation.* Basis of futures, the value differential between a future and the spot price...

over

. In almost all applications the polynomials are quadratic, i.e. they have degree 2. We start with the simplest kind of polynomials, namely monomials, and show how they lead to quadratic systems of equations.

Let us consider a finite field

, where

is a power of 2, and an extension field

. Let

to be a basis

Basis

as an

vector space

Vector space

A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...

. Let

such that

for some

and gcd

Greatest common divisor of two polynomials

Informally, the greatest common divisor of two polynomials p and q is the largest polynomial that divides both p and q evenly. The definition is modeled on the concept of the greatest common divisor of two integers, the greatest integer that divides both...

and take a random element

. We represent

with respect to the basis as

. Define

The condition gcd

Greatest common divisor of two polynomials

is equivalent to requiring that the map

is one to one and its inverse is the map

where

is the multiplicative inverse of

. Choose two secret affine transformation, i.e. two invertible

matrices

and

with entries in

and two vectors

and

of length

over

and define

and

via:

Let

be the matrix of linear transformation in the basis

such that

for

. Write all products of basis elements in terms of the basis, i.e.:

for each

. The system of

equations which is explicit in the

and quadratic in the

can be obtain by expanding (1) and equating to zero the coefficients of the

. By using the affine relations in (2) to replace the

with

, the system of

equations is linear

Linear

In mathematics, a linear map or function f is a function which satisfies the following two properties:* Additivity : f = f + f...

in the

and of degree 2 in the

. Applying linear algebra

Linear algebra

Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...

it will give

explicit equations, one for each

as polynomials of degree 2 in the

Multivariate cryptosystem

The basic idea of the HFE family of using this as a multivariate cryptosystem

Cryptosystem

There are two different meanings of the word cryptosystem. One is used by the cryptographic community, while the other is the meaning understood by the public.- General meaning :...

is to build the secret key starting from a polynomial

Polynomial

In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...

in one unknown

over some finite field

Finite field

In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...

(normally value

is used). This polynomial

Polynomial

can be easily inverted over

, i.e. it is feasible to find any solutions to the equation

when such solution exist. The secret transformation either decryption and/or signature

Digital signature

A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, and that it was not altered in transit...

is based on this inversion. As explained above

can be identified with a system of

equations

using a fixed basis. To build a cryptosystem

Cryptosystem

There are two different meanings of the word cryptosystem. One is used by the cryptographic community, while the other is the meaning understood by the public.- General meaning :...

the polynomial

Polynomial

must be transformed so that the public information hides the original structure and prevents inversion. This is done by viewing the finite fields

as a vector space

Vector space

over

and by choosing two linear affine transformation

Affine transformation

In geometry, an affine transformation or affine map or an affinity is a transformation which preserves straight lines. It is the most general class of transformations with this property...

and

. The triplet

constitute the private key. The private polynomial

Polynomial

is defined over

. The public key is

. Below is the diagram for MQ-trapdoor

in HFE

HFE polynomial

The private polynomial

Polynomial

with degree

over

is an element of

. If the terms of polynomial

Polynomial

have at most quadratic

Quadratic

In mathematics, the term quadratic describes something that pertains to squares, to the operation of squaring, to terms of the second degree, or equations or formulas that involve such terms...

terms over

then it will keep the public polynomial small. The case that

consists of monomials of the form

, i.e. with 2 powers of

in the exponent
is the basic version of HFE, i.e.

is chosen as

The degree

of the polynomial

Polynomial

is also known as security parameter and the bigger its value the better for security since the resulting set of quadratic equations resembles a randomly chosen set of quadratic equations. On the other side large

slows down the deciphering. Since

is a polynomial

Polynomial

of degree at most

the inverse of

, denoted by

can be computed in

operations.

Encryption and decryption

The public key is given by the

multivariate polynomials

over

. It is thus necessary to transfer the message

from

in order to encrypt it, i.e. we assume that

is a vector

. To encrypt message

we evaluate each

. The ciphertext is

.

To understand decryption let us express encryption in terms of

. Note that these are not available to the sender. By evaluating the

at the message we first apply

, resulting in

. At this point

is transferred from

so we can apply the private polynomial

which is over

and this result is denoted by

. Once again,

is transferred to the vector

and the transformation

is applied and the final output

is produced from

.

To decrypt

, the above steps are done in reverse order. This is possible if the private key

is known. The crucial step in the deciphering is not the inversion of

and

but rather the computations of the solution of

. Since

is not necessary a bijection, one may find more than one solution to this inversion (there exist at most d different solutions

since

is a polynomial of degree d). The redundancy denoted as

is added at the first step to the message

in order to select the right

from the set of solutions

. The diagram below shows the basic HFE for encryption.

HFE variations

Hidden Field Equations has four basic variations namely +,-,v and f and it is possible to combine them in various way. The basic principle is the following:

01. The + sign consists of linearity mixing of the public equations with some random equations.

02. The - sign is due to Adi Shamir and intends to remove the redundancy 'r' of the public equations.

03. The f sign consists of fixing some

input variables of the public key.

04. The v sign is defined as a construction and sometimes quite complex such that the inverse of the function can be found only if some v of the variables called vinegar variables are fixed. This idea is due to Jacques Patarin.

The operations above preserve to some extent the trapdoor solvability of the function.

HFE- and HFEv are very useful in signature schemes as they prevent from slowing down the signature generation and also enhance the overall security of HFE whereas for encryption

Encryption

In cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...

both HFE- and HFEv will lead to a rather slow decryption process so neither too many equations can be removed (HFE-) nor too many variables should be added (HFEv). Both HFE- and HFEv were used to obtain Quartz.

For encryption, the situation is better with HFE+ since the decryption process takes the same amount of time, however the public key has more equations than variables.

HFE attacks

There are two famous recent attacks on HFE:

01. Shamir-Kipnis: Recover the Private Key.

The key point of this attack is to recover the private key as sparse univariate polynomials over the extension field

. The attack only works for basic HFE and fails for all its variations.

02. Faugere: Fast Gröbner Bases.

The idea of Faugere's attacks is to use fast algorithm to compute a Gröbner basis

Gröbner basis

In computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating subset of an ideal I in a polynomial ring R...

of the system of polynomial equations. Faugere broke the HFE challenge 1 in 96 hours in 2002 and in 2003 Faugere and Joux worked together on the security of HFE.

External links

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.