**On Polynomial Systems Arising from a Weil Descent**

*Christophe Petit and Jean-Jacques Quisquater*

**Abstract: **In the last two decades, many computational problems arising in cryptography
have been successfully reduced to various systems of polynomial equations. In
this paper, we revisit a class of polynomial systems introduced by Faugère,
Perret, Petit and Renault.
%
Seeing these systems as natural generalizations of HFE systems, we provide
experimental and theoretical evidence that their degrees of regularity are
only slightly larger than the original degre of the equations, resulting in a
very low complexity compared to generic systems.
%
We then revisit the applications of these systems to the elliptic curve
discrete logarithm problem (ECDLP) for binary curves, to the factorization
problem in $SL(2,\mathbf{F}_{2^n})$ and to other discrete logarithm problems.
As a main consequence, we provide a heuristic analysis showing that Diem's
variant of index calculus for
ECDLP
requires a \emph{subexponential} number of bit operations $O(2^{c\,n^{2/3}\log
n})$ over the binary field $\mathbf{F}_{2^n}$, where $c$ is a constant smaller
than $2$.
%
According to our estimations, generic discrete logarithm methods are
outperformed for any $n>N$ where $N\approx2000$, but elliptic curves of
currently recommended key sizes ($n\approx160$) are not immediately
threatened.
%
The analysis can be easily generalized to other extension fields.

**Category / Keywords: **Elliptic Curve Cryptography, DLP, Polynomial System Solving

**Date: **received 19 Mar 2012, last revised 20 May 2012

**Contact author: **christophe petit at uclouvain be, jjq@uclouvain be

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

**Version: **20120520:135154 (All versions of this report)

**Short URL: **ia.cr/2012/146

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]