In the paper Koblitz and Menezes say "it is conceivable that the NSA has found (or believes that there might exist) a similar algorithm that requires far less precomputation."
This made we wonder; are there any historic example(s) of an algorithm we have improved over time which lead to the side stepping of a previously unavoidable and large pre-computation?
It is not a common occurrence, but it does happen occasionally.
Once upon a time the best known way to compute discrete logarithms was Shanks's Baby-Step Giant-Step. This method begins by constructing a table of size sqrt(p), and then finds a logarithm in time sqrt(p) as well. But in 1978, Pollard came up with the rho algorithm, which did not require any storage beyond 2 group elements, and had the same asymptotic runtime! This method relies on collision-finding, and is still the best algorithm today---in a modified fashion to make it parallelizable---to attack elliptic curves.
Another example happened in integer factorization, but is more nuanced. In the early 1980s, the best known integer factorization algorithm to break semi-primes (i.e., RSA keys) was the quadratic sieve. Now, the quadratic sieve runs in time exp( sqrt( log n log log n ) ), but also requires storage proportional to the size of its factor base---exp( 1/2 sqrt( log n log log n ) ). Then in 1985 Lenstra came up with the elliptic curve method, which once again requires little storage and has the same asymptotic runtime as the quadratic sieve. In practice, however, the quadratic sieve will be faster for RSA numbers. And in 1990, the number field sieve improved the running time to something curve-based methods could not match.
Seems like either the NSA has easy methods to crack ECC that they think will be public knowledge in the immediate future(unlikely but who knows), or they can't break ECC and are trying to push people away from it for the NSA's own own good
[+] [-] tptacek|10 years ago|reply
A seriously good read if you're even a little interested in elliptic curve.
[+] [-] YAYERKA|10 years ago|reply
>3.2. Does NSA have an $n^{1/3}$-algorithm for finding elliptic curve discrete logs? ...
In 2013 Bernstein and Lange described such an algorithm albeit with intractable pre-computation costs. [https://www.iacr.org/conferences/asiacrypt2013/slides/44.pdf]
In the paper Koblitz and Menezes say "it is conceivable that the NSA has found (or believes that there might exist) a similar algorithm that requires far less precomputation."
This made we wonder; are there any historic example(s) of an algorithm we have improved over time which lead to the side stepping of a previously unavoidable and large pre-computation?
[+] [-] pbsd|10 years ago|reply
Once upon a time the best known way to compute discrete logarithms was Shanks's Baby-Step Giant-Step. This method begins by constructing a table of size sqrt(p), and then finds a logarithm in time sqrt(p) as well. But in 1978, Pollard came up with the rho algorithm, which did not require any storage beyond 2 group elements, and had the same asymptotic runtime! This method relies on collision-finding, and is still the best algorithm today---in a modified fashion to make it parallelizable---to attack elliptic curves.
Another example happened in integer factorization, but is more nuanced. In the early 1980s, the best known integer factorization algorithm to break semi-primes (i.e., RSA keys) was the quadratic sieve. Now, the quadratic sieve runs in time exp( sqrt( log n log log n ) ), but also requires storage proportional to the size of its factor base---exp( 1/2 sqrt( log n log log n ) ). Then in 1985 Lenstra came up with the elliptic curve method, which once again requires little storage and has the same asymptotic runtime as the quadratic sieve. In practice, however, the quadratic sieve will be faster for RSA numbers. And in 1990, the number field sieve improved the running time to something curve-based methods could not match.
[+] [-] pearlsteinj|10 years ago|reply