Paper 2020/1380 Original: eprint.iacr.org/2020/1380 ↗

Fast Computing of Quadratic Forms of HFE Polynomials over fields of characteristic two

Abstract

In this paper the author introduces methods that represent elements of a Finite Field $F_q$ as matrices that linearize certain operations like the product of elements in $F_q$. Since the Central Polynomial Map $\mathcal{F}(X)$ coming from the HFE scheme involves multiplication of elements in a Finite Field $F_q$, using a \textit{novel method} based in Linear Algebra the Quadratic Forms resulting from the polynomial map of the Public Key can be computed in few steps and these are bounded by the matrix $R$ that represents the linear action of the polynomial remainder modulo $f(t)$, which is the irreducible polynomial that identifies $F_q$. When the irreducible polynomial $f(t)$ is of the form $t^a+t^b+1$ \textit{modulo $2$}, the matrix $R$ is computed deterministically in few steps and all the Quadratic Forms are derived from this matrix. The research done tells that the central Polynomial Map $\mathcal{F}(X)$ is computed extremely fast, for example, in the CAS \textit{Mathematica}, taking an HFE Polynomial, Quadratic Forms are computed in $\textcolor{red}{\approx 1.4}$ seconds for the case $n=128$. This raises the more general lemma that Quadratic Forms obtained from BigField schemes are entirely dependent on the selected irreducible polynomial $f(t)$ as the matrix $R$ is conditioned by the structure of this polynomial.