To Certicom
ECC Info
Contact Us

 

2 The Elliptic Curve Discrete Logarithm Problem (ECDLP)

This section provides a brief overview of state-of-the-art algorithms known for solving the elliptic curve discrete logarithm problem. For more information, the reader is referred to Chapter 3 of the Handbook of Applied Cryptography [MVV].

2.1 The discrete logarithm problem

Roughly speaking, the discrete logarithm problem is the problem of "inverting" the process of exponentiation. The problem can be posed in a variety of algebraic settings. The most commonly studied versions of this problem are:

1. The discrete logarithm problem in a finite field (DLP): Given a finite field Fq and elements g, h Fq, find an integer l such that gl = h in Fq, provided that such an integer exists.

2. The elliptic curve discrete logarithm problem (ECDLP): Given an elliptic curve E defined over a finite field Fq, and two points P, Q E(Fq), find an integer l such that lP = Q in E, provided that such an integer exists.

On the surface, these two problems look quite different. In the first problem, "multiplicative" notation is used: gl refers to the process of multiplying g by itself l times. In the second problem, "additive" notation is used: lP refers to the process of adding P to itself l times.

If one casts these notational differences aside, then the two problems are abstractly the same. What is intriguing about the two problems, however, is that the second appears to be much more difficult than the first. The fundamental reason for this is that the algebraic objects in the DLP (finite fields) are equipped with two basic operations: addition and multiplication of field elements. In contrast, the algebraic objects in the ECDLP (elliptic curves over finite fields) are equipped with only one basic operation: addition of elliptic curve points. The additional structure present in the DLP has led to the discovery of the index-calculus methods, which have a subexponential running time. Elliptic curves do not possess this additional structure, and for this reason no one has been able to apply the index-calculus methods to the ECDLP (except in very special and well-understood cases). This absence of subexponential-time algorithms for the ECDLP, together with efficient implementation of the elliptic curve arithmetic, is precisely the reason that elliptic curve cryptosystems have proven so attractive for practical use.

2.2 Algorithms known for the ECDLP

This section briefly overviews the algorithms known for the ECDLP. All of these algorithms take fully exponential time.

The notation used is the following:

  • q is the order of the underlying finite field.
  • Fq is the underlying finite field of order q.
  • E is an elliptic curve defined over Fq.
  • E(Fq) is the set of points on E both of whose coordinates are in Fq, together with the point at infinity.
  • P is a point in E( Fq).
  • n is the order of the point P.
  • Q is another point in E( Fq).

The ECDLP is: Given q, E, P, n and Q, find an integer l, 0 l n - 1 such that lP = Q, provided that such an integer exists.

For the remainder of the discussion, we shall only considers instances of the ECDLP for which the integer l exists.

  1. Naive exhaustive search.
    In this method, one simply computes successive multiples of P: P, 2P, 3P, 4P, ... until Q is obtained. This method can take upto n steps in the worst case.

  2. Baby-step giant-step algorithm.
    This algorithm is a time-memory trade-off of the method of exhaustive search. It requires storage for about points, and its running time is roughly 2 steps in the worst case.

  3. Pollard's rho algorithm.
    This algorithm, due to Pollard [Pollard], is a randomized version of the baby-step giant-step algorithm. The expected running time of roughly steps is subject to the ability to simulate a random walk in the group generated by P. Teske [Teske] showed how this can be done efficiently.

  4. Distributed version of Pollard's rho algorithm.
    Van Oorschot and Wiener [VW] showed how Pollard's rho algorithm can be parallelized so that when the algorithm is run in parallel on m processors, the expected running time of the algorithm is roughly / M steps. That is, using M processors results in an m-fold speed-up. Gallant, Lambert and Vanstone [GLV] improved this parallelized algorithm for the class of binary anomalous curves, which are curves over F2m but defined over F2 and which have exactly two points over F2. In this case, the expected running time of /M steps can be reduced by . For any curve, their techniques can be used to reduce the expected running time by up to a factor of .

    This distributed version of Pollard's rho algorithm is the fastest general-purpose algorithm known for the ECDLP.

  5. Pohlig-Hellman algorithm.
    This algorithm, due to Pohlig and Hellman [PH], exploits the factorization of n, the order of the point P. The algorithm reduces the problem of recovering l to the problem of recovering l modulo each of the prime factors of n; the desired number l can then be recovered by using the Chinese Remainder Theorem.

    The implications of this algorithm are the following. To construct the most difficult instance of the ECDLP, one must select an elliptic curve whose order is divisible by a large prime n. Preferably, this order should be a prime or almost a prime (i.e. a large prime n times a small integer h). The elliptic curves in the exercises and challenges posed here are all of this type.

  6. A special class of elliptic curves: supersingular curves.
    Menezes, Okamoto and Vanstone [MOV, Menezes] and Frey and Rück [FR] showed how, under mild assumptions, the ECDLP in an elliptic curve E defined over a finite field Fq can be reduced to the DLP in some extension field FqB for some B 1, where the index-calculus algorithms apply. The reduction algorithm is only practical if B is small - this is not the case for most elliptic curves. To ensure that this reduction algorithm does not apply to a particular curve, one only needs to check that n, the order of the point P, does not divide qB - 1 for all small B for which the DLP in FqB is intractable (1 B 2000 / (log2q) suffices).

    For the very special class of supersingular elliptic curves, it is known that B 6. It follows that the reduction algorithm yields a subexponential-time algorithms for the ECDLP in supersingular curves.
  7. Another special class of elliptic curves: anomalous curves.
    Smart [Smart] and Satoh and Araki [SA] independently showed that the ECDLP for the special class of anomalous elliptic curves is easy to solve. An anomalous elliptic curve over Fq is an elliptic curve over Fq which has exactly q points. This attack does not extend to any other classes of elliptic curves. Consequently, by verifying that the number of points on an elliptic curve does not equal the number of elements in the underlying field, one can easily ensure that the Smart-Satoh-Araki attack does not apply to a particular curve.


2.3 Is there a subexponential-time algorithm for ECDLP?

Whether or not there exists a subexponential-time algorithm for the ECDLP is an important unsettled question, and one of great relevance to the security of ECC. It is extremely unlikely that anyone will ever be able to prove that no subexponential-time algorithm exists for the ECDLP. (Analogously, it is extremely unlikely that anyone will every be able to prove that no polynomial-time (efficient) algorithm exists for the integer factorization and discrete logarithm problems.) However, much work has been done on the DLP over the past 20 years, and more specifically on the ECDLP over the past 12 years. No subexponential-time algorithm has been discovered for the ECDLP, confirming the widely-held belief that no such algorithm exists.

In particular, Silverman and Suzuki [SS] showed that it is very unlikely that there is an index calculus for the ECDLP which is analogous to the index calculus for the DLP in a finite field.

A summary of the work done on the ECDLP and further references can be found in the Certicom whitepaper [Certicom].

 

 

 

Copyright © Certicom Corp., 1997-2000. All rights reserved.
Information subject to change. http://www.certicom.com