Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

ECC is a minefield of patents, making it basically impossible to deploy; pushing for ECC does little to advance cryptography in practice. ECC also does not address concerns about quantum computers. In terms of mathematics, ECC is based on a problem that is in the intersection of NP and coNP, the same complexity class as the RSA assumption; there are more modern constructions based on NP-hard lattice problems.

Really, if you want to point to the NSA/NIST helping to advance the state of cryptography, point to the AES contest.



That was true 10 years ago. It is not at all true today. Meanwhile, RSA and simple prime-field DL crypto are the subject of serious progress, while whole avenues of attacks seem to be precluded for the ECDL problem.

Here's one summary of the ECC patent situation:

http://cr.yp.to/ecdh/patents.html

ECC is increasingly common in commercial systems. Who's asserting patents against those systems?


"Meanwhile, RSA and simple prime-field DL crypto are the subject of serious progress, while whole avenues of attacks seem to be precluded for the ECDL problem."

When last I checked, the 20-year-old GNFS algorithm was the most efficient way to attack RSA. Yes, this is faster than the best known attacks on ECDLP, but ECDLP attacks are still subexponential. Nothing has changed in the past ten years about the complexity class of ECDLP (it is still both in NP and in coNP).

Really, the future of cryptography is not elliptic curves, it is systems based on lattices, hidden linear codes, and hard learning problems (these are all related). You can do some interesting things with ECC, but there are far more interesting lattice cryptosystems being developed by researchers.

"ECC is increasingly common in commercial systems. Who's asserting patents against those systems?"

Certicom filed this famous lawsuit:

http://www.certicom.com/index.php/2007-press-releases/20-cer...

Really though, Dan Bernstein is not a lawyer, and I would not trust his analysis if I had a business to run. Even if he is right, that does not change the fact that ECC deployment is lagging because of fears about patent suits. The NSA's response to concerns about patents was to get a special license, specifically for government uses of ECC; they did nothing at all to encourage ECC deployment elsewhere, and they did not demonstrate that such deployment was a priority.


Good background on DL v. factoring v. ECDL is Odlyzko, http://www.dtc.umn.edu/~odlyzko/doc/discrete.logs.future.pdf.

Good background on PQ cryptography (McEliece, &c, the stuff you're referring to later in your comment): Bernstein's intro to Post-Quantum Crypto: http://pqcrypto.org/www.springer.com/cda/content/document/cd...

I've never seen anyone use McEliece, NTRU, &c commercially. Unlike ECC, these schemes aren't on the horizon for TLS.

ECC goes back to Lenstra and Koblitz in the mid-80's. I'm not wading into the validity of the patents the way DJB does, just saying, we're coming to the end of their lifespan.


You know darn well your question points to a strawman. It's pretty standard patent theory anymore to wait a little while, until there is lots of infringement, then to get a patent troll involved.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: