So despite this significant progress, it's probably a still a while until RSA is put out of the job. That being said, quantum computers would be able to retroactively break any public keys that were stored, so there's a case to be made for switching to quantum-resistant cryptography (like lattice-based cryptography) sooner rather than later.
I'm very sorry to admit it but I'm too lazy to read the entire discussion in this thread. Could you please tell me, a mere mortal, at which point the humanity should start worrying about the security of asymmetric encryption in the brave new world of quantum computing?
Which to be clear is quite a bit faster than expected in 2020, but still within the realm of plausible stuff.
The authors argue (e.g. in the first comment here https://scottaaronson.blog/?p=8310#comments) that by their definition, Google still only has a fraction of one logical qubit. Their logical error rate is of order 1e-3, whereas this paper considers a logical qubit to have error of order 1e-18. Google's breakthrough here is to show that the logical error rate can be reduced exponentially as they make the system larger, but there is still a lot of scaling work to do to reach 1e-18.
So according to this paper, we are still on roughly the same track that they laid out, and therefore might expect to break RSA between 2040 and 2060. Note that there are likely a lot of interesting things one can do before breaking RSA, which is among the hardest quantum algorithms to run.
The error correcting code used in this work also has a nice intuitive explanation. Imagine a 2D grid of bits, visualized as pixels that can be black or white. Now imagine drawing a bunch of lines of black pixels, and enforcing that lines can only end on the top or bottom boundary (loops are allowed). If there is an even number of lines connecting the top to the bottom, we call that logical 0, and if there is an odd number of lines, we call that logical 1. This again has the property that as you add more bits, the probability of changing between logical 1 and 0 gets exponentially smaller, because the lines connecting top to bottom get longer (just like in the repetiton code).
This code also has the nice property that if you measure the value of a small patch of (qu)bits, there's no way to tell what the logical state is. This is important for quantum error correction, because measurement destroys quantum information. So the fact that local measurements don't reveal the logical state means that the logical state is protected. This isn't true for the repetition code, where measuring a single bit tells you the logical state.
Use a key exchange that offers perfect forward secrecy (e.g. diffie Hellman) and you don’t need to worry about your RSA private key eventually being discovered.
Unless they break ECDHE, it doesn’t matter if RSA gets popped.
https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exc...
The point is that you can build stuff on top of RSA today even if you expect it to be broken eventually if RSA is only for identity verification.
[1] https://security.stackexchange.com/questions/33069/why-is-ec...
There are several choices with scaling RSA too, you can push the primes which slows generation time considerably. Or the more reasonable approach is to settle on a prime size but use multiple of them (MP-RSA). The second approach scales indefinitely. Though it would only serve a purpose if you are determined to hedge against the accepted PQC algorithms (Kyber/MLKEM, McEliece) being broken at some point.
The Intel 4004, in 1971, had only 2,250 transistors.
A handful of qubits today might become a billion sooner than you think.
All perfect forward secrecy means is that you delete your own ephemeral private keys, the public keys stay in the record. And a quantum computer will recover the deleted private keys.
Also, none of the currently accepted post-quantum cryptographic algorithms offer a Diffie-Hellman construction. They use KEM (Key Encapsulation Mechanism).
This.
People seems to think that because something is end to end encrypted it is secure. They don't seem to grasp that the traffic and communication that is possibly dumped/recorded now in encrypted form could be used against them decades later.
https://crypto.stackexchange.com/a/61596
But ... AES is believed to be quantum-safe-ish, so with perfect forwards secrecy this exact threat can be quite well managed.
The currently best known quantum attack on AES requires a serial computation of "half of key length" (Grover's algorithm ... so if they key is 128 bit long then it requires 2^64 sequential steps)
https://www.reddit.com/r/AskNetsec/comments/15i0nzp/aes256_i...
https://cloud.google.com/blog/products/identity-security/why...
Ah, okay for iMessage, something called PQ3[1], hm, it uses Kyber. And it's also a hybrid scheme, combining ECC. And a lot of peer review.
And there's also some formal verification for Signal's PQXDH [2].
Oh, wow, not bad. Thanks!
Now let's hope a good reliable sane implementation emerges so others can also try this scheme. (And I'm very curious of the added complexity/maintenance burden and computational costs. Though I guess this mostly runs on the end users' devices, right?)
[1] https://security.apple.com/blog/imessage-pq3/ [2] https://github.com/Inria-Prosecco/pqxdh-analysis
ETA: Wikipedia 2330 qubits, but I'm not sure it is citing the most recent work: https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#ci...
The Shor's algorithm requires binary encoding; hence, 2048 logical qubits are needed to become a nuance for cryptography. This, in turn, means that one will always be easily able to run away from a quantum adversary by paying a polynomial price on group element computations, whereas a classical adversary is exponentially bounded in computation time, and a quantum adversary is exponentially bounded with a number of physical qubits. Fascinating...
The Let's Encrypt intermediate certificates R10 and R11 seem to be only 2048 bit.
So don't fear them due to unfounded theories.
The problem it's presenting is more about software on the wild having different behavior... And if "some people connect on the internet and use software that behaves differently from mine" is a showstopper for you, I have some really bad news.
In my opinion the correct approach here is the most liberal one for the Q, R points. One checks each point cofactor at parsing 8P=0 and then use unbatched equation for verification. This way implementations can be made group agnostic.
Having group agnostic implementations is important as it creates a proper separation of concerns between curve implementations and the code that uses them. For instance if we were to accept strict validation as the ground truth and best practice one would have enormously hard time specifying verifiers for zero knowledge proofs and would also double time and code for the implementers without any effect on soundness.
https://crypto.stackexchange.com/questions/1978/how-big-an-r...
To see how it plays out consider adding a single logical qubit. First you need to increase the number of physical qubits to accommodate the new logical qubit at the same error rate. Then multiply the number of physical qubits to accommodate for exponentially decreased error rate which would be a constant factor N ( or polynomial but let’s keep things simple) by which the number of physical qubits need to be multiplied to produce a system with one additional logical qubit with an error rate to produce meaningful results.
To attain 1024 logical qubits for Schor algorithm one would need N^1024 physical qubits. The case where N<1 would be possible if error would decrease by itself without additional error correction.
The result shall be interpreted directly with the error rate for logical qubits to decrease as ~n^(-1/3). This, in turn, means that factorisation of a 10000-bit number would only require an error rate of 1/10th of the number of the logical qubits for a 10-bit number. This is practical given that one can make a quantum computer with around 100k qubits and correct errors on them.
On the other hand, a sibling comment already mentioned the limited connectivity that those quantum computers now have. This, in turn, requires a repeated application of SWAP gates to get the interaction one needs. I guess this would add a linear overhead for the noise; hence, the scaling of the error rate for logic qubits is around ~n^(-4/3). This, in turn, makes 10000-bit factorisation require a logical error rate of 1/10000 that of 10-bit number factorisation. Assuming that 10 physical qubits are used to reduce error by order, it can result in around 400k physical qubits.
[1]: https://link.springer.com/article/10.1007/s11432-023-3961-3
> Worth spending a little time doing some long tail strategizing I’d say
any tips for starters?
https://quantum.microsoft.com/en-us/tools/quantum-katas
The first few lessons do cover complex numbers and linear algebra, so skip ahead if you want to get straight to the 'quantum' coding, but there's really no escaping the math if you really want to learn quantum.
Disclaimer: I work in the Azure Quantum team on our Quantum Development Kit (https://github.com/microsoft/qsharp) - including Q#, the Katas, and our VS Code extension. Happy to answer any other questions on it.
there's no such thing as a practical QC and there won't be for decades. this isn't a couple of years away - this is "maybe, possibly, pretty please, if we get lucky" 25-50 years away. find the above comment that alludes to "2019 estimates needing ~20 million physical qubits" and consider that this thing has 105 physical qubits. then skim the posted article and find this number
> the key quantum computational resource — are now approaching 100 µs (microseconds)
that's how long those 105 physical qubits stay coherent for. now ponder your career pivot.
source: i dabbled during my PhD - took a couple of classes from Fred Chong, wrote a paper - it's all hype.
You don't need to know quantum theory necessarily, but you will need to know some maths. Specifically linear algebra.
There are a few youtube courses on linear algebra
For a casual set of video: - https://youtube.com/playlist?list=PLZHQObOWTQDPD3MizzM2xVFit...
For a more formal approach:
- https://youtube.com/playlist?list=PL49CF3715CB9EF31D
And the corresponding open courseware
- https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010...
Linear algebra done right comes highly recommended
1. Kaye, LaFlamme, and Mosca - An Introduction to Quantum Computing
2. Nielsen and Chuang - Quantum Computation and Quantum Information (The Standard reference source)
3. Andrew Childs's notes here [1]. Closest to the state-of-the-art, at least circa ~3 years ago.
I would not worry about hardware at first. But if you are interested and like physics, the simplest to understand are linear optical quantum circuits. These use components which may be familiar from high school or undergraduate physics. The catch is that the space (and component count) is exponential in the number of qubits, hence the need for more exotic designs.
From my __very__ shallow understanding, because all of the efficiency increases are in very specific areas, it might not be useful for the average computer science interested individual?
[1] - https://kvathupo.github.io/cs/quantum/457_Final_Report.pdf
the model of quantum mechanics, if you can afford to ignore any real-world physical system and just deal with abstract |0>, |1> qubits, is relatively easy. (this is really funny given how incredibly difficult actual quantum physics can be.)
you have to learn basic linear algebra with complex numbers (can safely ignore anything really gnarly).
then you learn how to express Boolean circuits in terms of different matrix multiplications, to capture classical computation in this model. This should be pretty easy if you have a software engineer's grasp of Boolean logic.
Then you can learn basic ideas about entanglement, and a few of the weird quantum tricks that make algorithms like Shor and Grover search work. Shor's algorithm may be a little mathematically tough.
realistically you probably will never need to know how to program a quantum computer even if they become practical and successful. applications are powerful but very limited.
"What You Shouldn't Know About Quantum Computers" is a good non-mathematical read.
I prefer his explanation to most other explanations because he starts, right away, with an analogy to ordinary probabilities. It's easy to understand how linear algebra is related to probability (a random combination of two outcomes is described by linearly combining them), so the fact that we represent random states by vectors is not surprising at all. His explanation of the Dirac bra-ket notation is also extremely well executed. My only quibble is that he doesn't introduce density matrices (which in my mind are the correct way to understand quantum states) until halfway through the notes.
But the key thing to know about quantum computing is that it is all about the mathematical properties of quantum physics, such as the way complex probabilities work.
Short enough that its reasonable to start r&d efforts on post quantum crypto.
One thing that might be problematic for a blockchain where everything has to go on the blockchain forever is that some post quantum schemes have really large signatures or key sizes.
I'm not that familiar with the details of bitcoin, but i had the impression that p2pkh is more secure against quantum computers.
[I should emphasize, im not a cryptographer and only somewhat familiar with bitcoin]
https://www.deloitte.com/nl/en/services/risk-advisory/perspe...
There are, however, analog quantum computers, e.g. by Pasqal, which hope to capitalize on this to optimize AI-like high dimension optimization problems.
At least as far as I'm aware by digital they probably mean a generally programmable QC, whereas another approach is to encode a specific class of problems in the physical structure of an analog QC so that it solves those problems much faster than classical. This latter approach is less general (so for instance you won't use it to factor primes) but much more attainable. I think D-wave or someone like that already had commercial application for optimization problems (either traveling salesman or something to do with port organization)
E.g. winning at Chess or Go (traditional AI domains) is searching through the space of possible game states to find a most-likely-to-win path.
E.g. an LLM chat application is searching through possible responses to find one which best correlates with expected answer to the prompt.
With Grover's algorithm, quantum computers let you find an answer in any disordered search space with O(sqrt(N)) operations instead of O(N). That's potentially applicable to many AI domains.
But if you're so narrow minded as to only consider connectionist / neural network algorithms as "AI", then you may be interested to know that quantum linear algebra is a thing too: https://en.wikipedia.org/wiki/HHL_algorithm
There are about 2^152 possible legal chess states. You cannot build a classical computer large enough to compute that many states. Cryptography is generally considered secure when it involves a search space of only 2^100 states.
But you could build a computer to search though sqrt(2^152) = 2^76 states. I mean it'd be big--that's on the order of total global storage capacity. But not "bigger than the universe" big.
Cryptographers worry about big numbers. 2^80 is not considered secure.
We're talking about something that can search a list of size N in sqrt(N) iterations. Splitting the problem in two doesn't halve the compute required for each half. If you had to search 100 items on one machine it's taken 10x iterations but split over two it'd take ~7x on each or ~14 in total.
This is not at all a surprising property. The same things happens with binary search: it has complexity O(log(N)), which means that running it on a list of size 1024 will take about 10 operations, but running it in parallel on two lists of size 512 will take 2 * 9 operations = 18.
This is actually easy to intuit when it comes to search problems: the element you're looking for is either in the first half of the list or in the second half, it can't be in both. So, if you are searching for it in parallel in both halves, you'll have to do extra work that just wasn't necessary (unless your algorithm is to look at every element in order, in which case it's the same).
In the case of binary search, with the very first comparison, you can already tell in which half of the list your element is: searching the other half is pointless. In the case of Grober's algorithm, the mechanism is much more complex, but the basic point is similar: Grover's algorithm has a way to just not look at certain elements of the list, so splitting the list in half creates more work overall.
Even for chess, 2^76 operations is still waaaaay more time than anyone will ever wait for a computation to finish, even if we assumed quantum computers could reach the OPS of today's best classical computers.
There is, at present, no quantum algorithm which looks like it would beat the state of the art on Chess, Go, or NP-complete problems in general.
What do you mean by this?
So the commenter is saying that Cybersecurity needs to be planning for a near-world where traditional cryptography, including lots of existing data at rest, is suddenly as insecure as plaintext.
Honestly, there's not that much to discuss on this though. The only things you can do from this strategizing is to consider even encrypted data as not safe to store, unless you're using quantum resistant encryption such as AES; and to budget time for switching to PQC as it becomes available.
Definitely agree with the latter, but do you have any sources on how quantum comphters make "AI" (i.e. matrix multiplication) faster?
That level of embarrassment is frankly difficult to face. And it would be devastating to the self-image of a bunch of “practical” security gurus.
Therefore any progress must be an illusion. In the real world, the threats are predictable and mistakes don’t slowly snowball into a crisis. See also, infrastructure.
Also, the more qubits you have/the more instructions are in your program, the faster the quantum state collapses. Exponentially so. Qubit connectivity is still ridiculously low (~3) and does not seem to be improving at all.
About AI, what algorithm(s) do you think might have an edge over classical supercomputers in the next 30 years? I'm really curious, because to me it's all (quantum) snake oil.
Google's willow chip has t-times of about 60-100mu.s. That's not an impressive figure -- in 2022, IBM announced their Eagle chip with t-times of around 400mu.s [2]. Google's angle here would be the error correction (EC).
The following portion from Google's announcement seems most important:
> With 105 qubits, Willow now has best-in-class performance across the two system benchmarks discussed above: quantum error correction and random circuit sampling. Such algorithmic benchmarks are the best way to measure overall chip performance. Other more specific performance metrics are also important; for example, our T1 times, which measure how long qubits can retain an excitation — the key quantum computational resource — are now approaching 100 µs (microseconds). This is an impressive ~5x improvement over our previous generation of chips.
Again, as they lead with, their focus here is on error correction. I'm not sure how their results compare to competitors, but it sounds like they consider that to be the biggest win of the project. The RCS metric is interesting, but RCS has no (known) practical applications (though it is a common benchmark). Their T-times are an improvement over older Google chips, but not industry-leading.
I'm curious if EC can mitigate the sub-par decoherence times.
[0]: https://www.science.org/doi/abs/10.1126/science.270.5242.163...
[1]: https://dl.acm.org/doi/abs/10.5555/3511065.3511068
[2]: https://www.ibm.com/quantum/blog/eagle-quantum-processor-per...
The main EC paper referenced in this blog post showed that the logical qubit lifetime using a distance-7 code (all 105 qubits) was double the lifetime of the physical qubits of the same machine.
I'm not sure how lifetime relates to decoherence time, but if that helps please let me know.
If the logical qubit can have double the lifetime of any physical qubit, that's massive. Recall IBM's chips, with t-times of ~400microseconds. Doubling that would change the order of magnitude.
It still won't be enough to do much in the near term - like other commenters say, this seems to be a proof of concept - but the concept is very promising.
The first company to get there and make their systems easy to use could see a similar run up in value to NVIDIA after ChatGPT3. IBM seems to be the strongest in the space overall, for now.
Reminds me of the time my research director pulled me aside for defining CPU as "core processing unit" instead of "central processing unit" in a paper!
Imagine a device conceived in the 17th century, the intended functionality of which would require a physical sphere which matches a perfect, ideal, geometric sphere in Euclidean space to thousands of digits of precision. We now know that the concept of such a perfect physical sphere is incoherent with modern physics in a variety of ways (e.g., atomic basis of matter, background gravitational waves.) I strongly suspect that the cancellations required for the Fourier Transform in Shor's algorithm to be cryptographically relevant will turn out to be the moral equivalent of that perfect sphere.
We'll probably learn some new physics in the process of trying to build a Quantum Computer, but I highly doubt that we'll learn each others' secrets.
Was this actually measured and published somewhere?
Yeah, this is pretty huge. They achieved the result with surface codes, which are general ECCs. The repetition code was used to further probe quantum ECC floor. "Just POC" likely doesn't do it justice.
(Original comment):
Also quantum dabbler (coincidentally dabbled in bitflip quantum error correction research). Skimmed the post/research blog. I believe the key point is the scaling of error correction via repetition codes, would love someone else's viewpoint.
Slightly concerning quote[2]:
"""
By running experiments with repetition codes and ignoring other error types, we achieve lower encoded error rates while employing many of the same error correction principles as the surface code. The repetition code acts as an advance scout for checking whether error correction will work all the way down to the near-perfect encoded error rates we’ll ultimately need.
"""
I'm getting the feeling that this is more about proof-of-concept, rather than near-practicality, but this is certainly one fantastic POC if true.
[1]: https://arxiv.org/abs/2408.13687
[2]: https://research.google/blog/making-quantum-error-correction...
Relevant quote from preprint (end of section 1, sorry for copy-paste artifacts):
"""
In this work, we realize surface codes operating below threshold on two superconducting processors. Using a 72-qubit processor, we implement a distance-5 surface code operating with an integrated real-time decoder. In addition, using a 105-qubit processor with similar performance, we realize a distance-7 surface code. These processors demonstrate Λ > 2 up to distance-5 and distance7, respectively. Our distance-5 quantum memories are beyond break-even, with distance-7 preserving quantum information for more than twice as long as its best constituent physical qubit. To identify possible logical error f loors, we also implement high-distance repetition codes on the 72-qubit processor, with error rates that are dominated by correlated error events occurring once an hour. These errors, whose origins are not yet understood, set a current error floor of 10−10. Finally, we show that we can maintain below-threshold operation on the 72qubit processor even when decoding in real time, meeting the strict timing requirements imposed by the processor’s fast 1.1µs cycle duration.
"""
However the main scaling of error correction is via surface codes, not repetition codes. It's an important point as surface codes correct all Pauli errors, not just either bit-flips or phase-flips.
They use repetition codes as a diagnostic method in this paper more than anything, it is not the main result.
In particular, I interpret the quote you used as: "We want to scale surface codes even more, and if we were able to do the same scaling with surface codes as we are able to do with repetition codes, then this is the behaviour we would expect."
Edit: Welp, saw your edit, you came to the same conclusion yourself in the time it took me to write my comment.
Goodbye not just to Bitcoin, but also Visa, Stripe, Amazon shopping, ...
symmetric ciphers would have similar properties (AES, CHACHA20). Asymmetric encryption atm would use ECDH (which breaks) to generate a key for use with symmetric ciphers - Kyber provides a PQC KEM for this.
So, the situation isn't as bad. We're well positioned in cryptography to handle a PQC world.
https://en.wikipedia.org/wiki/Post-quantum_cryptography
https://www.microsoft.com/en-us/research/project/post-quantu...
https://www.forbes.com/councils/forbestechcouncil/2024/10/09...
https://blog.cloudflare.com/kemtls-post-quantum-tls-without-...
Signatures still have to be upgraded, but that's more difficult. We're working on it. http://blog.cloudflare.com/pq-2024/#migrating-the-internet-t...
Yup, like Bitcoin going to zero.
As to faking signatures and, e.g. stealing Satoshi's coins or just fucking up the network with fake transactions that verify, there is some concern and there are some attack vectors that work well if you have a large, fast quantum computer and want to ninja in. Essentially you need something that can crack a 256 bit ECDSA key before a block that includes a recently released public key can be inverted. That's definitely out of the reach of anyone right now, much less persistent threat actors, much less hacker hobbyists.
But it won't always be. The current state of the art plan would be to transition to a quantum-resistant UTXO format, and I would imagine, knowing how Bitcoin has managed itself so far, that will be a well-considered, very safe, multi-year process, and it will happen with plenty of time.
EDIT: it's like rainbow hashes, but every possible variation is a color, not granular like binary, but all and any are included.
If the encryption on Bitcoin is broken, say goodbye to the banking system.
You mean digital signatures - and yes, we use signatures everywhere in public key cryptography.
More likely that other critical infrastructure failures will happen within trad-finance, much larger vulnerability footprint, and being able to trivially reverse engineer every logged SSL session is likely to be a much more impactful turn of events. I’d venture that there are significant ear-on-the-wire efforts going on right now in anticipation of a reasonable bulk SSL de cloaking solution. Right now we think it doesn’t matter who can see our “secure” traffic. I think that is going to change, retroactively, in a big way.
Is that a crime? Lots of forgotten keys in there.
As for the forgotten key case, I think the only way to prove you had the key at some point would need to involve the sender vouching for you and cryptographically proving they were the sender.
Legally, the situation is the same: legal ownership is not in any way tied to the mechanism of how some system or another keeps track of ownership. Your BTC is yours via a contract, not because the BTC network says so. Of course, proving to a judge that someone else stole your BTC may be extremely hard, if not impossible.
Saying "if the protocol permits anyone who can sign a valid transaction involving a given UTXO to another address, then it technically isn't a "crime"" is like saying "traditional banking is governed by a banker checking your identity, so if someone can convince the banker they are you, then it technically isn't a "crime"".
The only thing that wouldn't be considered a crime, in both cases, is the system allowing the transaction to happen. That is, it's not a crime for the bank teller to give your money to someone else if they were legitimately fooled; and it's not a crime for the Bitcoin miners to give your money to someone else if that someone else impersonated your private key. But the person who fooled the bank teller /the miners is definitely committing a crime.
A long-term tactic of our adversaries is to capture network traffic for later decryption. The secrets in the mass of packets China assumedly has in storage, waiting for quantum tech, is a treasure trove that could lead to crucial state, corporate, and financial secrets being used against us or made public.
AI being able to leverage quantum processing power is a threat we can't even fathom right now.
Our world is going to change.
So what are the implications if so ?
My memory is that 256 bit keys in non quantum resistant algos need something like 2500 qubits or so; and by that I mean generally useful programmable qubits. To show a bit over 100 qubits with stability, meaning the information survives a while, long enough to be read, and general enough to run some benchmarks on is something many people thought might never come.
There’s a sort of religious reaction people have to quantum computing: it breaks so many things that I think a lot of people just like to assume it won’t happen: too much in computing and data security will change -> let’s not worry about it.
Combined with the slow pace of physical research progress (Schorrs algorithm for quantum factoring was mid 90s), and snake oil sales companies, it’s easy to ignore.
Anyway seems like the clock might be ticking; AI and data security will be unalterably different if so. Worth spending a little time doing some long tail strategizing I’d say.