# How Significant is the New Quasi-Polynomial-Time Attack on Fixed Characteristic Discrete Logarithms?

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?

• 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$). – Aleph Jun 26 '19 at 12:14
• Shouldn't this comment be an answer? – Geoffroy Couteau Aug 29 '19 at 18:54