Re: Elliptic curves, current status?

At 12:07 PM 11/25/95, James A. Donald wrote:

....
>Can someone tell me the true story?

Not with any assurance. I don't trust my own knowledge yet.
I think that the opinion is that the discrete log problem is harder
with elliptic curves than for prime modulus arithmetic for numbers
of a given size. That is why you can use fewer bits.
The inner loop in some elliptic curve systems is not multiply-add
(as is the case with number fields)
but other operations that are as efficient with gates but less
efficient with normal machine instructions.

There are probably an order of magnitude more people that
have studied and published about the problems of breaking
prime modulus crypto than elliptic curves. Perhaps progress
will be faster should elliptic curves be studied by more people.
There are a lot of tricks to speed up discrete logs in for prime
modulus schemes that don't seem to work for elliptic curves.

There are many parameters to an elliptic curve crypto system.
I haven't seen any taxonomy of which kinds are good and which
have been shown to be week. In contrast there seems to be a
consensus about how to pick primes for RSA or Diffie-Hellman.

I am certainly no expert. Perhaps this will prompt comments
from someone who can point to real information.

On Sun, 26 Nov 1995, Norman Hardy wrote:

> There are many parameters to an elliptic curve crypto system.
> I haven't seen any taxonomy of which kinds are good and which
> have been shown to be week. In contrast there seems to be a
> consensus about how to pick primes for RSA or Diffie-Hellman.

The IEEE p1363 group's working draft on elliptic curve standard may help 
you here.  You can find it at ftp://ftp.rsa.com/pub/p1363/draft/ec.ps

One reason for confusion about the speed of elliptic curve cryptosystems is 
the small number of implementations.  A paper in Crypto 95 claimed that 
for doing key exchange, an elliptic curve algorithm takes about the same 
time and has about the same level of security as DH with 512 bit modulus, 
and that elliptic curve has a speed advantage if greater security is 
desired.

Wei Dai