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, 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.

  • $\begingroup$ Good question, but isn't it a bit hard to answer "no", considering that anyone might both propose and recommend virtually anything? $\endgroup$ May 29 '13 at 7:55
  • $\begingroup$ Right, there is more to it. $\endgroup$ May 29 '13 at 9:24
  • 4
    $\begingroup$ It's worth pointing out that these new results have effectively killed pairings over binary curves (as seen on this question) $\endgroup$ May 29 '13 at 12:37
  • $\begingroup$ @Henrick Hellström: For a basic case: what about an anolog of DSA on $GF(2^{4099})$ [NOT $GF(2^{4096})$ as I wrote previously, showing my serious lack of understanding]? Is the technique in the paper directly applicable, or is there some catch, like $6120$ being smooth, rather than prime? $\endgroup$
    – fgrieu
    May 29 '13 at 15:44
  • 3
    $\begingroup$ Yes, the shape of the field has much to do with the efficiency of the new algorithms. For example $6120$ was represented as $\mathbb{F}_{ {2^{24}}^{255} }$, and more generally the method currently requires that the base field ($2^{24}$) be larger than the extension degree ($255$). For primes like $4099$, we can't just change the representation of the field to match our needs. One possible solution, suggested by Joux, is to embed $\mathbb{F}_{2^{4099}}$ in $\mathbb{F}_{{2^{4100}}^{2\cdot 4099}}$, which doesn't look too good in practice. So prime exponents are safe for now. $\endgroup$ May 29 '13 at 17:13

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.

  • $\begingroup$ Many thanks! I'll try to assimilate that dense answer before accepting it; that'll take a week, at least. $\endgroup$
    – fgrieu
    May 31 '13 at 4:53

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.