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.
We will divide the research in post-quantum cryptography in three classes, according to the ways we allow the
adversaries to use their “quantum
Figure 2. Conjectured relation of complexity classes.
The conjectured relations are reinforced by
the existence of oracle results that separate
BQP with NP.
BQP NP
PSPACE
P