Proof of elliptic curve difficulty

Question

Are there any proofs that cryptographic functions on an elliptic curve are any more difficult than the analogues over modulo arithmetic?

While at present, ECC appears to be more difficult, as it is not as advanced as research into RSA etc., it seems to me there should be no reason why ECC is much stronger than, say, RSA and that the advantage of shorter keys might just be temporary.

I was wondering if there were any proofs that ECC was at least as strong as RSA etc. such that if you use a 2048 bit ECC key, then it is at least as strong as 2048 bit RSA key? I.e., ECC is not weaker than RSA for a given key length?

Answer 1

There are very few non-trivial proven lower bounds in computational complexity, and none whatsoever in cryptography, as far as I know.

Almost all results are of the form "If X is infeasible, then so is Y." For example, "If AES is a secure pseudo-random function, then so is CBC-AES given parameters such-and-such."

RSA and traditional Diffie-Hellman use integers and finite fields (integers modulo a prime). Those mathematical objects have, in some ways, "too much structure"; there are short cuts to factoring and to discrete log, so you have to use much larger keys than you would expect if you did not know about those short cuts.

As far as anyone knows, elliptic curves have "just enough" structure to do cryptography, but no additional structure that can be exploited to extract discrete logarithms via some short cut. That is why the number of bits for EC algorithms is generally chosen to be something like twice the symmetric key length, instead of something like 2048+ bits for RSA.

If you want some mathematical details, this thesis has a good overview:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.132.6034&rep=rep1&type=pdf

But again, none of these problems have been proven to be intractable. Maybe there is some linear-time factoring algorithm out there. Maybe elliptic curves -- or the particular curves approved by NIST -- have some unknown structure that could allow discrete log approaches with comparable complexity to those for finite fields. Maybe the NSA's mathematicians have found that structure ahead of everybody else...

Answer 2

I haven't seen any such proof. While elliptic curves lack certain properties, they appear quite 'rich' in some respects and I wouldn't be surprised to find that they have enough structure and in the end they are found to be no more difficult than the analogous operations under modulo arithmetic.

There have been recent advances on EC of small characteristic:

http://eprint.iacr.org/2013/400.pdf

The recent revelations on the NSA hobbling various standards could throw some doubt on whether there are hidden weaknesses in the proposed 'standard curves' and also whether ECC is much weaker than we think. Given that the NSA push for it to be adopted and apparently have deliberately pushed weak crypto in the past, it could be a sign that they know something we don't: http://www.nsa.gov/business/programs/elliptic_curve.shtml