Are there any proofs that cryptographic functions on an elliptic curve are any m

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?

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.