Quantenkryptographie

Quantum cryptography describes the use of quantum mechanical effects (in particular quantum communication and quantum computation) to perform cryptographic tasks or to break cryptographic systems. The use of classical (i.e., non-quantum) cryptography to protect against quantum attackers is also often considered as quantum cryptography (in this case, one also speaks of post-quantum cryptography).

Well-known examples of quantum cryptography are the use of quantum communication to securely exchange a key (quantum key distribution) and the (hypothetical) use of quantum computers that would allow us to break various popular public-key encryption and signature schemes (e.g., RSA and ElGamal).

The advantage of quantum cryptography lies in the fact that it allows to achieve various cryptographic tasks that are proven or conjectured to be impossible using only classical (i.e., non-quantum) communication (see below for examples). In particular, quantum mechanics guarantee that measuring quantum data disturbs that data; this can be used to detect an adversary's interference with a message.

However, researches at NTNU showed that man-in-middle attacks are possible without detections in some implementations of quantum systems.

Quantum key distribution

Arguably the best-known application of quantum cryptography is quantum key distribution (QKD). (First proposed by Bennett and Brassard based on ideas by Wiesner ) QKD describes the process of using quantum communication to establish a shared key between two parties (usually called Alice and Bob) without a third party (Eve) learning anything about that key, even if Eve can eavesdrop on all communication between Alice and Bob. This is achieved (roughly speaking) by letting Alice encode the bits of the key as quantum data before sending them to Bob; if Eve tries to learn these bits, the messages will be disturbed and Alice and Bob will notice.

QKD is possible without imposing any computational assumptions (that is, assumptions stating that certain mathematical problems such as factoring large numbers take very long time to solve on a computer). One also speaks of "unconditional security". The only assumptions are that the laws of quantum mechanics hold (which is to a certain extent disputable due to the difficulties of unifying relativity theory and quantum mechanics), and that Alice and Bob have an authenticated channel, i.e., Eve should not be able to impersonate Alice or Bob as otherwise a man-in-the-middle attack would be possible.

In contrast, without quantum communication (i.e., using only an authenticated channel for transmitting classical data), key exchange needs computational assumptions; and attacker that has no limitations on his computational power can extract the key from the communication of Alice and Bob.

QKD is the only example of commercially available quantum cryptography.

Quantum commitment

Following the discovery of quantum key distribution and its unconditional security, researchers tried to achieve other cryptographic tasks with unconditional security. One such task was commitment. A commitment scheme allows a party Alice to fix a certain value (to "commit") in such a way that Alice cannot change that value any more while still ensuring that the recipient Bob cannot learn anything about that value until Alice decides to reveal it. Such commitment schemes are commonly used in cryptographic protocols. In the quantum setting, they would be particularly useful: Crépeau and Kilian showed that from a commitment and a quantum channel, one can construct an unconditionally secure protocol for performing so-called oblivious transfer. Oblivious transfer, on the other hand, had been shown by Kilian to allow to implement almost any distributed computation in a secure way (so-called secure multi-party computation). (Notice that here we are a bit imprecise: The results by Crépeau and Kilian and Kilian together do not directly imply that given a commitment and a quantum channel one can perform secure multi-party computation. This is because the results do not guarantee "composability", that is, when plugging them together, one might lose security. Later works showed, however, how composability can be ensured in this setting.)

Unfortunately, early quantum commitment protocols where shown to be flawed. In fact, Mayers showed that (unconditionally secure) quantum commitment is impossible: a computationally unlimited attacker can break any quantum commitment protocol.

Yet, the result by Mayers does not preclude the possibility of constructing quantum commitment protocols (and thus secure multi-party computation protocols) under assumptions that are much weaker than the assumptions needed for commitment protocols that do not use quantum communication. The bounded quantum storage model described below is an example for a setting in which quantum communication can be used to construct commitment protocols.

Bounded quantum storage model

One possibility to construct unconditionally secure quantum commitment and quantum oblivious transfer (OT) protocols is to use the bounded quantum storage model (BQSM). In this model, we assume that the amount of quantum data that an adversary can store is limited by some known constant Q. We do not, however, impose any limit on the amount of classical (i.e., non-quantum) data the adversary may store.

In the BQSM, one can construct commitment and oblivious transfer protocols. The underlying idea is the following: The protocol parties exchange more than Q quantum bits (qubits). Since even a dishonest party cannot store all that information (the quantum memory of the adversary is limited to Q qubits), a large part of the data will have to be either measured or discarded. Forcing dishonest parties to measure a large part of the data allows to circumvent the impossibility result by Mayers; commitment and oblivious transfer protocols can now be implemented.

The protocols in the BQSM presented by Damgård, Fehr, Salvail, and Schaffner do not assume that honest protocol participants store any quantum information; the technical requirements are similar to those in QKD protocols. These protocols can thus, at least in principle, be realized with today's technology. The communication complexity is only a constant factor larger than the bound Q on the adversary's quantum memory.

The advantage of the BQSM is that the assumption that the adversary's quantum memory is limited is quite realistic. With today's technology, storing even a single qubit reliably over a sufficiently long time is difficult. (What "sufficiently long" means depends on the protocol details. By introducing an artificial pause in the protocol, the amount of time over which the adversary needs to store quantum data can be made arbitrarily large.)

In the classical setting, similar results can be achieved when assuming a bound on the amount of classical (non-quantum) data that the adversary can store. It was proven, however, that in this model also the honest parties have to use a large amount of memory (namely the square-root of the adversary's memory bound). This makes these protocols impractical for realistic memory bounds. (Note that with today's technology such as hard disks, an adversary can cheaply store large amounts of classical data.)

Post-quantum cryptography

In a predictive sense, quantum computers may become a technological reality; it is therefore important to study cryptographic schemes that are not themselves making use of quantum mechanical effects but that are (supposedly) secure even against adversaries with access to a quantum computer. The study of such schemes is often referred to as post-quantum cryptography. The need for post-quantum cryptography arises from the fact that many popular encryption and signature schemes (such as RSA and its variants, and schemes based on elliptic curves) can be broken using Shor's algorithm for factoring and computing discrete logarithms on a quantum computer. Examples for schemes that are, as of today's knowledge, secure against quantum adversaries are McEliece and lattice-based schemes. Surveys of post-quantum cryptography are available.

There is also research into how existing cryptographic techniques have to be modified to be able to cope with quantum adversaries. For example, when trying to develop zero-knowledge proof systems that are secure against quantum adversaries, new techniques need to be used: In a classical setting, the analysis of a zero-knowledge proof system usually involves "rewinding", a technique that makes it necessary to copy the internal state of the adversary. In a quantum setting, copying a state is not always possible (no-cloning theorem); a variant of the rewinding technique has to be used.

References

Vorlage:Reflist de:Quantenkryptografie