Breaking 256-Bit Elliptic Curve Encryption with a Quantum Computer
schneier.com
schneier.com
https://sam-jaques.appspot.com/quantum_landscape
https://www.bsi.bund.de/EN/Topics/Cryptography/QuantumComput...
The current record in factoring with Shor's algorithm is 21. Yes. 3*7. That record has stood for 12 years and arguably is not even running Shor's because it required a priori knowledge of the factors.
Even with "cheating" by using knowledge of the factors, in 20 years we have seen seen a single bit of improvement.
None of the new quantum computers from IonQ, Google, or QuEra with 32-256 qubits are even able to even replicate those early results. D-Wave claims 5000 qubits, but that is for adiabatic QC, which to my knowledge, cannot run Shor's algorithm.
To be a threat, QCs need millions of qubits and orders of magnitude better error correction. I think people make the mistake of looking at the speed of progress of classical computers and thinking it applies to QC. It's just not happening.
For QC to hit natural exponential growth, it would need to be economically feasible compared to the next best thing - classical computers. Is there anything even a tiny QC can do better, faster, and cheaper than a classical computer?
>Is there anything even a tiny QC can do better, faster, and cheaper than a classical computer?
This is a really good question, and I don't know the answer. If I were to try, I'd focus on QC efficient algorithms, and what you can do with that in an application. So, in your system a QC is a magic box that takes an O(n^2) algo and makes it O(n), say. But for ordinary humans, n is very small, so this won't matter. I don't think there is mundane problem, e.g. one dealing with ordinary productivity, that a QC can do better than classical. It's shaping up to be a nation-state funded capital intensive information superweapon against private communication. And you know what? Maybe if you can maintain the infrastructure and staff to build one, you deserve to have it! It's especially untroubling if it's capacity is limited, like being able to read 10 2048-bit RSA encrypted messages per day. That's a superpower, but a very limited and expensive one, which I am fine with.
Large-scale electronic computers were first developed for exactly the same purpose, during WWII. The first commercial computers weren't available until a few years after the war, about five years after Colossus.
For quantum computing, state is written into the wave function of an isolated particle, which is entangled with other isolated particles such that you can perform a read and get something useful out of it. (TBH I'm a little confused about how QC works at the physical level, because it seems like your program could require different patterns of entanglement, but AFAIK the pattern of qubit entanglement is determined by the hardware setup, and cannot be modified at runtime. Maybe there is a generally reusable "shape" that can be interacted with, cleared, setup for a new computation, etc by poking at the particles in some specific order. It's probably a really nice problem for physics folks who feared they'd never get to use their QM classes.)
That's an area of active research in computational complexity theory. It's not known if the class BQP[1] (bounded-error quantum polynomial time) is equal to P (classical polynomial time). Many people suspect that BQP > P, but it may not be and quantum computers might not have any problems where they're faster than classical computers.
I wonder if future QC design tools will require a QC to run effectively. Then we could get a similar feedback loop.
https://www.penguinrandomhouse.com/books/44425/turings-cathe...
https://www.forbes.com/sites/arthurherman/2021/06/07/q-day-i...
https://www.hpcwire.com/2021/10/21/d-wave-embraces-gate-base...
And those computers that do exist - they're just glorified analog machines which were known long time ago.
That is to say, it's an algorithmic overhang, the knowledge how is available but held back by not knowing how to achieve the hardware needed.
The risk being that someone could discover "how to make qubits" tomorrow, and although (because it's hardware) it might take a short while to turn that into an industrial qubit pipeline, we don't yet actually know yet that it's mechanically impossible to do.
If post-quantum cryptography algorithms are already there, I can see EC being abondoned soon
It's 13 million qubits. It's weird they write it in scientific notation, it makes it look larger. If qubits got to the moore-like-bandwagon, that is not many multiplications away from current amount.
However, millions of BTC are vulnerable with no quantum computation time limits. This includes about 1.75 M BTC in P2PK/raw multisig outputs, and over 4M BTC due to known pubkeys and scripts, revealed in the Bitcoin blockchain.
Main issue is that in cryptography (1) some secrets encrypted now will be secret in a decade (2) changing standard is very hard and takes a long time
[1] https://www.metaculus.com/questions/8169/256-bit-ecc-to-be-b...
Not as a UFO or conspiracy theory, but as a realization that there are some technologies intentionally kept secret to maintain military, political, or economic advantages.
When that distance between in-the-pipeline reaches a magnitude delta of 2, then I'd be concerned about what's already being designed or kept in secret.
Scaling QC is a difficult, unsolved problem of manufacturing.
They speculated about one way to break it. There could be several ways of using QC to break EC.
What is the chance that at least one of those other ways require, say only 1,000 qubits?
Oops, it's a two year time frame now. It might be a small chance, but I don't think we can discard it. Better plan for the worse.
A thousand physical qubits with current error rates? Pretty much impossible would be my guess.
By combining such a probability distribution with an estimate of how much damage could be done (or how much profit could be generated) by an enemy breaking elliptic curve encryption, it would then be possible to give a reasoned guess for how much to spend on bringing forward quantum-resistant cryptography.
The NSA has an interest in making sure that classified information stays that way for as long as the classification lasts. That is at least 25 years, potentially up to 75 years (src: https://en.wikipedia.org/wiki/Classified_information_in_the_...) so one could infer that the NSA believes there is a reasonable chance quantum computers will exist and be able to break classical encryption within that timeframe.
Thanks.