Introduction
Let's ensure we understand the foundational concepts before delving further into the subjects. Here is a brief introduction if you are unfamiliar with Cryptography.
The use of codes to secure information and communications in such a way that only the intended recipients can decipher and process them is known as cryptography. Hence, information access by unauthorised parties is prevented. Writing is denoted by the suffix "graphy," while the word "crypt" denotes "hidden."
This article explains the details of Field Equations, but they are hidden in cryptography. We will discuss its mathematical background, Mathematical background, HFE polynomial, Encryption and decryption, HFE variations, and HFE attacks.
Without further ado, let's get started.
Hidden Field Equations
Jacques Patarin (in French) proposed the Hidden Fields Equations (HFE) public key cryptosystem, often known as the HFE trapdoor function, as an improvement to the Matsumoto and Imai system. It was first used at Eurocrypt in 1996. It uses polynomials over finite fields Fq of various sizes to hide the connection between the private key and public key. The basic HFE and combinatorial HFE versions make up the HFE family. Since the extension field and the private polynomials are concealed using private affine transformations, the HFE family of cryptosystems is predicated on the hardness of the challenge of finding solutions to a system of multivariate quadratic equations (also known as the MQ problem).
Mathematical background
One of the key ideas in comprehending the operation of Hidden Field Equations is the realisation that, for two extension fields over the same base field Fq, one can interpret a system of m multivariate polynomials in n variables over by utilising an appropriate basis of over Fq. The polynomials are virtually always of degree 2, or quadratic, in all applications. Monomials, the most basic type of polynomial, are used as a starting point to demonstrate how quadratic systems of equations can be formed.
Consider a finite field Fq and an extension field K, where q is a power of 2. Let be such that it gcd and for some theta. In order to satisfy the condition gcd , it is necessary for the map on K to be one to one and for its inverse to be the map , where h' is the multiplicative inverse of .
Pick an element at random . Establish by
Assume that serves as K's Fq vector space basis. In relation to the basis, we represent u as and . In other words, let represent the matrix of the linear transformation with regard to the basis .
for . Write every basis element products in terms of the basis as well, i.e.
for each. By expanding (1) and setting the coefficients of the to zero, one can construct the system of n equations that is explicit in the wi and quadratic in the uj.
Select two secret affine transformations S and T, which are represented by two invertible
n x n matrices Ms = {Sij} and MT = {Tij} with entries in Fq and two vectors vS and vT of length n over Fq, then define x and y using:
The system of n equations is linear in the yl and of degree 2 in the xk if the affine relations in (2) are used to replace the uj, wi with xk ,yl. It will produce n explicit equation using linear algebra, one for each yl as polynomials of degree 2 in the xk.
Multivariate cryptosystem
The fundamental concept of the HFE family is to create the secret key by starting with a polynomial P in one unknown x over a finite field (typically, value q=2). In other words, it is possible to find any solutions to the equation P(x)=y when such solutions exist because this polynomial may be simply inverted over . This inversion is the foundation of the secret transformation, which may be a decryption or a signature. As previously mentioned, P can be determined via a fixed basis system with n equations (p1,..,pn). The polynomial (p1,..,pn) must be modified in order to create a cryptosystem so that the public knowledge conceals the original structure and prevents inversion.This is accomplished by selecting the two linear affine transformations S and T and seeing the finite fields as a vector space over Fq. The private key is made up of the triplet (S,P,T). Over , the private polynomial P is defined. The open key is (p1,..,pn). The illustration for MQ-trapdoor (S,P,T) in HFE is shown below.
HFE polynomial
includes the private polynomial P with degree d over . The public polynomial will remain small if the polynomial P's terms contain no more than two quadratic terms over Fq. The fundamental version of HFE is when P is chosen as a set of monomials of form xi, i.e. with two powers of q in the exponent.
The polynomial's degree d is also referred to as the security parameter, and the higher its value, the better for security because the resulting collection of quadratic equations closely mimics a set of quadratic equations selected at random. Large d, on the other hand, makes deciphering more difficult. The inverse of P, indicated by P-1, which has a degree of at most d, can be calculated in operations.
Encryption and decryption
The n multivariate polynomials (p1,..., pn) over Fq provide the public key. Therefore, in order to encrypt the message M, it must be transferred from , so we assume that M is a vector of type . At (x1,...,xn) we assess each pi to encrypt message M. The ciphertext is .
Let's define encryption in terms of S, T, P to better comprehend decryption. Keep in mind that the sender is not able to access these. By applying S first and assessing pi at the message, we get x'. In order to apply the private polynomial P, which is over , at this point, x' is transferred from ; the resulting value is indicated by . Once more, the transformation T is used to transform the vector (y1,..,yn) into the final output, , from which is created.
The above steps are carried out in reverse order to decrypt y. If the private key (S,P,T) is known, then this is feasible. The computations of the P(x')=y' solution are more important than the inversion of S and T in the decoding process. There may be more than one solution to this inversion since P need not be a bijection (there exist at most d different solutions since P is a polynomial of degree d). In order to choose the appropriate message M from the group of solutions X', redundancy, denoted by the symbol r, is added at the beginning of the process. The fundamental HFE for encryption is shown in the diagram below.
HFE variations
📂 The four basic Hidden Field Equations variations are +,-, v, and f, and there are several ways to mix them. The following is the fundamental idea:
1️⃣ The linearity of random and open equations is mixed to get the + sign.
2️⃣ Adi Shamir is to be credited for the - sign, which eliminates the redundant "r" in the public equations.
3️⃣ The public key's f input variables are fixed as part of the f sign.
4️⃣ The v sign is defined as a construction, sometimes fairly complicated, that makes it possible to find the inverse of a function only when a certain number of variables, known as vinegar variables, are fixed. Jacques Patarin is to thank you for the concept.
The above operations maintain part of the function's trapdoor solvability.
HFE- and HFEv are highly helpful in signature schemes as they avoid slowing down the formation of signatures and increase the overall security of HFE. However, neither HFE- nor HFEv should be used since they will result in an overly long decryption procedure (HFEv). To obtain Quartz, both HFE- and HFEv were employed.
With HFE+, encryption is better because the decryption procedure is faster, but the public key includes more equations than variables.
HFE attacks
💁 Two well-known attacks on HFE include:
The main goal of this assault, known as the Shamir-Kipnis attack, is to obtain the private key as sparse univariate polynomials over the extension field . The attack is only effective against basic HFE and fails against all of its variants.
Fast Gröbner Bases (Faugère): The aim behind Faugère's attacks is to compute a Gröbner basis of the system of polynomial equations using a quick approach. In 2002, Faugère completed the HFE Challenge 1 in 96 hours. In 2003, Faugère and Joux collaborated on HFE security.