Abstract. This report discusses the elliptic curve discrete logarithm problem and the known methods to solve it. We consider the implications of these methods for choosing the domain parameters in elliptic curve based cryptographic schemes. We also study s

8S.D.GALBRAITH AND N.P.SMART

We define a function d on the group

d :G →{0,1}

such that d (g )=1around 1/2t of the time.For example,the function d is often defined by returning d (g )=1if a certain subset of t of the bits representing a group element R are set to zero.The elements in G for which d (g )=1will be called distinguished .

Now it is only the distinguished group elements which are transmitted back to the central server.In other words,only 1in 2t points in the random walk are sent to the server.This means that one expects the random walks to need to continue another 2t steps in the worst case before a collision occurs between two random walks.Hence,the computing time now becomes O √+2

t −1 in the average case,whilst the storage becomes O √l/2t .

Both these complexity estimates are for the average case running time and storage requirements.Since the algorithms are Las Vegas in nature there is the possibil-ity that they never terminate (although this is highly unlikely).In addition the distribution of the running time can have quite a large variance.

One might be tempted to balance the above two equations by choosing 2

t −1≈ πl/2/m so that the time requirement is O (√l/m )while the space requirement is O (m ).In practice this is not what is done,since any single processor probably

cannot execute 2t =O (√l/m )operations.Instead,the space requirement is chosen

in such a way that the central server has enough memory,and that single processors can produce distinguished points at an convenient rate (for instance,one or two distinguished points each day).

It must be remembered that all the distinguished points are sent to a central server where they are stored.This leads to practical memory and network consid-erations which are an obstacle to performing this method in very large groups.

Finally,we note that a parallel random walk attack similar to the one mentioned above is known for finding collisions in cryptographic hash functions.This means that elliptic curve cryptosystems should have parameter sizes chosen according to the same security criteria as hash function output sizes.Implication 3.When choosing elliptic curve parameter sizes it must be remem-bered that the work effort required is essentially reduced by a linear factor in terms of the number of processors available to an attacker.

Elliptic curve parameter sizes should be chosen to be at least as large as recom-mended hash function output sizes.

2.5.Practical considerations.As already remarked it is usual to choose

l ≈N,

and general theory implies that N ≈q .So in most fielded elliptic curve cryptosys-tems we have

l ≈q