Hidden Field Equations - Mathematical Background

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 of 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 of as an vector space. Let such that for some and gcd and take a random element . We represent with respect to the basis as . Define by

The condition gcd is equivalent to requiring that the map on 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 in the and of degree 2 in the . Applying linear algebra it will give explicit equations, one for each as polynomials of degree 2 in the .