## Quantum Computing and Cryptography

If you google “Is Quantum Computing Dangerous”, you will find headline after headline about the imminent dangers of quantum computing. Articles instilling fear in readers through the talk of the ways that Quantum computing is a “tool of destruction”, or that it is the “end of cryptography”. Articles such as this one argue that modern cryptography will be defeated and even ends with the following statement “Should the Russian government break all of our encryption before the US develops countermeasures, stolen elections will seem like small potatoes. Welcome to the cyber-battlefield of the 21st century.” Where are these fears coming from, and are they substantiated? Should we actually fear a complete breakdown of cryptographic methods if quantum computing technology advances? Will it advance to that state?

First, the fears about cryptography. Many cryptographic methods and schemes, such as RSA, are built on top of the difficulty of solving one-way mathematical functions, such as prime factorization. These problems are easy to compute in one direction, but take exponential time in the other direction, so the ability to guess and break a method such as RSA are not feasible with modern computers, which at best solve problems in linear time. However, theoretically, quantum computers should be able to compute problems much faster, even problems that would normally take exponential time to solve. On the face of it, this would mean that all our current systems, i.e. banks, national security, etc. would be compromised if someone had a quantum computer that truly worked as a quantum computer (i.e. each qubit, rather than storing two possible states, 0 and 1, store three states, 0 and 1 and 0 and 1. When you multiply out the additional computing power for many hundreds of thousands of bits, then its easy to see the where the additional computing power would come from). Its easy to see the fear in this -> at face value it boils down to an arms race with a crazy powerful weapon that could break all cyper security and cryptographic schemes by solving exponential time algorithms in quadratic time.

But, in reality this fear seems a bit too strong. What is the current progress of quantum computers? Is it even possible to reach create a fully functional quantum computer with more than 50 qubits (the number needed for quantum supremacy, that is a quantum computer that cannot be simulated on a classical computer)? Currently, there are some serious roadblocks in the practical creation of such a machine, with IBM having the closet possibility of it. But, even if such a machine is to come, “it isn’t obvious how useful even a perfectly functioning quantum computer would be. It doesn’t simply speed up any task you throw at it; in fact, for many calculations, it would actually be slower than classical machines. Only a handful of algorithms have so far been devised where a quantum computer would clearly have an edge. And even for those, that edge might be short-lived. The most famous quantum algorithm, developed by Peter Shor at MIT, is for finding the prime factors of an integer. Many common cryptographic schemes rely on the fact that this is hard for a conventional computer to do. But cryptography could adapt, creating new kinds of codes that don’t rely on factorization.” -> https://www.technologyreview.com/s/610250/serious-quantum-computers-are-finally-here-what-are-we-going-to-do-with-them/

The truth is, there are serious difficulties ahead for the advancements of quantum computers to a useful state, and it doesn’t currently seem like there are that many practically useful efforts for quantum computers. Moreover, if a quantum computer was created, cryptography could adapt quickly to rely on a NP-Hard problem that is not easily solvable by a quantum computer (which would need some sort of quantum algorithm to solve the problem in the first place). All in all, the technology is incredibly interesting, but it does not seem like much of the current fear is merited. At least for the time being.

## 1 Comment »

1. ### Cassper Nyovest

October 29, 2018 @ 5:50 pm

1

Quantum Computing hasn’t really been elaborated clearly in my country, I would really love to get more insights in the topic and also cryptocurrency.