Prof. Ueli Maurer

How to Fool Quantum Adversaries in Cryptography

At the frontiers of quantum computing and cryptography

Cryptography and Information Security Research Group

Non-classical quantum phenomena may allow computational tasks which are infeasible or even impossible with classical physics. For cryptography, this means that an attacker equipped with quantum devices might be able to break a cryptosystem, even one that has been proven to be secure against any classical adversary. This problem is now partly solved by a new result achieved at ETH showing that quantum storage devices are not more powerful than their classical counterparts. An implication is that cryptographic schemes previously proved to be secure against a classical adversary remain secure even against a quantum adversary.

Authors: Ueli Maurer und Renato Renner

Quantum physics is a godsend for cryptographers ...

Quantum physics, in contrast to classical physics, is often counterintuitive, contradicting our everyday experience. One of these properties is the impossibility of observing a particle, say a photon, without disturbing it. A photon thus ``looks different'' before and after it has been observed. This effect can be directly applied in cryptography: Assume that two parties, Alice and Bob, are connected by an optical fiber, and that they want to exchange secret messages. To do so, Alice first chooses a random key and sends this key, encoded into a sequence of photons, to Bob, using the optical fiber. Bob, upon receiving these photons, makes use of their quantum mechanical property to check whether the photons have already been observed, e.g., by an eavesdropper. If this is not the case, the key Bob obtained from Alice is guaranteed to be secure and can thus be used to encrypt the secret messages they want to exchange.

Another interesting property of quantum mechanical systems is the so-called superposition of states. The probably most famous example illustrating this peculiarity of quantum physics is Schrödinger's cat:

Classically, a cat can either be dead or alive. In quantum mechanics, a cat -- if it would have the properties of small particles -- could be in an arbitrary state in between. This is the effect quantum computers are based on: A storage register of a quantum computer can not only contain one fixed value, but rather an arbitrary superposition of values, e.g., all numbers from 1 to 100. In a computation, all these values are then processed simultaneously. For instance, if the squaring operation is applied on the superposition of values from 1 to 100, the outcome is the superposition of all square numbers from 1 to 10000. This apparent parallelism can be used to solve efficiently certain problems which are believed to be infeasible on a classical computer, e.g., factoring large numbers.

... but it is also a threat ...

The two examples sketched above illustrate the two-fold significance of quantum information processing in cryptography: On one hand, it allows for the construction of provably secure cryptosystems. On the other hand, many of today's cryptosystems become completely insecure against an adversary equipped with a quantum computer. For instance, the security of public key cryptosystems such as RSA relies on computational assumptions, e.g., that factoring large numbers is not possible within reasonable time, an assumption which is, as mentioned above, not true for quantum computers.

Using quantum effects might thus be advantageous for an attacker trying to break a cryptosystem, even if the cryptosystem itself is purely classical. This means that security of a cryptosystem against classical adversaries does not necessarily imply its security against quantum adversaries. In view of the fact that our real world is indeed quantum mechanical, even classical cryptographers are forced to face this problem of quantum adversaries.

... which is, however, less important than it seemed to be!

One step towards a general solution of this problem has recently been achieved by proving that quantum storage devices are in a certain sense not more powerful than purely classical storage devices (see box "Classical and Quantum Bits"). This is important for cryptography: it implies that a cryptosystem which is secure against an adversary holding a certain limited amount of classical information remains secure even against an adversary gathering the same amount of quantum information.

Entanglement and Pseudo-Telepathy

One of the most intriguing properties of quantum mechanics is that the behavior of distant systems can be correlated. This so-called entanglement can be illustrated by pseudo-telepathy games. These are games which can always be won by collaborating players if they are allowed to use quantum entanglement, while, for purely classical players, there is some unavoidable probability to lose the game. A simple example of such a game for n players P1, ..., Pn is as follows:

First, two players Pi and Pj are randomly chosen and separated in such a way that neither of them knows who the other one is. In particular, no communication between them is allowed. Then, each of them is asked to pick one of two possible colors, say red or blue. The game is lost if they pick the same color, otherwise they win.

Since the two chosen players Pi and Pj are not allowed to communicate, they will, with a certain probability, pick the same color and thus lose the game. This is even true if the remaining n-2 players can choose the two colors from which Pi and Pj have to pick one. However, it can be shown by simple quantum information theoretic arguments that if the players use quantum entanglement (but still no communication between them is allowed) they can always win the game [2].

Classical and Quantum Bits

While a classical bit can only be in two possible states, usually denoted as 0 and 1, a quantum bit is in one of infinitely many so-called superpositions of them. A classical bit is thus by far not sufficient to describe the state of a quantum bit, i.e., a quantum bit seems to contain more information than its classical counterpart. Nevertheless, as the following result suggests, this apparent quantum advantage is not relevant.

Consider an entity who is given access to an n-bit random string S and can store arbitrary information about S in r bits of memory (classical or quantum), where r<n and thus the stored information about S is bound to be only partial. Later, when only the stored information is available, a random binary question about S is asked. The maximum probability of correctly answering this question is then a measure for the usefulness of the information stored in the r classical or quantum bits. It has now been shown [1] that this probability is roughly the same for both the classical and the quantum case.

Footnotes:

[1] Robert Koenig, Ueli Maurer, Renato Renner. On the Power of Quantum Memory. e-print-archive: http://arxiv.org/abs/quant-ph/0305154

[2] Renato Renner, Stefan Wolf. Towards Characterizing the Non-Locality of Entangled Quantum States. e-print-archive: http://arxiv.org/abs/quant-ph/0211019