Do recent announcements about solving the DLP in $GF(2^{6120})$ apply to schemes proposed for cryptographic use?

Question

A recent paper by Göloğlu, Granger, McGuire, and Zumbrägel: Solving a 6120-bit DLP on a Desktop Computer seems to "demonstrate a practical DLP break in the finite field of $2^{6120}$ elements, using just a single core-month". They credit a 2012 paper by Antoine Joux: Faster index calculus for the medium prime case. Application to 1175-bit and 1425-bit finite field for paving the way they explore. In 2013 Joux published A new index calculus algorithm with complexity $L(1/4+o(1))$ in very small characteristic, and very recently announced he "is able to compute discrete logarithms in $GF(2^{6168})=GF({(2^{257})}^{24})$ using less than 550 CPU.hours". It seems the field (pun intended) of DLP in $GF(2^n)$ is in ebullition.

Current French official recommendations (section 2.2.1.3), updated June 2012, do distance themselves from schemes based on the DLP in $GF(2^n)$, but only mildly. If such scheme is used, the requirement is that $n\ge 2048$ bits up to year 2030, and $n\ge 3072$ bit afterwards, with subgroups of order a multiple of a prime of at least 200 bits. It is recommended to prefer a scheme not based on the DLP in $GF(2^n)$, and if one is used, that the order of the subgroup is prime.

How do the progress reported in the above papers translate into actual breaks for schemes proposed for cryptographic use, based on arithmetic in $GF(2^n)$, and conforming to the quoted recommendations? What are such schemes?

Note: related to this old question; and even closer to this recent one, except that I am not only interested in pairing-based schemes, but also more mundane things like a DSA analog over $GF(2^{4099})$, if there can be such a thing.

Answer 1

The quoted recommendations do little to prevent fields that are subject to the recent developments. Take the $\mathbb{F}_{2^{6120}}$ example: it clearly passes the field size criterion, but also the subgroup rule, as the group order $2^{6120} - 1$ has one $1536$-bit prime factor.

Not all binary fields are affected equally, however. Both Göloğlu et al and Joux's approaches descend from the medium-prime function field sieve, and require the field $\mathbb{F}_{2^N}$ to be representable as (among others):

• $\mathbb{F}_{q^n}$, where $q = 2^l$ and $n = 2^{l/k' \cdot d_1}$, $d_1, k'$ constant (Göloğlu et al);
• $\mathbb{F}_{q^n}$, where $q = 2^l$ and $n = 2^{l/k'} - 1$, $k'$ constant (Göloğlu et al);
• $\mathbb{F}_{q^{2n}}$, where $q = 2^{l}$ and $n \le q + \delta,\, \delta \ll q$ (Joux).

When the exponent of the binary field is smooth, we get many choices to try and represent the field in the forms above. Example: $1778 = 7 \cdot (2 \cdot 127)$; $6120 = 24 \cdot (2^{24/3} - 1)$; $6168 = 257\cdot (2\cdot 12)$; etc. When the exponent is prime, however, we have no such luck.

Instead, as Joux suggested, one may embed the target field within a larger field that does: $\mathbb{F}_{q^{2N}}$, where $q = 2^{\lceil \log_2 N \rceil}$. While this solution may be asymptotically satisfactory, the blow up in size increases the bitlength where Joux's algorithm is faster than the regular function field sieve. It is currently unknown what this size may be, but it is likely that is is higher than current common key sizes (1024-4096 bits).

As for actual uses of binary fields, I do not know of any real-world usage of schemes based on the DLP over binary fields (beyond pairings). We have long been avoiding composite degree binary fields for elliptic curves due to their increased susceptibility to index-calculus; it seems that finite fields are now forced to do the same.