### Question 31. What are Elliptic Curve Cryptosystems?

*Elliptic curve cryptosystems* [Mil86]
[Kob87] are analogs of public-key
cryptosystems such as RSA (see Question 8) and ElGamal
(see Question 29), in which modular multiplication
is replaced by the elliptic curve addition operation.

The curves used in elliptic curve analogs of discrete logarithm cryptosystems
are normally of the form

*y*^{2} = *x*^{3} + *ax* + *b* (mod *p*),

where *p* is prime. The problem tapped by the discrete logarithm
analogs in elliptic curves is the elliptic curve logarithm problem, defined
as follows: given a point *G* on an elliptic curve with order *r
*(number of points on the curve) and another point *Y *on the curve,
find a unique *x* (0 *x* *r* - 1) such that *Y*
= *xG*, i.e., *Y* is the *x*th multiple of *G*.

Until recently, the best attacks on elliptic curve logarithm problems
were the general methods applicable to any group. The methods have a running
time of about a constant times the square root of *r *on average,
which is much slower than specialized attacks on certain types of groups.
The lack of specialized attacks means that shorter key sizes for elliptic
cryptosystems give the same security as larger keys in cryptosystems that
are based on discrete logarithm problem . However, for certain elliptic
curves, Menezes, Okamoto, and Vanstone [MOV90] have been able to reduce
the elliptic logarithm problem to a discrete logarithm problem. It is possible
that algorithm development in this area will change the security of elliptic
curve discrete logarithm cryptosystems to be equivalent to that of general
discrete logarithm cryptosystems; this is an open research problem.

Elliptic curve analogs of RSA have been proposed, and they are based
on the difficulty of factoring, just as RSA is. The elliptic curve analogs
do not seem to offer any significant advantage over RSA, as the underlying
problem is the same and the key sizes are similar for equivalent levels
of security. Two of their purported advantages resistance to "low-exponent"
attacks and to signature forgery against a chosen message attack have recently
been shown not to hold (see [KO95] and
[Kal95]).