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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \oplus} to yield Q. The discrete logarithm is called the index of Q with respect to P, and
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 [1][2] and Pollard’s rho algorithm [3] 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 immediately be broken by a polynomial-time solution 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, and information is redacted from published sources in those countries as well as Germany, Switzerland, and probably New Zealand as well.
The NSA probably (in effect, if not through an official quid pro quo) gave up most of its theoretical cryptanalysis and cryptology on elliptic curves as a bargaining chip in exchange for cementing NSA’s access to raw surveillance intelligence throughout the “Western” world, as most of the countries of the Trilateral Commission and Bilderberg Meetings humored dumb Americans who couldn’t crack their crypto.
And for as much as the NSA used to prize secrecy and loyalty, there has been a falling away at the agency toward a general homeland security labor union beat cop mentality of establishing “fusion centers” for domestic surveillance, hustling travelers at airports with random searches, and similar low-intelligence and mostly ineffectual security theater.
Alan Turing built “the Bombe” that cracked the codes of Germany’s Enigma cipher machine, and again, as much as NSA would value secrecy and loyalty, there are certain things about those top secret government places, which when we don’t hear the noise and the chatter of them abroad, we know simply are not happening. «Fait accompli» and they have the intelligence already by some preprogrammed or automated process, or else they simply don’t care and it’s someone else’s job to find it out for them.