14
$\begingroup$

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

Questions:

  • 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 do the non Kummar 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 is 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 $\le 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.

$\endgroup$
  • $\begingroup$ I've emailed one of the authors. While I'll look around for the answers, or someone can give before. $\endgroup$ – kelalaka Aug 12 at 20:28
  • 1
    $\begingroup$ I fixed a typo in group order and a few English expressions. Feel free to undo if you like. $\endgroup$ – kodlu Aug 18 at 22:48

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.