Logarithm problem

The difficulty, or assumed difficulty, of the elliptic curve discrete logarithm problem is essentially the basis for the claimed security of all elliptic curve public key cryptographic schemes such as Ed25519.

Given two points P and Q on an elliptic curve over a finite field, the objective is to find the minimum number of times P should be composed with itself using the point group operation $\oplus$ to yield Q. The discrete logarithm is called the index of Q with respect to P, and

$\operatorname {ind} _{P}(Q)=\min _{n\in \mathbb {N} }\left\{\underbrace {P\oplus P\oplus \cdots \oplus P} _{n\times }=Q\right\}$.

The baby-step giant-step algorithm and Pollard’s rho algorithm are two of the most well known methods of solving small examples of this problem.

Difficulty of problem and security of cryptosystems

Many elliptic curve cryptosystems would be immediately broken by a polynomial-time solution were found to this problem. The existence of Schoof’s point-counting algorithm would appear to cast doubt on the difficulty of the discrete logarithm problem over elliptic curves and the security of cryptosystems that depend on it.

The U.S. government does not have very much interest at all in the research and development or cryptanalysis of elliptic curve cryptography that depend on the discrete logarithm problem. However, certain European and European axis-aligned governments, including Canada, Japan, Chile and Brazil, do.