Granger et al. recently published a paper about breaking a record for discrete logarithm on the Binary field

They computed the discrete log of $\mathbb{F}_{2^{30750}}$ on 2900 core year of single-core of Intel Xeon Ivy Bridge processor running at 2.6 GHz. The previous record was $\mathbb{F}_{2^{9234}}$ and required 45 core years.

The field $\mathbb{F}_{2^{30750}}$ is extended as $\mathbb{F}_2: \mathbb{F}_{2^{20}}:\mathbb{F}_{2^{30750}}$

To find the discrete logarithm, they select the target element $h_\pi$ by using the digits of $\pi$, as not to be "cooked up", see nothing-up-my-sleeve number


  • What is the aftermath of this work for Cryptography? (DLog is not restricted to Cryptography)

  • The binary extension field is not a nothing-up-my-sleeve number. They choose $30750 = 3 \cdot 10 \cdot (2^{10}+1)$, i.e., it is in the form $\mathbb{F}_{q^3(q+1)}$ so that they can use the twisted Kummer extension. It is mentioned in this case it is much easier than other extensions of the same order of magnitude. It is clear that not every extension can be a Kummer extension.

    • How much easier?
    • On what magnitude are the non Kummer extensions safer?
  • The group order of the extension is $N:= 2^{30750}− 1$, and it has 58 prime factors up to 135-bit size.

    • Is a binary extension field with fewer prime factors safe?
    • Is one with a large factor still safe?
  • What is the fixed characteristic (mentioned on page 3)?

    It turns out that fixed characteristic is used for the computational complexity calculations. A nice explanation is given in here;

    Let $C2^pk^r$ be the cost of an algorithm over a field of characteristic $p$ and size $k$ for some constants $C,r$. We say that it is polynomial for fields of fixed characteristic but exponential in the characteristic.



Your Answer

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