Paper 2012/146

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
Elliptic Curve CryptographyDLPPolynomial System Solving
Contact author(s)
christophe petit @ uclouvain be
jjq @ uclouvain be
History
2012-05-20: revised
2012-03-22: received
See all versions
Short URL
https://ia.cr/2012/146
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/146,
      author = {Christophe Petit and Jean-Jacques Quisquater},
      title = {On Polynomial Systems Arising from a Weil Descent},
      howpublished = {Cryptology ePrint Archive, Paper 2012/146},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/146}},
      url = {https://eprint.iacr.org/2012/146}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.