as having access to all the terms of the superposition, in the same way that in Myth 2 we explained not all paths are realized. For example, if one measured directly this superposition they would receive a single ciphertext of one ( randomly chosen) plaintext and the security would not be compromised. Instead, attacks involve using this output superposition of ciphertexts state in another quantum algorithm that would reveal hidden structures of the cryptosystem.

Requesting from protocols to be secure against this type of attacks leads to new security definitions for a number of functionalities (for example, quantum indistinguishability). Boneh8 was the first paper to offer such definitions, where the quantum random oracle model was defined.c Since then encryption, signatures, pseudo-random functions and message authentication codes have been similarly defined. 9

Interestingly, there have been attacks of this type to symmetric cryptosystems recently, that provide an exponential speed-up. 25 This was the first quantum attack with exponential speed-up to symmetric cryptosystems, using Simon’s algorithm. It does not use Shor’s or Grover’s algorithmd that are the quantum algorithms typically used to attack cryptosystems, and demonstrates that post-quantum security is much more subtle than generally believed. It is important to require these higher notions of security and to review all candidate post-quantum cryptosystems in the light of quantum cryptanalysis as described.

We should comment on an obvious
objection that one could raise, namely
that our systems are classical and there-
fore applying (for example) the encryp-
tion algorithm “coherently” on a super-
position input, seems not physically
motivated.e We use a hypothetical ex-
c The (classical) random oracle is an oracle
that to each call it responds with a random
response. It is used, for example, as a mathe-
matical abstraction to capture the idea of cryp-
tographic hash functions in security proofs.
d Attacks using Grover’s algorithm were per-
formed, for example, on the original Merkle’s
key exchange, and only recently post-quantum
secure modification was developed.
e Such attacks will be crucial in the future when
the infrastructure will, by default, allow for
quantum information processing, but here
we argue that even before that, these attacks
could be implementable.
ample of “Frozen Smart-Card” given in
Gagliardoni21 to demonstrate that one
should not ignore this type of attacks
even now. Real-world encryption and au-
thentication is frequently implemented
on small electronic devices such as
smart cards. A quantum attacker could
implement a side-channel attack where
they get hold of the smart card and at-
tempt to freeze it to a temperature that
starts behaving quantum mechanically.
Then they attempt to query it in super-
position. This type of side-channel at-
tack is not very different to side-channel
attacks considered on cryptographic
hardware in today’s labs, using thermal
or electromagnetic manipulation.
Proof techniques against quantum
adversaries. To take the most general
view, we should model the internal
space of a quantum adversary as a
generic quantum state and all their
actions and communication (with
honest parties) as generic quantum op-
erations. Modeling the adversary quan-
tumly has two effects. On the one hand
it gives the adversary more ways to devi-
ate/attack, as for example in the super-
position attacks described previously.
On the other hand, it has an effect on
how to prove security since simulating
their view requires simulating quan-
tum rather than classical processes.
Note that showing that a proof tech-
nique is not applicable does not mean
finding an attack that breaks the corre-
sponding cryptosystem, it only means
it is no longer provably secure.
For example, to define and prove
security in functionalities such as se-
cure multiparty computation (SMPC)
the concept of simulation is frequently
used. In particular, an adversary should
be unable to distinguish whether they
are interacting with the real (honest)
parties or a simulated view that has no
direct access to the private information
of the parties involved. 28 However, since
the internal space of the adversary and
the interaction with the simulator are
quantum the simulated view should
also be quantum. This is incompatible
with existing constructions of simula-
tors, where the steps taken are not pos-
sible for general quantum states.
The key example that we implicitly
assume having classical systems when
constructing the simulators is the “re-
winding” step (for example, see Lindell28
for a detailed explanation of the simula-
In order to define
the quantum-bit
security of a crypto
system, one must
establish which
is the fastest
algorithm that
attempts to break
the system.