FQ is OK with me, please move it if you think it fits better than in MPSIMS.
I wonder if the OP was inspired to ask based on this news making the rounds this week:
No, I was not, I don’t usually read crypto-news sites, but it goes in the direction I was musing. If the problem is so obvious that even me, a complete aficionado, can figure out that there could be trouble ahead the professionals must be aware of that too. Nice to know that the general direction of my thinking is not completely off base. A bit sad to see that cryptocurrencies are not going to collapse tomorrow. Probably.
I would suggest that, if quantum computing continues to progress, this is a sticking plaster that will not stop the bloodbath.
The threat to Blockchain is just an example of technological advancements challenging our security and systems. It’s an arms race and some security solutions will inevitable hit a brick wall.
Another example of the arms race in action:
Done.
Thanks! I was overthinking when I put it in MPSIMS. It does fit better here indeed. 
Is there anything where there is a mathematical proof that something has no classical solution, but where it is believed that this may not hold for quantum?
There are certainly threats to the security of most cryptocurrencies from quantum computers, as well as to most forms of currently used encryption in general. However, these threats are well known, and there are active mitigation measures—NIST has begun evaluation of ‘quantum safe’ encryption methods in 2016, and has introduced standards as well as migration timelines (deprecation of unsafe methods by 2030, and fully disallowing them by 2035). So there are already active efforts to mitigate the problem.
Of course, there is significant uncertainty as to the actual timelines in play. There have been recent algorithmic breakthroughs that have significantly reduced the resource estimates for breaking current encryption methods (both integer factorization based RSA, which secures most internet traffic, and elliptic curve/discrete logarithm based methods), from needing a quantum computer with ~20,000,000 qubits to needing only ~1,000,000 or even 100,000 qubits with a specific architecture (500,000 for elliptic curves). (Current devices, depending on architecture, are on the order of ~1,000 qubits.) It remains to be seen whether these breakthroughs make their way from the drawing board into the real world, but as one data point, Google (whose researchers are behind some of these breakthroughs) has publicly stated that they have accelerated their timeline for migration to quantum-safe encryption internally to 2029. Since this is a process that probably won’t come cheap, they seem to put at least some stock in their own hype. Also, Android 17 will ship with native support for post-quantum cryptography.
(Anyhow, I’m a researcher in quantum computing, so if there are any further questions, I’d be happy to try and answer them.)
Depends on what you mean by that. In principle, quantum and classical computers compute all the same things (i.e. the set of computable functions is the same for both paradigms), however, the complexity (how much the computation time and/or resources increase if the input size increases, roughly) may scale differently in certain cases. The most well-known of these cases is integer factorization, which is what underlies (most) current cryptography, such as RSA. There, it is strongly conjectured that the best classical algorithms take exponential time (well, sub-exponential, technically), while Shor’s algorithm takes polynomial time on a quantum computer (exponential and polynomial here are to be understood such that the time it takes to solve an instance of size n grows exponentially or polynomially with n). There currently is no known classical algorithm that can equal the performance of the quantum algorithm, but there is no proof that such an algorithm doesn’t exist—however, we’re sure enough that none does that we wager essentially the whole of global cybersecurity on that assumption.
There are, however, cases where a provable speedup for quantum computing exists. The most well-known example is searching through an unstructured database for a particular element: if there are n elements in the database, you’d have to make \frac{n}{2} comparisons to find what you’re looking for on average using a classical strategy, but a quantum algorithm (Grover’s algorithm) exists that needs only ~\sqrt{n} steps. That’s a far more modest speedup than in the case of Shor’s algorithm, but this also yields an ‘one size fits all’ improvement for a large class of problems: any problem that is difficult to solve, but where the solution is simple to verify (like integer factorization, because multiplication is fast), receives a speedup by just checking all possible solutions. There are also examples of greater provable speedups, such as for the game Mastermind.
While this isn’t something that classical computers can’t do, for relevant problem sizes, they may take millions of years, while a quantum computer achieves the result within hours (see here for an interesting visualization). But depending on your definitions, there may also be things that quantum computers can do, that no classical ones can. This point was first raised by Feynman, who stated that ‘it is impossible to represent the results of quantum mechanics with a classical universal device’. A simple example is randomness: if quantum mechanics is genuinely random (and there are good reasons to think it is), then no classical computer can account for quantum measurement outcomes. There are also quantum systems that show properties corresponding to classically undecidable questions, most notably the question whether a quantum system has a finite difference in the energies of its ground state and first excited state. One may be divided regarding the significance of this and similar results, however—after all, undecidable questions also arise in classical systems (albeit, to the best of my knowledge, only regarding the long-term behavior of systems, such as the question of whether a certain configuration is ever achieved, not in their properties).
All it will take for a massive movement to quantum safe forms of TLS (https encryption) is for Google to announce they will be downranking non-quantum safe websites. This is the same as the big increase in encrypted websites 10+ years ago when Google started downranking unencrypted websites.
No one has proved that factorization is NP hard, but it does succumb to quantum computers. As explained by @peccavi there is a quantum algorithm that is, in principal, unbreakable. It uses a one-time pad for encryption and the pad is sent for decryption by a quantum exchange mechanism.
Note, BTW, that if you have captured some current encrypted data, then you will be able to decode it when you get your quantum computer. So anything you exchange today might be vulnerable in a decade.
Nope, nowhere, much though people would like one. There’s a classification scheme for problems, with a category called “NP” which includes nearly every problem worth considering, and a category called “P” for problems which can be solved easily*, and everyone thinks that there are some NP problems that aren’t in P, and there are problems where we know that, if there’s anything that’s not in P, those problems aren’t… but nobody has ever actually proven that the NP category isn’t just the same as the P category. In other words, it might be that all problems can actually be solved easily by a classical computer, and we just haven’t figured out the trick for how to do it yet.
Well, it’s not quite the same, because in that case, the public key infrastructure capable of implementing this switch was already in place, whereas post-quantum cryptography needs at least some revision to existing structures. For one, the computations involved are more challenging, so there’s likely some degree of hardware upgrades that’s necessary. Likewise, you’ll need more network throughput.
While it’s true that nobody knows if there are classically efficient algorithms to solve NP-hard problems, P vs. NP is not the only separation worth considering, and beyond that, there are indeed known speedups for quantum algorithms. Beyond time complexity, one can for instance look at query complexity, where the relevant question is how many times a (‘black box’) function needs to be evaluated. There, we have several known examples of an unconditional quantum speedup, with the most well-known being Grover’s algorithm, which, as noted above, reduces the complexity of searching through an unsorted database of n entries from O(n) calls in the classical case to O(\sqrt{n}) calls.
This can also yield a reduction in terms of time complexity, if the test of whether the checked item fulfills the criteria for whatever you’re looking for is simple, e.g. can be done in polynomial time. This is the case for factorization, where you just have to multiply numbers to check whether your guess is right. And while that yields only a relatively modest speedup, there are also known exponential and super-exponential speedups in the query complexity model, most famously Simon’s problem, but also the Mastermind-algorithm posted above.
That seems to me like a difference between the problem being easy with a classical computer versus even easier with a quantum computer, not going from being effectively impossible to being doable. I don’t think you could make a practical, high-security encryption system using a problem that’s merely polynomial to brute-force (yes, in principle, you could have a polynomial-complexity problem with very high exponents or coefficients, but I have my doubts that you could actually make them high enough).
Well, if one can use Grover’s algorithm to speed up the solution of a problem from taking 100 years to 10, I think that’s quite a gain in feasibility. However, actually achieving the Grover speedup is probably going to be more difficult than e.g. in the case of Shor’s algorithm, because one has to go to bigger problem instances and hence, larger quantum computers. But for other unconditional, even exponential speedups, the first demonstrations on present-day hardware already exist, see e.g. here.
Of course, the first practically relevant quantum computers aren’t going to be doing any of these things. Right now, the best hope are either heuristic optimization algorithms, or the simulation of quantum systems. Neither of these have a proven speedup, but of course, for practical problems, that’s not relevant: like with factoring integers, if you can do it faster than any current classical algorithm, the $1 million you’d stand to gain from establishing the speedup formally would rather be pocket change.
But we already know how to speed up a problem from taking 100 years to taking 10: Throw ten times as many computers at it. Which it’s probably worth doing, if it’s a problem that’s worth spending ten years on solving it. Converting an exponential-time problem to a polynomial-time problem, though, can mean increases in speeds in the factors of trillions or more, which we can’t do just by devoting more resources.
I think I’m missing your point. If it’s about a theoretically provable speedup, there absolutely are examples of even super-exponential speedups (in query complexity) that don’t depend on any unproven assumptions; if it’s about practically realizable advantage, then it doesn’t really matter whether we can prove that P = NP, as long as nobody has a classical algorithm with subexponential time complexity that solves a given problem. Even proving that such an algorithm exists doesn’t mean we can find it, so the quantum device will still yield a practical advantage.
Yeah, I had a paragraph about the software not being ready that I removed for brevity. Bottom line is, the software is being actively worked on.
I’m not sure about new infrastructure, though. If all I have to do is adjust my web server’s config files to allow quantum safe algorithms available in the latest update, that really isn’t new infrastructure. All of the SSH that I manage became quantum safe doing nothing but following the standard upgrade path.
I thought the big benefit is in the key exchange, and not the symmetric cypher used after that? I could be wrong, as I’m not an expert in how the cryptography works, just in turning it on. If the initial key exchange is more computationally intensive, but the bulk of the data is the same as now, I don’t think it will require a big upgrade in computational power or network throughput.
We have time to get it sorted out, though, as the largest number ever factored by a quantum computer is 21 or 27 or something like that. I’m basing this on the recent Gutmann paper. I do not have anything like the knowledge to critique the paper, or find its flaws.
Their argument is that all of the large factorizations by quantum computers have been cheating or are otherwise not representative of real world uses, and can be recreated by a dog trained to bark three times.
Maybe that’s true for reasonably current systems, but there’s tons of legacy hardware around that can’t support PQC algorithms and will need to be replaced. The latest estimate by the US government is to the tune of $7.1 billion in order to make the transition for federal agencies. There is also the problem that the data exchanged for post-quantum cryptography schemes is much larger than that for current SSL encryption.
I’m not sure if you’re conflating quantum key distribution and post-quantum cryptography here. The former uses quantum effects to establish a physically secure way of establishing, essentially, a shared string of random bits that can be used to encrypt a message by adding the random bits to the message, i.e. a one-time pad. The benefit of this is that any attempt to ‘eavesdrop’ on the key exchange is detectable during the protocol, so if it is successful, you know that nobody else can have a significant amount of the established key. The latter is using classical encryption algorithms, such as lattice-based cryptography, which are believed to be secure against attacks using quantum computers. There, any handshake will have significantly larger overhead to be transmitted across the network.
That claims that worst case the initial handshake is pushed to 15k from 1k. Sounds terrible, and there is much ringing of hands about it, but I’m not sure if it matters. Have you seen how much each web page downloads in javascript and other crap? Plus things like HTTP/2 and QWIK keep the connection open, greatly reducing the number of handshakes that have to happen over HTTP/1.1.
Sure, increasing all traffic across the internet by 1% or whatever was claimed is lots of additional traffic, but that could probably be clawed back by reducing the size of a few common ad or surveillance libraries.
No, it’s the two stages of TLS. First is the handshake and key-exchange (both sides have different keys), and second is the symmetric encryption (both sides use the same key they just shared with each other). It’s only the first part that needs a quantum safe algorithm, as symmetric cryptography is generally thought to be quantum safe as is.
That works for some types of problems, but not others.
The question of how to parallize algorithms is still very much with us in computer science.