The following is a quotation from my cryptography course:

Recent results on the discrete logarithm raise big concerns on the security of elliptic curves over a binary field.

What are these results? Also, is characteristic three safe?

  • 3
    $\begingroup$ Related question. $\endgroup$
    – fgrieu
    Jun 10, 2017 at 12:00
  • $\begingroup$ @fgrieu That certainly addresses the first question, thanks. What about characteristic 3? $\endgroup$ Jun 10, 2017 at 12:01
  • 1
    $\begingroup$ This is flying quite above my head, but my understanding is that the Joux results apply to some level for small characteristics larger than two. Try his bibliography on Discrete Logarithms. $\endgroup$
    – fgrieu
    Jun 10, 2017 at 13:54
  • 1
    $\begingroup$ Not a full answer, but here's an attack on characteristic three curves involving Weil descent. $\endgroup$
    – user47922
    Jun 10, 2017 at 15:29
  • 1
    $\begingroup$ The usual reason to distrust low-characteristic elliptic curve groups is the Petit-Quisquater result, which suggests the discrete logarithm might be subexponential there. But as far as I know, the real-world relevance of this result is still in question. $\endgroup$ Jun 10, 2017 at 21:28

1 Answer 1


There is no known subexponential-cost algorithm for computing discrete logs in elliptic curves over fields of small characteristic—barring standard generic algorithms on groups of smooth order, transfers to $\operatorname{GF}(2^n)$, etc.—but there seems to be exploitable structure that just hasn't been worked out yet. The most recent survey seems to be from 2015:

Stephen D. Galbraith and Pierrick Gaudry, ‘Recent progress on the elliptic curve discrete logarithm problem’, IACR Cryptology ePrint Archive: Report 2015/1022, 2015-10-22.

See in particular §10.2, ‘A subexponential algorithm for elliptic curves over $\mathbb F_{2^n}$?’, p. 18.

  • 2
    $\begingroup$ Pierrick Gaudry, not Patrick. ;) $\endgroup$
    – fkraiem
    Jun 9, 2018 at 6:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.