3 ms·
What is the probability that someone developed/will soon develop good enough quantum computers for breaking RSA, ECC in secrecy?
by im3w1l 14y ago
What is the probability that someone developed/will soon develop good enough quantum computers for breaking RSA, ECC in secrecy?
- cantos 14y ago[Edit: misread the question. This answer is about how close we might be to breaking these cryptosystems on classical, not quantum, computers] Publicly accessible progress on factoring and discrete log have essentially employed variations on single idea and hundreds of papers have been written on the topic. It is one of the most common Phd thesis topics in math. Yet still there has been no significant new ideas since 1994. I think that Arjen Lenstra has said that he believes there will be no further progress with this approach and new ideas are needed. However, there's not even a hint of where to begin. Likewise there has never been a single promising idea for an attack on ECC. But this lack of progress in academia may be a self fulfilling prophecy in some sense. It is not possible to get funding to just attempt to break cryptographic protocols, at least not without already having a breakthrough result. If a government decided to go all out trying to break a protocol that would create an environment more conducive to making progress.
- api 14y agoI thought ECC was vulnerable to Shor's algorithm. Of course we probably don't have QCs good enough to actually do it even for "toy" key sizes, let alone for the 256 bit or higher key sizes that are commonly used.
- cantos 14y agoYes you're right that ECC is vulnerable to Shor. I answered a different question then the one that was asked.
- jessriedel 14y agoHaving spoken with experts on the experimental (and theory) side at IBM Watson, the general answer for an over/under estimate to a quantum computer performing a useful calculation is 20 or 30 years. Most people put wide error bars on that, though, and I think the 2-sigma range is probably 5-100 years.
- archgoon 14y agoI'll interpret that as an optimistic: "Never or soon."