3
$\begingroup$

There has been recent work, due to Joux, Gologlu, Zumbragel and others which has developed efficient algorithms for discrete logarithms in small (and specifically binary) characteristics, where the exponents have some special form. See the discussion in the questions

how-robust-is-discrete-logarithm-in-GF(2^n)

and

do-recent-announcements-about-solving-the-dlp-in-gf26120-apply-to-schemes?noredirect=1&lq=1

My understanding is that discrete logarithms in $\operatorname{GF}(2^n)$ where $n$ is large and has no special for is still relatively robust to attacks.

Here is the question, say I pick $n$ large enough such that the multiplicative group $\operatorname{GF}(2^n)^{\ast}$ has no small subgroups. So either $2^n-1$ is prime, or $n$ is so large and well chosen that the largest subgroup is large enough.

Would the best algorithm in this case still be baby-step-giant-step for the discrete logarithm? Or something else of still exponential (in $n$) time and memory complexity?

Improve this question
$\endgroup$
3
  • $\begingroup$ Asymptotically, every small characteristic field is broken by the quasi-polynomial algorithms of either Barbulescu et al. or Granger et al.. In practice, however, a prime exponent $GF(2^p)$ is safer than most others, since you have to embed that field in a larger one for the attack to work. The current record for a prime-exponent field is $GF(2^{1279})$; the record for arbitrary exponent is $GF(2^{9234})$. $\endgroup$
    – Samuel Neves
    Mar 13, 2018 at 18:17
  • $\begingroup$ @SamuelNeves please see edited answer. $\endgroup$
    – kodlu
    Mar 13, 2018 at 22:06
  • 1
    $\begingroup$ Sounds about right. $\endgroup$
    – Samuel Neves
    Mar 14, 2018 at 5:10

1 Answer 1

Reset to default
1
$\begingroup$

Edit: My hunch that the best complexity is exponential was incorrect. It is actually quasi-polynomial (thanks to Samuel Neves for his comment).

Recall that Coppersmith's algorithm has complexity $$ L_{2^n}(1/3,c) $$ for a small constant $c,$ while even for $n$ prime, which is the hardest case, discrete logarithms over $GF(2^n)$ using Barbulescu et. al.'s method have quasi polynomial complexity $$ O(2^{c(\log n)^2})\asymp c' n^{c \log n}. $$

Note that the authors state "The crossing point between the (best knoen before) L(1/4) algorithm and our quasi-polynomial one is not determined yet".

Improve this answer
$\endgroup$

Your Answer

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

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