Elliptic curve discrete logarithm problem in characteristic two


Several recent preprints have discussed summation polynomial attacks on the ECDLP in characteristic 2:

  • eprint 2015/310, New algorithm for the discrete logarithm problem on elliptic curves, by Igor Semaev.
  • eprint 2015/319, Point Decomposition Problem in Binary Elliptic Curves, by Koray Karabina.
  • arxiv 1503.08001, Notes on summation polynomials, by Michiel Kosters and Sze Ling Yeo.

To recall some history, in 2004 Semaev introduced a fundamental new idea for index calculus algorithms for the ECDLP. Fix an elliptic curve $latex E$ over a field $latex K$. Semaev’s summation polynomials $latex S_m( x_1, dots, x_m )$ have the property that if $latex S_m( a_1, dots, a_m ) = 0$ for some field elements $latex a_1, dots, a_m in K$ then there are elliptic curve points $latex (a_1, b_1), dots, (a_m,b_m)$ on $latex E(overline{K})$ such that $latex (a_1, b_1) + cdots + (a_m,b_m) = 0$.
Gaudry and Diem explored how to…

View original post 1,278 more words


Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s