There is a new paper by Kleinjung and Wesolowski on eprint that claims and proves a new attack on the discrete logarithm problem in finite fixed characteristic fields in quasi-polynomial time.

Concretely a run-time of $$(pn)^{2\log_2n+O(1)}$$ is claimed for discrete logarithms in the group $\mathbb F^\times_{p^n}$.

Of course I did some calculations and they ended up showing that for a 2048-bit modulus, i.e. $(p,n)$ such that $p^n\approx 2^{2048}$ this expression evaluates to at least $\approx 2^{280}$ (and up to about $2^{310}$ for "bad" pairs). I also computed a guesstimate for varying modulus sizes and it showed that this function grows so fast that even at about 150-200 bits this already crosses the $2^{100}$ mark and the $2^{200}$ mark at about 1200-bit.

So my question:
What is actually the significance of this work? Does it merely provide a provably sub-exponential algorithm that can't compete e.g. with the non-provably fast GNFS / Function Field Sieve? Is it actually a practically relevant improvement over the GNFS / FFS?

  • 3
    $\begingroup$ This is a major result, but not for cryptanalytic reasons. The paper is not intended as an attack; indeed, it has been known for a while that one shouldn't rely on the DLP in $\mathbb{F}_{p^n}^\times$ with small $p$ for security. In cryptography (such as classical DH) we typically use very large $p$. Note that the algorithm you want to compare with here is not the number field sieve (which you might use if $p$ is much larger than $n$) but rather the function field sieve (which is preferable when $p$ is much smaller than $n$). $\endgroup$ – Aleph Jun 26 '19 at 12:14
  • $\begingroup$ Shouldn't this comment be an answer? $\endgroup$ – Geoffroy Couteau Aug 29 '19 at 18:54

Your Answer

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

Browse other questions tagged or ask your own question.