HN discussion for the paper itself: https://news.ycombinator.com/item?id=34235964
It's not an HN discussion if there's no discussion there.
Breaking RSA with a quantum computer?
31–40 of 161 posts
Re: Breaking RSA with a quantum computer?
#32Earlier quoted context omitted.
Post-quantum cryptography is not necessarily secure either. One of the four finalists in a NIST competition for post-quantum cryptography [SIDH] was suddenly, out of the blue, shattered with an algorithm that could break it in hours on a laptop. Turns out it was secure against quantum computers but insecure against classical computers. If you want to be safe, you might almost consider standard cryptography on one of…
It's worth noting that BTC could be quantum-resistant if enough of the network decided they wanted it to be. Unfortunately the BTC community is famously resistant to change so it wouldn't happen until it's too late, but in a rational world the problem could be fixed.
Tangentially to secant, BTC community resistance is in the spirit of maintaining a solid base layer that is not perpetually in startup mode given stakeholder motives. Use other coins for that purpose.
Regarding changes that still maintain or even enhance this goal of long-lived store of value, I bet they'd be fine with that, even if the work effort of BTC transactions increased.
Re: Breaking RSA with a quantum computer?
#33You divide the number of physical qubits by 5 to get the number of fault tolerant error corrected qubits. [0]
If their algorithm works, they need a 1860 (372*5) qubit computer to break 2048 bit RSA.
IBM expects to get there by 2025. [1]
[0] https://en.wikipedia.org/wiki/Five-qubit_error_correcting_co...
Re: Breaking RSA with a quantum computer?
#34[deleted]
Re: Breaking RSA with a quantum computer?
#35Even if this particular scheme doesn't work at scale, the writing is on the wall for conventional crypto. If you are encrypting data that will be at rest for more many years it's time to start think about migrating to post-quantum crypto so you don't end up one day discovering you're entire corpus is vulnerable.
No practical quantum supremacy or anything like it has been demonstrated has it? Is it sort of expected that will co-occur with QC breaking encryption? I'm just trying to gauge how "almost here" this actually is, or if it's still talk
Re: Breaking RSA with a quantum computer?
#36Even if this particular scheme doesn't work at scale, the writing is on the wall for conventional crypto. If you are encrypting data that will be at rest for more many years it's time to start think about migrating to post-quantum crypto so you don't end up one day discovering you're entire corpus is vulnerable.
Post-quantum cryptography is not necessarily secure either. One of the four finalists in a NIST competition for post-quantum cryptography [SIDH] was suddenly, out of the blue, shattered with an algorithm that could break it in hours on a laptop. Turns out it was secure against quantum computers but insecure against classical computers. If you want to be safe, you might almost consider standard cryptography on one of…
There are open questions about whether any PQ algorithm is truly quantum-safe, given the limits of our knowledge about QC.
But it's also just the case that any "new" (for values of "new" that include "old but never deployed at a scale sufficient to attract scrutiny") encryption primitive, PQ or not, stands a decent change of being breakable by a laptop, at least in its initial implementation parameters. That's what happened with the supersingular isogenies you're referring to. That's just to say: there's nothing special about the "PQ-ness" of these protocols that makes them risky; all cryptography is risky. It took a surprisingly long time --- well into the 2000s --- to figure out how to safely deploy RSA.
Virtually every serious PQ implementation proposal pairs the PQ key exchange with a "conventional" key exchange, for this reason.
If you believe that QC is going to break "conventional" cryptography, Bitcoin is toast; I don't think there aren't a lot of extra "ifs" to that. Smarter people than me think there might be a window of time where RSA falls and ECC survives; maybe you could hope that Bitcoin would react quickly enough inside that window.
Re: Breaking RSA with a quantum computer?
#37You divide the number of physical qubits by 5 to get the number of fault tolerant error corrected qubits. [0] If their algorithm works, they need a 1860 (372*5) qubit computer to break 2048 bit RSA. IBM expects to get there by 2025. [1] [0] https://en.wikipedia.org/wiki/Five-qubit_error_correcting_co... [1] https://www.ibm.com/quantum/roadmap
What practical things can be done once RSA is broken?
Re: Breaking RSA with a quantum computer?
#38You divide the number of physical qubits by 5 to get the number of fault tolerant error corrected qubits. [0] If their algorithm works, they need a 1860 (372*5) qubit computer to break 2048 bit RSA. IBM expects to get there by 2025. [1] [0] https://en.wikipedia.org/wiki/Five-qubit_error_correcting_co... [1] https://www.ibm.com/quantum/roadmap
What practical things can be done once RSA is broken?
Breaking RSA is a practical thing.
E.g. forge email (most dkim keys are 1024 bit rsa). Break ssh (depends on key algo chose). Break pgp (depending on settings). Mitm https connections, Etc.
Re: Breaking RSA with a quantum computer?
#39Earlier quoted context omitted.
All that would need to happen for this exact scenario to occur would be for anyone, anywhere to find a case where P == NP. [1] P !== NP is a theory that has never been proven, so it very well could happen in reality. This is one of those things that keeps me awake, like Carrington events [2]. [1] https://en.wikipedia.org/wiki/P_versus_NP_problem [2] https://en.wikipedia.org/wiki/Carrington_Event
As someone who is only vaguely familiar with the P = NP problem, can someone explain to me if proving P=NP automatically solves the numerous problems that can then be “quickly computed” or does it simply prove there is an existence of an algorithm for each problem? To rephrase if this is not the case - what value does solving P = NP provide?
It's only required to prove an algorithm that solves an NP-complete problem exists, not find it.
Even if that algorithm exists and was found, it could be that such an algorithm is O(n^123456789), which would not break RSA in any practical sense, though it would be mathematically asymptotically faster than O(2^n).
Re: Breaking RSA with a quantum computer?
#40Even if this particular scheme doesn't work at scale, the writing is on the wall for conventional crypto. If you are encrypting data that will be at rest for more many years it's time to start think about migrating to post-quantum crypto so you don't end up one day discovering you're entire corpus is vulnerable.
No practical quantum supremacy or anything like it has been demonstrated has it? Is it sort of expected that will co-occur with QC breaking encryption? I'm just trying to gauge how "almost here" this actually is, or if it's still talk
Quantum supremacy is a much much much lower bar than breaking rsa (at normal key strength)