A Riddle Wrapped in an Enigma [pdf]

http://eprint.iacr.org/2015/1018.pdf

by tptacek • 11 years ago

19 8 11 years ago

eprint.iacr.org

tptacek• 11 years ago

This is Koblitz and Menezes, two giants of academic cryptography, evaluating conspiracy theories about the NSA tampering with crypto standards.

A seriously good read if you're even a little interested in elliptic curve.

pearlsteinj• 11 years ago

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

YAYERKA4• 11 years ago

Thanks for posting; found many sections interesting especially 3.2;

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?

pbsd2• 11 years ago

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.

YAYERKA4• 11 years ago

Thanks for your response; 1971 Shanks' BSGS improvement to 1974 Pollard Rho for DLP is indeed a nice example.

A Riddle Wrapped in an Enigma [pdf]

Related Stories