25
$\begingroup$

"Normal" discrete logarithm based cryptosystems (DSA, Diffie-Hellman, ElGamal) work in the finite field of integers modulo a big prime $p$. However, there exist other finite fields out there, in particular binary fields $GF(2^n)$. There is a specific attack described by Coppersmith for discrete logarithm in a binary field, and it was later on refined into the more general Function Field Sieve by Adleman and Huang. The FFS was used by Joux and Lercier to obtain the current record in $GF(2^n)$ discrete logarithm, where $n = 613$.

What I would like to know is:

  • How does discrete logarithm in $GF(2^n)$ compares to discrete logarithm modulo a prime $p$ of $n$ bits ? At the time when Coppersmith published his algorithm, it made discrete logarithm in binary fields look easier than its prime $p$ counterpart, but the latter also got improved later on.
  • Is it important, for discrete logarithm in $GF(2^n)$, whether $n$ is itself prime or not ? The current record is for $GF(2^{613})$, beating the previous record of $GF(2^{607})$, and both 607 and 613 are prime numbers. Would discrete logarithm in $GF(2^{1024})$ be easier than in $GF(2^{1021})$ ?
$\endgroup$
0

3 Answers 3

15
$\begingroup$

Discrete logarithms in $\mathbb{F}_{p}$ share the same asymptotic complexity as integer factorization for general numbers: $L_p[1/3,1.923]$ for general integers, $L_p[1/3,1.587]$ for special integers. Discrete logarithms in $\mathbb{F}_{p^n}$ have the same asymptotic complexity as factoring special integers, i.e. $L_{p^n}[1/3, 1.587]$, via the Function Field Sieve.

So, extrapolating from the factoring records, we can handwave that a discrete log in $\mathbb{F}_{2^{1021}}$ is an order of magnitude easier than a discrete log modulo a 768-bit general prime, and about the same as modulo a pseudo-Mersenne prime $2^{1021} - c$.

As to whether composite degree extension fields are easier to solve, maybe. It is possible to represent the same composite field in a number of ways (usually known as tower of fields), and it is possible that some representations allow for faster breaks than others. Here's a quote from Andrew Odlyzko's 1985 paper Discrete logarithms and their cryptographic significance:

In fact, these fields may be very weak because of the possibility of moving between the field and its subfields.

However, there is no data on significant asymptotic advantages of composite degree over prime degree (if there was, pairing-based schemes would be toast, as embedding degrees are by and large composite).

One shouldn't also forget to check the smoothness of $p^n-1$, to avoid embarrassing Pohlig-Hellman breaks.

May 2013 Update

It seems that composite degree is indeed weaker than prime degree. The recent results of Göloğlu et al and Joux attack fields $\mathbb{F}_{2^n}$, for composite $n$, much faster than the function field sieve referred above. See this question for more information.

$\endgroup$
6
  • 3
    $\begingroup$ Welcome to Crypto Stack Exchange! Sadly, we don't yet have MatJax Formula support enabled here, so your formulas look a bit raw. Also, your links are somehow missing. $\endgroup$ Aug 19, 2011 at 0:54
  • $\begingroup$ Alright, removed the LaTeX syntax, and did some general fixing (including links). $\endgroup$ Aug 19, 2011 at 11:59
  • $\begingroup$ As we now have working LaTeX syntax, I added the formulas again to your post. Please check that I didn't transform anything wrong. $\endgroup$ Sep 30, 2011 at 18:02
  • 3
    $\begingroup$ There has been recent results that seem relevant to the question, including Göloğlu, Granger, McGuire, and Zumbrägel's Solving a $6120$-bit DLP on a Desktop Computer $\endgroup$
    – fgrieu
    May 29, 2013 at 5:07
  • $\begingroup$ Highly composite extension degree means that the order of the multiplicative group will automatically have some factors. This in turn allows Chinese remainder theorem based attacks on DLP. However, a single large prime factor will still spell trouble for the attacker. For example 2^1024-1=(2^512-1)(2^512+1). The latter factor is a Fermat number F_9 with a known factorization and its largest factor is about 7*10^92. Still very large, but some of the size will get wasted when you have automatic factors. Mersenne primes are good in this respect. $\endgroup$ Jul 3, 2014 at 21:45
8
$\begingroup$

Antoine Joux very kindly sent me the following on the topic:

People worry that [logarithms over fields with composite exponent] might be easier, this is why they use prime exponent. For some factorization of the exponent, viewing the finite field as a tower of extensions $(p^{n_1})^{n_2}$ indeed makes things easier.

See "The function field sieve in the Medium Prime Case" by R. Lercier and myself.


[The portion below, while correct, is not relevant to this question. I have not deleted it as that would leave the comment dangling.]
Elliptic cuves over $GF(2^m)$ where $m$ is composite are potentially vulnerable to attacks based on Weil descent. People wishing to show the state of the art in discrete logarithm computation choose problems with m a prime so that no such shortcuts are possible.

The paper Analysis of the GHS Weil Descent Attack on the ECDLP over Characteristic Two Finite Fields of Composite Degree (2001) by Markus Maurer, Alfred Menezes and Edlyn Teske is the most recent work on the topic I can conveniently find.

$\endgroup$
1
  • $\begingroup$ Note that the Weil descent approach to elliptic curves of composite-degree transfers the discrete logarithm from $E(\mathbb{F}_{2^n})$ to $J(\mathbb{F}_{2^{(n/p)}})$, where $p$ is some divisor of $n$, and $J$ is the Jacobian of a high-degree hyperelliptic curve where the discrete log might be faster. The original question, however, was about discrete logarithms in the base field $\mathbb{F}_{2^n}$; the Weil/Tate pairing might be used to transfer $E(\mathbb{F}_{2^n})$ to $\mathbb{F}_{2^n}$ (MOV and FR attacks). $\endgroup$ Sep 30, 2011 at 21:19
4
$\begingroup$

To complete @Samuel's answer, there are a few shortcuts that can be used when $n$ is composite; however, they only contribute small constant factors, hence they do not change the asymptotic behavior:

  • If $n$ can be divided by $r$, then one can first solve the discrete logarithm in the subfield $GF(2^r)$. In a sieve-based algorithm, this can provide up to half the relations that we need for the final linear algebra step.
  • The final linear algebra step of the FFS computes things modulo $2^n-1$. If $n$ is not prime, then $2^n-1$ is not prime either, and such operations can be implemented more efficiently through the use of the Chinese Remainder Theorem.

Also, if working in a subgroup, one can botch the choice of the subgroup. If $n = rs$ for non-trivial factors $r$ and $s$, then $GF(2^n)^{*}$ has size $2^n-1$, which is a multiple of $2^r-1$. If we choose a subgroup generated by a value $g$ of order $q$ where $q$ divides $2^r-1$, then we are actually computing things in $GF(2^r)$ and we can solve the discrete log by working in that subfield, where attacks are much more efficient, since $r$ is no more than $n/2$. In other words, when choosing the subgroup order $q$ (a prime), we must make sure that $q$ does not divide any $2^r-1$ for any $r$ which divides $n$. A prime $n$ is a simple way to ensure that.

$\endgroup$

Your Answer

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

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