Hidden Field Equations

Short description: Public key cryptosystem

Template:Ref expand Hidden Fields Equations (HFE), also known as HFE trapdoor function, is a public key cryptosystem which was introduced at Eurocrypt in 1996 and proposed by Script error: The function "in_lang" does not exist. Jacques Patarin following the idea of the Matsumoto and Imai system. It is based on polynomials over finite fields 𝔽q 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.[1]

## Contents

* 1 Mathematical background
* 2 Multivariate cryptosystem
* 3 HFE polynomial
* 4 Encryption and decryption
* 5 HFE variations
* 6 HFE attacks
* 7 References

## Mathematical background

One of the central notions to understand how Hidden Field Equations work is to see that for two extension fields 𝔽qn 𝔽qm over the same base field 𝔽q one can interpret a system of m multivariate polynomials in n variables over 𝔽q as a function 𝔽qn->𝔽qm by using a suitable basis of 𝔽qn over 𝔽q. In almost all applications the polynomials are quadratic, i.e. they have degree 2.[2] We start with the simplest kind of polynomials, namely monomials, and show how they lead to quadratic systems of equations.

Consider a finite field 𝔽q, where q is a power of 2, and an extension field K. Let 0<h<qn such that h=qθ+1 for some θ and gcd(h,qn−1)=1. The condition gcd(h,qn−1)=1 is equivalent to requiring that the map u->uh on K is one to one and its inverse is the map u->uh′ where h′ is the multiplicative inverse of h modqn−1.

Take a random element u∈𝔽qn. Define w∈𝔽qn by

w=uh=uqθu (1)

Let β1,...,βn to be a basis of K as an 𝔽q vector space. We represent u with respect to the basis as u=(u1,...,un) and w=(w1,...,wn). Let A(k)=aij(k) be the matrix of the linear transformation u->uqk with respect to the basis β1,...,βn, i.e. such that

βiqk=∑j=1naijkβj, aijk∈𝔽q

for 1≤i,k≤n. Additionally, write all products of basis elements in terms of the basis, i.e.:

βiβj=∑l=1nmijlβl, mijl∈𝔽q

for each 1≤i,j≤n. The system of n equations which is explicit in the wi and quadratic in the uj can be obtained by expanding (1) and equating to zero the coefficients of the βi.

Choose two secret affine transformations S and T , i.e. two invertible n×n matrices MS={Sij} and MT={Tij} with entries in 𝔽q and two vectors vS and vT of length n over 𝔽q and define x and y via:

u=Sx=MSx+vS w=Ty=MTy+vT (2)

By using the affine relations in (2) to replace the uj,wi with xk,yl, the system of n equations is linear in the yl and of degree 2 in the xk. Applying linear algebra it will give n explicit equations, one for each yl as polynomials of degree 2 in the xk.[3]

## Multivariate cryptosystem

The basic idea of the HFE family of using this as a multivariate cryptosystem is to build the secret key starting from a polynomial P in one unknown x over some finite field 𝔽qn (normally value q=2 is used). This polynomial can be easily inverted over 𝔽qn, i.e. it is feasible to find any solutions to the equation P(x)=y when such solution exist. The secret transformation either decryption and/or signature is based on this inversion. As explained above P can be identified with a system of n equations (p1,...,pn) using a fixed basis. To build a cryptosystem the polynomial (p1,...,pn) must be transformed so that the public information hides the original structure and prevents inversion. This is done by viewing the finite fields 𝔽qn as a vector space over 𝔽q and by choosing two linear affine transformations S and T. The triplet (S,P,T) constitute the private key. The private polynomial P is defined over 𝔽qn.[1][4] The public key is (p1,...,pn). Below is the diagram for MQ-trapdoor (S,P,T) in HFE

inputx->x=(x1,...,xn)->secret:Sx′->secret:Py′->secret:Toutputy

## HFE polynomial

The private polynomial P with degree d over 𝔽qn is an element of 𝔽qn[x]. If the terms of polynomial P have at most quadratic terms over 𝔽q then it will keep the public polynomial small.[1] The case that P consists of monomials of the form xqsi+qti, i.e. with 2 powers of q in the exponent is the basic version of HFE, i.e. P is chosen as

P(x)=∑cixqsi+qti

The degree d of the 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 d slows down the deciphering. Since P is a polynomial of degree at most d the inverse of P, denoted by P−1 can be computed in d2(ln⁡d)O(1)n2𝔽q operations.[5]

## Encryption and decryption

The public key is given by the n multivariate polynomials (p1,...,pn) over 𝔽q. It is thus necessary to transfer the message M from 𝔽qn->𝔽qn in order to encrypt it, i.e. we assume that M is a vector (x1,...,xn)∈𝔽qn. To encrypt message M we evaluate each pi at (x1,...,xn). The ciphertext is (p1(x1,...,xn),p2(x1,...,xn),...,pn(x1,...,xn))∈𝔽qn.

To understand decryption let us express encryption in terms of S,T,P. Note that these are not available to the sender. By evaluating the pi at the message we first apply S, resulting in x′. At this point x′ is transferred from 𝔽qn->𝔽qn so we can apply the private polynomial P which is over 𝔽qn and this result is denoted by y′∈𝔽qn. Once again, y′ is transferred to the vector (y1′,...,yn′) and the transformation T is applied and the final output y∈𝔽qn is produced from (y1,...,yn)∈𝔽qn.

