5 ms·
The Factoring Cryptopocalypse
- Mithrandir 13y agoPrevious discussions on the presentation: https://news.ycombinator.com/item?id=6191171 https://news.ycombinator.com/item?id=6191171 https://news.ycombinator.com/item?id=6155502 https://news.ycombinator.com/item?id=6155502
- cperciva 13y agoThanks, I missed the first discussion and was inspired to write only by the second discussion.
- iuguy 13y agoI think Colin's bang on here. Now is the time for cryptographers and software developers to act to implement a mature alternative to RSA, but it's not the point for your average joe to switch to an as yet relatively untested/unproven ECC implementation. For what it's worth, Tom Ritter recently posted his notes on de-anonymizing alt.anonymous.messages[1], something widely believed to be very anonymous and very secure. It's an interesting read and shows why you not only need the crypto to be sound, but the implementation and your own use of it to be right too. [1] - http://ritter.vg/blog-deanonymizing_amm.html http://ritter.vg/blog-deanonymizing_amm.html
- maaku 13y agoHow is EC “relatively untested/unproven”? It's been in OpenSSL for ages (by internet norms), is the subject of numerous national standards. It secures a billion dollar bitcoin economy.
- redthrowaway 13y agoHe said it's not time for the average programmer to switch to a new and untested ECC implementation, not that ECC itself is new and untested. By the standards of any of the common RSA libraries out there, their ECC counterparts would be relatively untested given how much comparative use each has seen.
- kazagistar 13y agoFor someone who is somewhat unfamiliar with cryptography, what is the obstacle in creating cryptography that is provably secure: in other words, cryptography that can be absolutely trusted within certain provided parameters.
- nhaehnle 13y agoHeuristically speaking, this problem is at least as hard as the P != NP question, which is one of the millenium problems for which the Clay institute has awarded one million dollars to whoever resolves it. From a theory point of view, breaking a crypto-system typically means something like being able to do the following fast (i.e., in polynomial time): Given two plaintexts and a ciphertext which is the encryption of one of those two plaintexts, decide which of the plaintexts it is. Of course you could flip a coin, so the essential condition is that your success probability must be larger than 1/2. So to show that a crypto-system is secure, you have to show that the problem of breaking it cannot be solved in polynomial time. We simply do not know how to show that any useful problem cannot be solved in polynomial time (we do know that P != EXPTIME, but we don't know any problems in EXPTIME that would be useful for cryptography). Hence the lack of provable security.
- YZF 13y agoI think the complexity class of discrete log or integer factorization are not known. No one has proved there isn't a polynomial time algorithm but if one is found it does not mean P = NP.
- nhaehnle 13y agoThis is true. However, this actually means that the type of proof that kazagistar asked for is harder than a proof that P != NP. After all, if you prove that factorization cannot be done in polynomial time, then a corollary of this result is that P != NP. Intuitively, NP-hard problems are believed to be harder than factorization and discrete log. And so it should be easier to prove that an NP-hard problem is not in P. What you are referring to is the opposite direction of the implication, which is very relevant in a discussion of why people have failed to find faster algorithms for integer factorization. However, the question I replied to is essentially why people have failed to prove that integer factorization (and discrete log) are hard problems. Edit: After re-reading my previous comment, perhaps this clarifies it best: Integer factorization and discrete log are probably less hard than NP-hard problems. However, the meta-problem "prove that integer factorization or discrete log is really, unconditionally hard" is at least as difficult as the meta-problem "prove P != NP".
- tptacek 13y agoOut of curiosity: If you were to design Tarsnap from scratch in 2013, would you still use RSA?
- cperciva 13y agoI think so.
- deleted 13y ago[deleted]
- hnha 13y agoECC means "Elliptic curve cryptography" here, it is not about something with "ECC memory". I've been so confused with all the discussion so far because of this. Dear masters of your domain, if there are acronyms that are not unique, please try not to use them or at least introduce them!
- moocowduckquack 13y agoAlternatively, when trying to follow a conversation in a domain specific context, learn the terms.