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

*Borja Gómez*

**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.

**Category / Keywords: **public-key cryptography / multivariate-cryptography quadratic-forms hidden-field-equations implementation public-key quadratic-polynomials finite-fields

**Date: **received 3 Nov 2020

**Contact author: **kub0x at elhacker net

**Available format(s): **PDF | BibTeX Citation

**Version: **20201110:123203 (All versions of this report)

**Short URL: **ia.cr/2020/1380

[ Cryptology ePrint archive ]