"If you take just one piece of information from this blog:
Quantum computers would not solve hard search problems
instantaneously by simply trying all the possible solutions at once." - Scott Aaronson
Classical searches are O(N). Grover's (quantum) algorithm can perform such searches in O(N^(1/2)) and is optimal, so what you're talking about can't be faster than that (without nonlocal variables or some nonsense like that).
The Post-Quantum Crypto Summer School lectures cover this in more detail if anybody is interested https://2017.pqcrypto.org/school/schedule.html specifically the Quantum Algorithms lectures and notes by Ronald de Wolf.
Classical computers take a polynomial amount of time (in key size) to perform RSA but exponential amount of time (in key size) to break RSA. Quantum computers can break RSA in polynomial time.
For classical systems, the cost to break RSA grows much faster than the cost to perform it, so we can always outpace more powerful adversaries with a less powerful computer. This is not true for quantum machines. I cannot produce a key size that will be small enough that I can work with it but large enough that it is secure against attack.
This is when I wish people would read the article before commenting... It goes over what quantum would be good at solving, why it's good at solving it, and what can stump it. All in just a handful of paragraphs.
Quantum computers will be good at a specific range of problems where interference can be taken advantage of. It drives me crazy how many people think they just go into a superposition and calculate all outcomes at the same time. It doesn't work that way.
And we still have to scale them with proper error correction. Who knows what the timeline for this looks like. Anyone who assumes "Moore's Law" isn't taking into consideration the fact that scaling here isn't as simple as multiplying the number of transistors in parallel.
To be useful they have to achieve entanglement between new qubits. Plus error correction and isolation have to also be scaled with that.
An unintuitive but important fact is that n qubits do not correspond to n unit vectors in two-dimensional Hilbert space (but rather to one unit vector in 2^n-dimensional Hilbert space).
I think you have the right idea but the wrong terminology. A n qubit system requires amplitudes (probabilities) for all 2^n possible basis states. For example, the representation we can give to a 2-qubit system is just a probability (technically an amplitude) associated with each of states 00, 01, 10, and 11. It's not really fancy or hard to see how this increases exponentially.
Here's an example with classical randomness (and has a close quantum analogue). If you have two closed boxes with coins in them and shake both around so that the coins flip around in the in such a way that they land 50/50 on each side, you could represent that state of the system as [1/4, 1/4, 1/4, 1/4], that is, each possible state of the system of two coins (heads head, heads tail, tail head, and tail tail), has 1/4 chance of being observed when you open the boxes.
Note that entanglement refers to the idea that two bits can be correlated. That is, the state of one is correlated with the state of another in some sense. In the example I just gave, the coins are not entangled, since the observation of one of the coins does not affect the probability of what the other coin could be. In mathematics we say this is possible if the state of the 2-coin system [1/4 1/4 1/4 1/4] can be written as a tensor product of the constituent 1-coin systems [1/2 1/2] and [1/2 1/2], which it can (entanglement refers to a state where this factorization isn't possible).
That said, we can achieve entanglement with the coins too, by somehow getting a state vector like [1/2 0 0 1/2] (50% chance that both coins are heads and 50% chance both are tails), which cannot be written as a tensor product of two 1-coin states. Moreover, if you open one box and see its a heads coin, you know the other box must also have a head coin. That's what is meant by 'correlation'. To product such a state of the coin boxes, I guess you would need a third party or something to put the two coins in the boxes and delivering them to you.
My conclusion is, entanglement doesn't have to do too much with the exponential size of representation n-qubit states, and I hope I gave a good example of what entanglement kind of really means. While (randomized) classical analogues to quantum effects are not really perfect, I think they demonstrate these effects more understandably.
Parent is correct — entanglement is exactly due to the fact that there exist more vectors in Hilbert space than tensor products (~ tuples) of unit vectors.
From a computational complexity standpoint, it's not even clear if quantum computing is actually faster. The discrete log problem and integer factoring problem aren't known to be NP-complete, so even assuming P != NP it's possible there are polynomial time algorithms for factoring and discrete log on classical computers as well. BQP vs. P is still, IIRC, unresolved.
Though, from a practical standpoint, I have a feeling that, regardless of how the computational classes shake out, the quantum Fourier transform will prove to be faster than classical techniques. And possibly Grover's algorithm, though its results are somewhat less dramatic.
There was a recent post on BBC where the academics said their quantum computer will scale through modules. So they have to get a module right, and after that it will be "easy" to scale.
The recent UNSW silicon architecture announcement included something similar to that (480 qubit chip module that scales). Plus, they said they have an error-correction algorithm that will scale to millions of qubits.
In that post Martinis actually hoped they'd double the number of qubits every year, but I think it's been closer to 1.5-2 years, for both Google and IBM. Google plans to announce the rumored 49 qubits quantum computer next March.
D-Wave was able to double the number of qubits every year in their first four years, and now it seems to double every 2 years. I think D-Wave's capabilities have only improved significantly, rather than regressed with the number of qubits. We don't know yet if that's true for Google and IBM, but I would imagine it is.
D-Wave's computer is fundamentally different than other quantum computers. The D-Wave is a quantum annealling computer. And for a while, there was some question whether what it was doing could actually be described fully classically, though now I think the consensus is that there is some quantum effect. Although classical or quantum, there could still be a practical speed up over the typical conventional computers. The idea is to use them for optimization problems. But they aren't a straightforward mapping to the usual quantum computer, and so cannot be directly compared.
To me, it's like comparing an analogue and a digital computer.
It turns out, though, that those few problems are pretty common.
FFT is O(d log d) classically, and O((log d)^2) Quantum mechanically.
Gaussian elimination (used to find eigenvectors and eigenvalues) is O(d^3) or O(s * d^2) for classical (non-sparse and sparse, respectively) versus O((log d)^2) for Quantum.
(And similar speed up for Matrix inversion.)
FFT? Matrix inversion? Gaussian elimination? Super common. And in the case of Gaussian elimination, it gets pretty hard pretty fast.
You're right that we still have to scale with proper error correction, but the fact that quantum error correction is possible is very good news for the future of quantum computing. And the best, ~50-bit quantum computers are approaching what is needed for a fully error corrected qubit, although proper connectivity needs some work.
So you're right to be wary of the current status of quantum computing, but I think you're wrong about Moore's Law, here. Qubits can be and are made with photolithographically scalable techniques today with error rates that approach what's needed for error correction, even taking into account some of the problems that integration causes for integration. And, in fact, error correction is what enables us to scale quantum computing (although there are still some calculations we can do without error correction).
I do think we're pretty close to a threshold, here, with quantum computing. We are probably under one or two years away from "quantum supremacy," if you accept having a quantum computer too sophisticated to reliably simulate classically.
We aren't 3 years away from breaking encryption using Shor's Algorithm. We're probably at least a decade away. But there ARE a bunch of uses for quantum computing that don't require as many qubits. A few hundred physical qubits is still enough to do things that wouldn't be feasible with classical computing.
I want to add that quantum FFT performs the transform on the amplitudes in the n-qubit state. Thus its output is an n-qubit state with the amplitudes matching the fourier tranforms. We cannot actually directly extract the amplitudes of the resulting state (which is the actual transformed values) from the system, since a measurement collapses the state of the system.
While some people have figured out how to used the result of the quantum FFT to do useful things (e.g. Shor's algorithm), it does not actually provide us with the transformed values in the traditional sense as the classical algorithm does.
None of them, in the conventional sense. The ECDLP itself is breakable with Shor's Algorithm more easily, in experimental simulation, than RSA.
Curves still have a role in PQ systems through isogenies, which are mappings between entire curves. But those schemes are very different than the elliptic curves we use today; you can think of them as systems that exchange whole curves rather than curve points.
Correct me if I'm wrong but The article doesn't describe how 'classical' cryptography will survive quantum computers. It merely describes how it will break RSA and then lightly covers a potential alternative quantum proof public private key cryptography scheme.
This is a good point. I found the article's content disappointing, to be honest. I think it hit a bit of an uncanny valley - it was too shallow to be comprehensive for a technical math/computer science audience, but too deep (and emphasizing the wrong things) to cover the ground in a way that would be appropriate for a non-technical audience.
If I were to write an article like this, I would probably choose a more explicit audience from the outset, then cover either a depth-first or breadth-first approach to the subject. A breadth-first approach would be good for a non-technical audience: here are the general types of cryptosystems, here are the ones threatened by quantum computers, here are the ones that are not, here are the current proposals for post-quantum resistant cryptosystems.
On the other hand, were I writing for a technical audience I would assume an understanding of why quantum computers threaten classical cryptography (and why e.g. symmetric encryption is mostly safe), then take a deeper look at each of the post-quantum proposals.
Interesting that sha256 is mentioned as approved by the government, didn't the NSA invent this encryption? Also I seem to recall another article on HN this year about the 1st sha1 collision being found? Maybe it won't take a QC to break after all. My mistake just reread, it AES256 mentioned sorry.
SHA-256 (SHA-2) is incomparable to SHA-1. The (first) successful SHA-1 collision attack executed by Google et al earlier this year implies absolutely nothing about the computational hardness of SHA-2.
There is no evidence whatsoever that quantum computers will break SHA-256; I'd be willing to personally stake essentially all of my assets on the bet that it won't be broken within our lifetimes. I also cannot think of a credible cryptographer off the top of my head who has voiced the opinion that quantum computers pose a threat to the SHA-2 family (or SHA-3, for that matter).
At best I could see a complexity reduction, but nothing in polynomial time. Cryptographic primitives have such attacks published against them (and survive them) all the time.
Ok, first off I didn't say it would be broken by a QC but that is besides the point. As a person who has been around long enough to remember when people stated our computers would never need more that 640K, I would never stake all my assets on what will come in the future, but maybe your not long for this world..happy new year.
For those who would like to get a better idea of the cryptography described in this article, here is an overview of the usually encountered computational hardness problems in lattice-based cryptography:
1. Shortest Vector Problem (SVP) - Given a lattice with a basis B, find the shortest vector in the lattice.
2. Closest Vector Problem (CVP) - Given a lattice with a basis B and some target vector t, find the point v which is closest to t.
3. Shortest Independent Vector Problem (SIVP) - Given a lattice basis B in Z^(n x n), find n linearly independent lattice vectors [s1, ..., sn], where si is in the lattice of basis B for all i.
4. Learning With Errors (LWE) - Given integral starting parameters n, m and q, with a probability distribution X on Zq, distinguish between an input pair (A, v) and a vector e in (Zq)^m. A is chosen uniformly from (Zq)^(m x n) and v is (typically) chosen uniformly from (Zq)^m.
In other words, try to recover the secret key s in (Zq)^n by examining a sequence of approximate linear equations. The error introduced is what makes this computationally hard, otherwise it could be done in polynomial time using Gaussian elimination.
5. Learning Parity With Noise (LPN) - Given a secret length l, a noise rate 0 < r < 0.5 and the number of samples q, find the random l-bit secret string s in (Z2)^l using q samples. This is the search problem version; there is also a decisional variant.
There are good surveys that cover lattice-based cryptography in general or particular computational problems in greater depth; for example, try [1], [2], or [3].
I'm a little surprised we didn't have decent quantum-resistant crypto even 20 years ago. All our public key crypto is based on the hardness of integer factoring and the discrete logarithm problem, neither of which are known to be NP-complete or NP-hard. Quantum computers can efficiently solve those two problems, but they haven't been shown to be able to handle any NP-complete problems. There have been previous attempts to make cryptosystems based on NP-complete problems like the knapsack problem, but never became as popular as RSA. Anyone have any guesses why we didn't see any popularly used crypto based on the hardness of, say, 3SAT or the knapsack problem?
I was hoping for an explanation about how some of those NP-complete problems have a large class of edge cases that make them vulnerable, or maybe that it's difficult to design protocols that use them. I wasn't hoping for a conspiracy theory.
It seems it's just really hard to create a new public key crypto system, so people sticked to what works as long as the quantum threat didn't sound too scary. Now it sounds scary enough that people look for alternatives.
It's still sort of just scary in the abstract. There's no evidence that a quantum computer that could attack even weak incarnations of DH or RSA are within the realm of feasibility, and if things break in engineering's favor over the next decade we still probably won't be there. It's possible that me might never get there!
The big problem is that there's a chance (a low chance) that we might get there within the (long) lifespan of our existing public key algorithms. There's a mindset in cryptography engineering that we design for secrets that must be kept for many decades. So: the "plausible" threat we face here is decades-hence retroactive decryption.
It's useful to keep this in mind when doing security engineering, because PQ isn't "free": we have to trade things off to get it. It's possible that the modern PQ schemes we're pursuing will have grave flaws that put them within reach of classical cryptanalysis within just a few years. Even more importantly, it's not only possible but likely that there are implementation errors --- like using schoolbook RSA, or failing to validate a curve point --- that we won't fully understand for a decade after we adopt a new PQ scheme.
And, just to make things more fun, we're not looking at 1 PQ scheme but at 3-4, some of them entirely unrelated to each other.
Against all this you should also keep in mind the other forces that push PQ to the front of the field of cryptography's consciousness. Most serious cryptography is done academically. PQ has created a gold rush of paper topics. Naturally, it's going to seem super important if you pay attention to IACR ePrints.
If what you're trying to protect are conventional financial transactions, or the integrity of applications running today that will have been rebooted at least once before 2050, there's a good chance that PQ is bad engineering for you.
What you need for cryptography is to be able to reliably generate hard instances. It's actually easy to factor most numbers--½ of all numbers are divisible by 2, and ⅓ of all numbers are divisible by 3. What's difficult is factoring products of similar-sized primes, and generating arbitrarily large primes is fairly easy. When you look at, say, graph coloring or graph isomorphism, it turns out that most named classes of such graphs turn out to be fairly easily solved, which means generating the instances that can't be solved easily is difficult.
39 comments
[ 2.2 ms ] story [ 101 ms ] threadhttps://www.scottaaronson.com/blog/
For classical systems, the cost to break RSA grows much faster than the cost to perform it, so we can always outpace more powerful adversaries with a less powerful computer. This is not true for quantum machines. I cannot produce a key size that will be small enough that I can work with it but large enough that it is secure against attack.
https://cr.yp.to/papers/pqrsa-20170419.pdf
And we still have to scale them with proper error correction. Who knows what the timeline for this looks like. Anyone who assumes "Moore's Law" isn't taking into consideration the fact that scaling here isn't as simple as multiplying the number of transistors in parallel.
To be useful they have to achieve entanglement between new qubits. Plus error correction and isolation have to also be scaled with that.
"Wait a minute... That means a qubit corresponds to a unit vector in two-dimensional Hilbert space!"
And quantum gates/operations on qubits are just unitary linear transformations on those vector spaces...
Here's an example with classical randomness (and has a close quantum analogue). If you have two closed boxes with coins in them and shake both around so that the coins flip around in the in such a way that they land 50/50 on each side, you could represent that state of the system as [1/4, 1/4, 1/4, 1/4], that is, each possible state of the system of two coins (heads head, heads tail, tail head, and tail tail), has 1/4 chance of being observed when you open the boxes.
Note that entanglement refers to the idea that two bits can be correlated. That is, the state of one is correlated with the state of another in some sense. In the example I just gave, the coins are not entangled, since the observation of one of the coins does not affect the probability of what the other coin could be. In mathematics we say this is possible if the state of the 2-coin system [1/4 1/4 1/4 1/4] can be written as a tensor product of the constituent 1-coin systems [1/2 1/2] and [1/2 1/2], which it can (entanglement refers to a state where this factorization isn't possible).
That said, we can achieve entanglement with the coins too, by somehow getting a state vector like [1/2 0 0 1/2] (50% chance that both coins are heads and 50% chance both are tails), which cannot be written as a tensor product of two 1-coin states. Moreover, if you open one box and see its a heads coin, you know the other box must also have a head coin. That's what is meant by 'correlation'. To product such a state of the coin boxes, I guess you would need a third party or something to put the two coins in the boxes and delivering them to you.
My conclusion is, entanglement doesn't have to do too much with the exponential size of representation n-qubit states, and I hope I gave a good example of what entanglement kind of really means. While (randomized) classical analogues to quantum effects are not really perfect, I think they demonstrate these effects more understandably.
Though, from a practical standpoint, I have a feeling that, regardless of how the computational classes shake out, the quantum Fourier transform will prove to be faster than classical techniques. And possibly Grover's algorithm, though its results are somewhat less dramatic.
http://www.bbc.com/news/av/technology-42426121/quantum-compu...
The recent UNSW silicon architecture announcement included something similar to that (480 qubit chip module that scales). Plus, they said they have an error-correction algorithm that will scale to millions of qubits.
https://newsroom.unsw.edu.au/news/science-tech/complete-desi...
Google has also suggested that they just need to get the stability of the first qubits right and then scaling them will be easier:
https://www.wired.com/2014/09/martinis/
In that post Martinis actually hoped they'd double the number of qubits every year, but I think it's been closer to 1.5-2 years, for both Google and IBM. Google plans to announce the rumored 49 qubits quantum computer next March.
D-Wave was able to double the number of qubits every year in their first four years, and now it seems to double every 2 years. I think D-Wave's capabilities have only improved significantly, rather than regressed with the number of qubits. We don't know yet if that's true for Google and IBM, but I would imagine it is.
To me, it's like comparing an analogue and a digital computer.
FFT is O(d log d) classically, and O((log d)^2) Quantum mechanically.
Gaussian elimination (used to find eigenvectors and eigenvalues) is O(d^3) or O(s * d^2) for classical (non-sparse and sparse, respectively) versus O((log d)^2) for Quantum.
(And similar speed up for Matrix inversion.)
FFT? Matrix inversion? Gaussian elimination? Super common. And in the case of Gaussian elimination, it gets pretty hard pretty fast.
You're right that we still have to scale with proper error correction, but the fact that quantum error correction is possible is very good news for the future of quantum computing. And the best, ~50-bit quantum computers are approaching what is needed for a fully error corrected qubit, although proper connectivity needs some work.
So you're right to be wary of the current status of quantum computing, but I think you're wrong about Moore's Law, here. Qubits can be and are made with photolithographically scalable techniques today with error rates that approach what's needed for error correction, even taking into account some of the problems that integration causes for integration. And, in fact, error correction is what enables us to scale quantum computing (although there are still some calculations we can do without error correction).
I do think we're pretty close to a threshold, here, with quantum computing. We are probably under one or two years away from "quantum supremacy," if you accept having a quantum computer too sophisticated to reliably simulate classically.
Some resources: Google talk about Quantum computing engineering work being done at MIT Lincoln: https://www.youtube.com/watch?v=Jgc20Xc8IpA
This man's blog is fantastic: https://medium.com/@decodoku/latest ...with a usefully skeptical take here: https://medium.com/@decodoku/quantum-computing-is-not-as-clo...
We aren't 3 years away from breaking encryption using Shor's Algorithm. We're probably at least a decade away. But there ARE a bunch of uses for quantum computing that don't require as many qubits. A few hundred physical qubits is still enough to do things that wouldn't be feasible with classical computing.
While some people have figured out how to used the result of the quantum FFT to do useful things (e.g. Shor's algorithm), it does not actually provide us with the transformed values in the traditional sense as the classical algorithm does.
https://crypto.stackexchange.com/questions/35482/which-ellip...
Curves still have a role in PQ systems through isogenies, which are mappings between entire curves. But those schemes are very different than the elliptic curves we use today; you can think of them as systems that exchange whole curves rather than curve points.
Misleading title?
If I were to write an article like this, I would probably choose a more explicit audience from the outset, then cover either a depth-first or breadth-first approach to the subject. A breadth-first approach would be good for a non-technical audience: here are the general types of cryptosystems, here are the ones threatened by quantum computers, here are the ones that are not, here are the current proposals for post-quantum resistant cryptosystems.
On the other hand, were I writing for a technical audience I would assume an understanding of why quantum computers threaten classical cryptography (and why e.g. symmetric encryption is mostly safe), then take a deeper look at each of the post-quantum proposals.
There is no evidence whatsoever that quantum computers will break SHA-256; I'd be willing to personally stake essentially all of my assets on the bet that it won't be broken within our lifetimes. I also cannot think of a credible cryptographer off the top of my head who has voiced the opinion that quantum computers pose a threat to the SHA-2 family (or SHA-3, for that matter).
At best I could see a complexity reduction, but nothing in polynomial time. Cryptographic primitives have such attacks published against them (and survive them) all the time.
1. Shortest Vector Problem (SVP) - Given a lattice with a basis B, find the shortest vector in the lattice.
2. Closest Vector Problem (CVP) - Given a lattice with a basis B and some target vector t, find the point v which is closest to t.
3. Shortest Independent Vector Problem (SIVP) - Given a lattice basis B in Z^(n x n), find n linearly independent lattice vectors [s1, ..., sn], where si is in the lattice of basis B for all i.
4. Learning With Errors (LWE) - Given integral starting parameters n, m and q, with a probability distribution X on Zq, distinguish between an input pair (A, v) and a vector e in (Zq)^m. A is chosen uniformly from (Zq)^(m x n) and v is (typically) chosen uniformly from (Zq)^m.
In other words, try to recover the secret key s in (Zq)^n by examining a sequence of approximate linear equations. The error introduced is what makes this computationally hard, otherwise it could be done in polynomial time using Gaussian elimination.
5. Learning Parity With Noise (LPN) - Given a secret length l, a noise rate 0 < r < 0.5 and the number of samples q, find the random l-bit secret string s in (Z2)^l using q samples. This is the search problem version; there is also a decisional variant.
There are good surveys that cover lattice-based cryptography in general or particular computational problems in greater depth; for example, try [1], [2], or [3].
________________________________________
1. Peikert, Chris: A Decade of Lattice-Based Cryptography - https://web.eecs.umich.edu/~cpeikert/pubs/lattice-survey.pdf
2. Micciancio, Regev: Lattice-Based Cryptography (chapter in Post-Quantum Cryptography)
3. Regev, Oded: The Learning With Errors Problem - https://cims.nyu.edu/~regev/papers/lwesurvey.pdf
It seems it's just really hard to create a new public key crypto system, so people sticked to what works as long as the quantum threat didn't sound too scary. Now it sounds scary enough that people look for alternatives.
It's still sort of just scary in the abstract. There's no evidence that a quantum computer that could attack even weak incarnations of DH or RSA are within the realm of feasibility, and if things break in engineering's favor over the next decade we still probably won't be there. It's possible that me might never get there!
The big problem is that there's a chance (a low chance) that we might get there within the (long) lifespan of our existing public key algorithms. There's a mindset in cryptography engineering that we design for secrets that must be kept for many decades. So: the "plausible" threat we face here is decades-hence retroactive decryption.
It's useful to keep this in mind when doing security engineering, because PQ isn't "free": we have to trade things off to get it. It's possible that the modern PQ schemes we're pursuing will have grave flaws that put them within reach of classical cryptanalysis within just a few years. Even more importantly, it's not only possible but likely that there are implementation errors --- like using schoolbook RSA, or failing to validate a curve point --- that we won't fully understand for a decade after we adopt a new PQ scheme.
And, just to make things more fun, we're not looking at 1 PQ scheme but at 3-4, some of them entirely unrelated to each other.
Against all this you should also keep in mind the other forces that push PQ to the front of the field of cryptography's consciousness. Most serious cryptography is done academically. PQ has created a gold rush of paper topics. Naturally, it's going to seem super important if you pay attention to IACR ePrints.
If what you're trying to protect are conventional financial transactions, or the integrity of applications running today that will have been rebooted at least once before 2050, there's a good chance that PQ is bad engineering for you.