Communications of the ACM

lyze the three categories of quantum cyber security research. We explore post-quantum security, giving a brief overview of the field and focusing on the issue of security definitions and proof techniques. Then we sketch the research directions in quantumly enhanced security, focusing on the issue of implementation attacks and device independence. Later, we focus on classical clients securely delegating computations to the quantum cloud and conclude with a glimpse of how we envision cyber security will be reshaped in the decades to come.

Myths and Realities about
Quantum Computing

In many popular accounts, quantum computers are described as some mythical computation devices that, if ever constructed, would magically solve pretty much anything one can imagine in a fraction of a second. In reality, the power of quantum computers is much more modest. Here, we clarify four of the most common misconceptions on the computational power and possibilities of quantum computers and quantum adversaries. In this way we can see the effects on cyber security research more clearly.

Myth 1. Quantum computers are much faster in performing operations than classical computers.

Reality. Quantum computers are not faster in the sense of implementing larger number of operations per second. The computational speed-up that quantum computers offer is achieved because quantum theory allows algorithms that include operations practically impossible for classical computers. Therefore, to achieve a speed-up is a task that requires the invention of new algorithms that use these operations suitably and is not straightforward. Indeed, the exact speed-up highly depends on the specific problem considered. This problem-dependency of the speed-up justifies why a quantum adversary can break only certain public-key cryptosystems, while others may remain secure with minor modifications (for example, in the key lengths).

Myth 2. Quantum computers simultaneously perform all branches of a ( probabilistic) computation and can find accepting paths instantly.

Reality. Quantum computers span the space of possibilities, computational branches, in a peculiar way. It is similar with classical probabilistic computers (bpp),b with the important difference that quantum computers behave as having “probabilities” that take complex values. This behavior, leads to “cancellations” of certain branches, since adding complex numbers is not monotonically increasing (unlike adding numbers in the interval [0, 1] as for BPP devices). This property, along with algorithms that exploit it, leads to quantum speed-ups. However, at the end of a quantum computation, the result (accepting/rejecting in a decision problem) is obtained by a single read-out/measurement and, therefore, all the “unrealized” branches do not contribute, contrary to the myth that quantum computers perform all branches in parallel in a way that someone can meaningfully extract all the information present in those branches.

Myth 3. Quantum computers can efficiently solve NP-complete problems (such as Traveling Salesman Problem).

Reality. The class of decision problems that quantum computers can solve efficiently is called BQP. Its ( conjectured) relation to other known classes can be seen in Figure 2. In particular, we see that NP is not contained in bqp and, therefore, a quantum computer cannot solve a NP-complete problem efficiently. Having said that, it is important to note that quantum computers may (and do) provide polynomial or b It is the class of decision problems that can be solved efficiently by a probabilistic Turing machine with error bounded away from 1/2. This class captures well the problems that can be solved efficiently by modern classical computers.

constant speed-up in many problems outside bqp (for example, quadratic search speed-up), including such speed-ups for NP-complete problems.

For many tasks, even such a moderate speed-up could be of great importance. In cyber security, for example, it affects the size of keys needed to guarantee a requested level of security.

Myth 4. Using problems that are hard for a quantum computer (outside BQP) suffices to make a cryptographic protocol secure against any quantum attack.

Reality. This is a necessary but not sufficient condition. A quantum attacker can use quantumness in various ways, not only in order to solve some classical problems quicker. Next, we give such examples (superposition attacks) and specify that both the security definitions and the proof techniques need to be modified.

Post-Quantum Security:
Quantum Adversaries

Even if one is not convinced of the necessity to drastically change the existing cryptographic protocols and infrastructure to use quantum technologies in a positive way, they still must address the possibility that current or future adversaries might use such technologies to their benefit. Since scalable, fault-tolerant, quantum computers that could break current cryptography require thousands of qubits, one could assume this is unlikely to happen in this decade.

However, there are three important reasons why we need to address quantum attackers now. Firstly, security can be broken retrospectively. For instance, if some agency intercepts and stores encrypted email messages sent today, and 10 years later develops a quantum computer, they can then use it to decrypt them. 1 Secondly, to develop cryptographic solutions that are post-quantum secure, to achieve high efficiency and to build confidence on the security of these solutions is an endeavor that requires years of research by multiple, independent, top research groups. Thirdly, changing the cryptographic infrastructure will also require years once we have decided to do it.