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 '17 at 12:00
  • $\begingroup$ @fgrieu That certainly addresses the first question, thanks. What about characteristic 3? $\endgroup$ – Rodrigo Jun 10 '17 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 '17 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 '17 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$ – Samuel Neves Jun 10 '17 at 21:28

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.

| improve this answer | |
  • 2
    $\begingroup$ Pierrick Gaudry, not Patrick. ;) $\endgroup$ – fkraiem Jun 9 '18 at 6:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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