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?
$\begingroup$
$\endgroup$
9
-
3$\begingroup$ Related question. $\endgroup$– fgrieu ♦Commented Jun 10, 2017 at 12:00
-
$\begingroup$ @fgrieu That certainly addresses the first question, thanks. What about characteristic 3? $\endgroup$– user1868607Commented 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 ♦Commented 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$– user47922Commented 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$– Samuel NevesCommented Jun 10, 2017 at 21:28
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
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:
See in particular §10.2, ‘A subexponential algorithm for elliptic curves over $\mathbb F_{2^n}$?’, p. 18.
answered Jun 9, 2018 at 2:35
-
2