Re: Diffie-Hellman in GF(2^n)?

In article <Pine.SUN.3.91.951110184600.19312B-100000@eskimo.com> you write:
> Most Diffie-Hellman implementations currently use the multiplicative group
> of prime fields.  However, the multiplicative group of finite fields of
> characteristic 2 (GF(2^n)) can also be used and should be easier to
> implement.  Is there any reason why they should not be used?  Does anyone
> know the asymptotic running time of the best algorithm for calculating
> discrete logarithms in GF(2^n)? 

I remember that the discrete log problem is quite a bit easier
in GF(2^n), but I don't remember how much easier.   Let me try
to look it up...

A. Odlyzko has a paper recommending that people should not use
GF(2^n) for discrete log applications; in it he states that you
will need at the minimum n > 800, and probably n > 1500.  (And
you also need to choose n carefully.)  A quote from the abstract:

``Hence the fields GF(2^n) out to be avoided in all cryptographic
applications.''

I don't know enough about number theory to judge for myself;
but you can read the (long) paper yourself at

	ftp://netlib.att.com/netlib/att/math/odlyzko/discrete.logs.ps.Z

I hope this helps!

> I don't know enough about number theory to judge for myself;
> but you can read the (long) paper yourself at
> 
> 	ftp://netlib.att.com/netlib/att/math/odlyzko/discrete.logs.ps.Z

Thanks for the reference.  The paper gives a running time of exp(c(n 
log n)^(1/2)) for discrete log in GF(p) and exp(c*n^(1/3)*(log n)^(2/3)) 
for discrete log in GF(2^n).  However, this paper was published in 1985. 
There is now an algorithm to calculate discrete logs in GF(p) in
exp(c*n^(1/3)*(log n)^(2/3)) (see prime.discrete.logs.ps.Z in the same
directory), so perhaps GF(2^n) isn't so bad after all. 

Wei Dai

I wrote earlier:

> Thanks for the reference.  The paper gives a running time of exp(c(n 
> log n)^(1/2)) for discrete log in GF(p) and exp(c*n^(1/3)*(log n)^(2/3)) 
> for discrete log in GF(2^n).  However, this paper was published in 1985. 
> There is now an algorithm to calculate discrete logs in GF(p) in
> exp(c*n^(1/3)*(log n)^(2/3)) (see prime.discrete.logs.ps.Z in the same
> directory), so perhaps GF(2^n) isn't so bad after all. 

To clarify my earlier post, although both of the latter two algorithms
have a runtime of the form exp(c*n^(1/3)*(log n)^(2/3)), for GF(p)
c=1.922+o(1), for GF(2^n) c=1.405+o(1).  This seems to imply that if 
GF(2^n) is to be used, n needs to be 2.56*log p to achieve a comparable 
level of security to using GF(p).  (2.56=1.922^3/1.405^3)

Wei Dai