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.