Paper 2010/157

Elliptic Curve Discrete Logarithm Problem over Small Degree Extension Fields. Application to the static Diffie-Hellman problem on $E(\F_{q^5})$

Antoine Joux and Vanessa Vitse

Abstract

In 2008 and 2009, Gaudry and Diem proposed an index calculus method for the resolution of the discrete logarithm on the group of points of an elliptic curve defined over a small degree extension field $\F_{q^n}$. In this paper, we study a variation of this index calculus method, improving the overall asymptotic complexity when $\log q \leq c n^3$. In particular, we are able to successfully obtain relations on $E(\F_{p^5})$, whereas the more expensive computational complexity of Gaudry and Diem's initial algorithm makes it impractical in this case. An important ingredient of this result is a new variation of Faugère's Gröbner basis algorithm F4, which significantly speeds up the relation computation and might be of independent interest. As an application, we show how this index calculus leads to a practical example of an oracle-assisted resolution of the elliptic curve static Diffie-Hellman problem over a finite field on $130$ bits, which is faster than birthday-based discrete logarithm computations on the same curve.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
elliptic curvediscrete logarithm problem (DLP)index calculusGröbner basis computationsummation polynomialsstatic Diffie-Hellman problem (SDHP)
Contact author(s)
vanessa vitse @ prism uvsq fr
History
2010-03-24: received
Short URL
https://ia.cr/2010/157
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/157,
      author = {Antoine Joux and Vanessa Vitse},
      title = {Elliptic Curve Discrete Logarithm Problem over Small Degree Extension Fields. Application to the static Diffie-Hellman problem on $E(\F_{q^5})$},
      howpublished = {Cryptology ePrint Archive, Paper 2010/157},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/157}},
      url = {https://eprint.iacr.org/2010/157}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.