and methods used, and on the cryptanalysis of existing protocols beyond
what is implied from giving an oracle
access to a quantum computer.
Quantumly Enhanced
Security: Quantum Gadgets
for Classical Parties
Quantum technologies can also offer advantages for cyber security research. To
view this positive aspect, we should consider the possibility of including quantum steps in (honest) protocols with the
aim of achieving certain improvement
compared to the corresponding fully
classical setting. The fact that improvements are in principle possible is well
established, with the best known example that of quantum key distribution (QKD).
6 In QKD, using untrusted
quantum channels and classical authenticated channels one can establish a shared, secret key between two
spatially separated parties, with information theoretic security. This task, essentially information theoretic secure
key expansion, is impossible using
only classical communications. Importantly, having a protocol with information theoretic security means the security is not based on any computational
assumption and therefore remains secure even in the presence of an attacker
with a quantum computer. Another
example of quantum enhancement is
the quantum fingerprints,
40 where two
parties can establish if they are sharing
the same bit-string using minimal communication. The best classical communication complexity is Ω(√– n), which is
exponentially more than the quantum
communication of O(log2 n).
We are interested in using “quantum
gadgets,” usually with simple quantum
devices (available with current state-of-the-art technologies), to boost classical protocols in a number of ways. The
types of enhancement/advantages offered could be, for example, information theoretic security from a computationally secure classical protocol (as in
QKD); “computational” security against
quantum attackers from no security
against quantum or classical attackers;f
f For example, in position verification one can
achieve a quantum protocol with security
against adversaries with bounded amounts of
shared entanglement,
14 while no fully secure
classical position verification protocol exists,
against multiple colluding adversaries.
tion proof technique and the role of rewinding). In rewinding, the simulator
is given the ability to copy the internal
state, and in some cases to rewind it to
an earlier step. However, due to the no-cloning theorem we know that general
quantum states cannot be copied. This
problem was identified early37 while two
weaker versions of quantum rewinding,
attempting to fix this issue, have been
later developed. The first is the oblivious
quantum rewinding,
39 where one can rewind but is not allowed to “remember”
the transcripts of the previous runs apart
from whether a rewinding was necessary
or not. The second is the special quantum rewinding,
36 where by demanding
some extra conditions (special and strict
soundness) one can retain information
from two runs of the rewinding process.
Using quantum-rewinding steps comes
at a cost, since it can only be proven that
the rewound state is close but not exactly
the same as the non-rewound state. This
leads to a (small) distinguishing possibility between the real and simulated
views, affecting the security parameters
of the protocol.
These (limited) quantum-rewinding
steps can be used to achieve important
primitives. In particular the oblivious
rewinding was used to prove quantum
security of zero-knowledge proofs, while
the special quantum rewinding to prove
quantum security of proofs of knowledge.
Another application of the quantum rewinding is as subroutine in
certain proof techniques. In order to
prove security one frequently proves
the security against a very weak (
essentially honest) adversary and then
adds a mechanism that enforces fully
malicious adversaries to behave as
the weak adversary or else abort. Such
techniques are the Goldreich-Micali-Wigderson (GMW) compiler and the
cut-and-choose technique. Both can be
used to prove the security of Yao’s seminal secure two-party computation protocol against malicious adversaries,
and both require rewinding. The GMW
compiler uses zero-knowledge proofs
and thus the quantum secure version
already mentioned suffices, while the
cut-and-choose technique can also be
proven quantum secure using the special quantum rewinding.
26
To recap, considering fully quantum adversaries has consequences in
security definitions, proof techniques
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
operations.