Quoting Glenn McIntosh (neonsignal@meme.net.au):
Ecrypt have published a couple of reports on keysizes. A 512bit EC keysize is roughly equivalent to a 15424 bit RSA keysize. http://www.ecrypt.eu.org/ecrypt2/documents/D.SPA.20.pdf
These are really just a statement of the mathematical difficulty of brute forcing the keys using the best current algorithms, eg a general number field sieve for prime factoring vs a naive meet-in-the-middle attack to find a discrete logarithm. There are no mathematical proofs of the hardness of any of these problems.
As you point out, security also involves other factors - how well an algorithm has been examined by third parties, the soundness of the protocols, endpoint security, and so on.
Thank you. I note, without special objection to the elliptic curve cryptography recommendation but merely for completeness, that at least one ECC-based standards, a random number generator based on elliptic curve mathematics, has proven upon examination to have been compromised: http://www.wired.com/2013/09/nsa-backdoor/ Early this month the New York Times drew a connection between their talk and memos leaked by Edward Snowden, classified Top Secret, that apparently confirms that the weakness in the standard and so-called Dual_EC_DRBG algorithm was indeed a backdoor. The Times story implies that the backdoor was intentionally put there by the NSA as part of a $250-million, decade-long covert operation by the agency to weaken and undermine the integrity of a number of encryption systems used by millions of people around the world. The Times story has kindled a firestorm over the integrity of the byzantine process that produces security standards. The National Institute of Standards and Technology, which approved Dual_EC_DRBG and the standard, is now facing a crisis of confidence [...] Yeah, thank you _so_ much, Never Say Anything people. Now, I have to worry that I can't trust anything from NIST. Bastards. IETF and CFRG drew the same conclusions last year, and started moving towards non-NIST elliptic curves for Internet standards: https://tools.ietf.org/html/draft-irtf-cfrg-curves-02 I also note this curio from half a year ago: https://www.schneier.com/blog/archives/2015/10/why_is_the_nsa_.html Why Is the NSA Moving Away from Elliptic Curve Cryptography? In August, I wrote [link] about the NSA's plans to move to quantum-resistant algorithms for its own cryptographic needs. Cryptographers Neal Koblitz and Alfred Menezes just published a long paper [link] speculating as to the government's real motives for doing this. They range from some new cryptanalysis of ECC to a political need after the DUAL_EC_PRNG disaster -- to the stated reason of quantum computing fears. Read the whole paper. (Feel free to skip over the math if it gets too hard, but keep going until the end.) EDITED TO ADD (11/15): A commentary and critique [link] of the paper by Matthew Green. I found the Green paper particularly interesting. Some days, seems like Charles Stross's _Halting State_ is becoming non-fiction.