To decrypt y, the above steps are done in reverse order. This is possible if the private key (S,P,T) is known. The crucial step in the deciphering is not the inversion of S and T but rather the computations of the solution of P(x′)=y′. Since P is not necessary a bijection, one may find more than one solution to this inversion (there exist at most d different solutions X′=(x1′,...,xd′)∈𝔽qn since P is a polynomial of degree d). The redundancy denoted as r is added at the first step to the message M in order to select the right M from the set of solutions X′.[1][3][6] The diagram below shows the basic HFE for encryption.

M->+rx->secret:Sx′->secret:Py′->secret:Ty

## 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 f input variables of the public key, this variant is sometimes called p for projection.
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.
05\. The IP sign means Internal perturbation, it consists in adding random quadratic polynomial to the secret equations. However the random quadratic polynomial is composed with a small rank linear map. Making it possible to invert.
06\. The LL'  variant consist in adding a random linear combination of a small number of product of linear map to every public equations. It is meant to be used in encryption mode.

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

HFE- and HFEv were useful in signature schemes as they prevent from slowing down the signature generation and also enhance the overall security of HFE whereas for encryption 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. However due to new Min-Ranks attack by Ding, Petzoldt and Tao it made these scheme obsolete.[7]

For Signatures it is now recommended to use HFE IP- or HFE IPv.[8] Indeed the IP variant is very effective against certain type of Min-Rank attacks (Min-Rank S) while v or - variant are effective against all other attacks (Mainly Min-Rank T or Gröbner Basis attacks).

For encryption, the only current recommended scheme is HFE LL'.[9]

## HFE attacks

There are two famous attacks on HFE:

Recover the Private Key (Shamir-Kipnis): The key point of this attack is to recover the private key as sparse univariate polynomials over the extension field 𝔽qn. The attack only works for basic HFE and fails for all its variations.

Fast Gröbner Bases (Faugère): The idea of Faugère's attacks is to use fast algorithm to compute a Gröbner basis of the system of polynomial equations. Faugère broke the HFE challenge 1 in 96 hours in 2002, and in 2003 Faugère and Joux worked together on the security of HFE.[1]

## References

1. ↑ 1.0 1.1 1.2 1.3 1.4 Christopher Wolf and Bart Preneel, Asymmetric Cryptography: Hidden Field Equations
2. ↑ Nicolas T. Courtois On Multivariate Signature-only public key cryptosystems
3. ↑ 3.0 3.1 Ilia Toli Hidden Polynomial Cryptosystems
4. ↑ Jean-Charles Faugère and Antoine Joux, Algebraic Cryptanalysis of Hidden Field Equations (HFE) Cryptosystems Using Gröbner Bases
5. ↑ Nicolas T. Courtois, "The Security of Hidden Field Equations"
6. ↑ Jacques Patarin, Hidden Field Equations (HFE) and Isomorphic Polynomial (IP): two new families of asymmetric algorithm
7. ↑ "Improved Key Recovery of the HFEv- Signature Scheme". 2020. https://eprint.iacr.org/2020/1424.
8. ↑ "State of the art of HFE variants is it possible to repair HFE with appropriate perturbations?". 2024. https://eprint.iacr.org/2024/1706.
9. ↑ "Multivariate Encryptions with LL' perturbations - is it possible to repair HFE in encryption? -". 2024. https://eprint.iacr.org/2024/1999.

* Nicolas T. Courtois, Magnus Daum and Patrick Felke, On the Security of HFE, HFEv- and Quartz
* Andrey Sidorenko, Hidden Field Equations, EIDMA Seminar 2004 Technische Universiteit Eindhoven
* Yvo G. Desmet, Public Key Cryptography-PKC 2003, ISBN 3-540-00324-X

* v
* t
* e

Public-key cryptography

Algorithms|

| Integer factorization|

* Benaloh
* Blum–Goldwasser
* Cayley–Purser
* Damgård–Jurik
* GMR
* Goldwasser–Micali
* Naccache–Stern
* Paillier
* Rabin
* RSA
* Okamoto–Uchiyama
* Schmidt–Samoa

|

Discrete logarithm|

* BLS
* Cramer–Shoup
* DH
* DSA
* ECDH
* ECDSA
* EdDSA
* EKE
* ElGamal
* signature scheme
* MQV
* Schnorr
* SPEKE
* SRP
* STS

Lattice/SVP/CVP/LWE/SIS|

* NTRUEncrypt
* NTRUSign
* RLWE-KEX
* RLWE-SIG
* BLISS

Others|

* AE
* CEILIDH
* EPOC
* HFE
* IES
* Lamport
* McEliece
* Merkle–Hellman
* Naccache–Stern knapsack cryptosystem
* Three-pass protocol
* XTR

Theory|

* Discrete logarithm
* Elliptic-curve cryptography
* Non-commutative cryptography
* RSA problem
* Trapdoor function

Standardization|

* CRYPTREC
* IEEE P1363
* NESSIE
* NSA Suite B
* Post-Quantum Cryptography Standardization

Topics|

* Digital signature
* OAEP
* Fingerprint
* PKI
* Web of trust
* Key size
* Post-quantum cryptography

* v
* t
* e

Cryptography

* History of cryptography
* Cryptanalysis
* Outline of cryptography

* Symmetric-key algorithm
* Block cipher
* Stream cipher
* Public-key cryptography
* Cryptographic hash function
* Message authentication code
* Random numbers
* Steganography

* Category

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Hidden Field Equations. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Hidden_Field_Equations&oldid=3990519"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template