Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

"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(2n). 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(2n) discrete logarithm, where n = 613.

What I would like to know is:

  • How does discrete logarithm in GF(2n) 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(2n), whether n is itself prime or not ? The current record is for GF(2613), beating the previous record of GF(2607), and both 607 and 613 are prime numbers. Would discrete logarithm in GF(21024) be easier than in GF(21021) ?
share|improve this question
add comment

3 Answers 3

up vote 11 down vote accepted

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.

share|improve this answer
2  
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. –  Paŭlo Ebermann Aug 19 '11 at 0:54
    
Alright, removed the LaTeX syntax, and did some general fixing (including links). –  Samuel Neves Aug 19 '11 at 11:59
    
As we now have working LaTeX syntax, I added the formulas again to your post. Please check that I didn't transform anything wrong. –  Paŭlo Ebermann Sep 30 '11 at 18:02
3  
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 –  fgrieu May 29 '13 at 5:07
    
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. –  Jyrki Lahtonen Jul 3 at 21:45
add comment

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.

share|improve this answer
    
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). –  Samuel Neves Sep 30 '11 at 21:19
add comment

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(2r). 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 2n-1. If n is not prime, then 2n-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(2n)* has size 2n-1, which is a multiple of 2r-1. If we choose a subgroup generated by a value g of order q where q divides 2r-1, then we are actually computing things in GF(2r) 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 2r-1 for any r which divides n. A prime n is a simple way to ensure that.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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