Welcome to the resource topic for 2020/1380
Title:
Fast Computing of Quadratic Forms of HFE Polynomials over fields of characteristic two
Authors: 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.
ePrint: https://eprint.iacr.org/2020/1380
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .