Quantenkryptographie
# Quantenkryptographie

Quantenkryptographie ist die Verwendung quantenmechanischer Effekte (besonders bei Quantenkommunikation und Quantencomputern) als Bestandteil kryptographischer Verfahren oder zur Kryptoanalyse.

Die bekanntesten Beispiele der Quantenkryptographie sind der Quantenschlüsselaustausch und der (noch nicht praktikable) Shor-Algorithmus zum Faktorisieren großer Zahlen. Quantenkryptographie erlaubt das Entwickeln von Verfahren, die klassisch (d. h. ohne den Einsatz von Quanteneffekten) unmöglich sind. Zum Beispiel kann bei einem Quantenkanal ein Lauscher entdeckt werden, weil seine Messung die gesendeten Daten beeinflusst.

## Quantenschlüsselaustausch

Die am besten bekannte und kommerziell verfügbare Anwendung von Quantenkryptographie ist der Quantenschlüsselaustausch. In den 1970er Jahren schlug Stephen Wiesner eine auf Quanteneffekten basierende Informationsübertragung vor, konnte diesen Vorschlag jedoch erst 1983 veröffentlichen. Charles H. Bennett und Gilles Brassard stellten 1984 das erste Protokoll zum Quantenschlüsselaustausch vor (BB84). Ziel eines Schlüsselaustauschprotokolls ist es, dass sich zwei Parteien (üblicherweise Alice und Bob genannt) auf einen gemeinsamen geheimen Schlüssel einigen, ohne dass eine dritte Partei (Eve) Informationen über den Schlüssel erhält, selbst wenn sie den Kommunikationskanal abhört. Beim Quantenschlüsselaustausch wird das durch den Einsatz eines Quantenkanals erreicht, da Eve die über diesen Kanal laufenden Nachrichten nicht abhören kann, ohne sie zu verändern. Einen Schlüsselaustausch mit Quantenverschränkung führte Artur Ekert 1991 ein.

Die Sicherheit eines Quantenschlüsselaustauschprotokolls kann auch gegen unbeschränkte Angreifer bewiesen werden, was bei einem klassischen Schlüsselaustauschprotokoll unmöglich ist. Die einzigen Annahmen, die benötigt werden, sind die Gültigkeit der Gesetze der Quantenmechanik und eine Möglichkeit für Alice und Bob, sich gegenseitig zu authentifizieren, um einen Man-in-the-middle-Angriff auszuschließen. Zudem wird in den Sicherheitsbeweisen angenommen, dass die Kommunikationspartner nicht abgehört oder heimlich beobachtet werden und dass die verwendeten Geräte (z. B. Photodetektoren, Photonenquellen, Zufallsgeneratoren) wie spezifiziert funktionieren. Die zweite dieser Annahmen ist bei Verwendung von als "geräte-unabhängig" bezeichneten Verfahren (device-independent quantum cryptography) nicht notwendig.

Was die Sicherheitsbeweise am Ende liefern, ist eine Garantie der Form: „Wenn die Voraussetzungen dieses Beweises gelten, weiß der Gegner nur mit (sehr kleiner) Wahrscheinlichkeit $p$ mehr als $\epsilon$ über den vereinbarten Schlüssel.“ Die Größen $p,\epsilon$ hängen von im Rahmen des Protokolls und vor Verwendung des Schlüssels bestimmbaren Größen ab.

## Quanten-Commitmentverfahren

Die Entdeckung des Quantenschlüsselaustauschs weckte die Hoffnung, auch andere kryptographische Verfahren gegen unbeschränkte Angreifer sicher machen zu können. Ein grundlegendes Primitiv sind Commitment-Verfahren, die es einer Partei erlauben, sich gegenüber einer anderen Partei auf eine solche Weise auf einen Wert festzulegen, dass sie den Wert nicht mehr ändern kann, die andere Partei jedoch nichts über den Wert lernt, bis er aufgedeckt wird. Zusammen mit einem Quantenkanal kann man aus einem Quanten-Commitmentverfahren ein Primitiv namens Oblivious Transfer (OT) konstruieren, das gegen unbeschränkte Angreifer sicher ist. Oblivious Transfer ist ein vollständiges Primitiv, da es die sichere Implementierung beliebiger verteilter Berechnungen erlaubt (sichere Mehrparteienberechnung). (Die Ergebnisse von Crépeau und Kilian und Kilian alleine reichen noch nicht aus, um aus einem Quantencommitment und einem Quantenkanal allgemeine Protokolle für sichere Mehrparteienberechnung zu konstruieren, da die „Komponierbarkeit“ nicht gegeben ist, es ist also nicht sichergestellt, dass das gleichzeitige Verwenden zweier sicherer Primitive keine Sicherheitslücken erzeugt. Die Komponierbarkeit wurde jedoch später nachgewiesen.)

Erste Versuche, Quanten-Commitmentverfahren zu konstruieren waren fehlerhaft. Es konnte gezeigt werden, dass es unmöglich ist, Quanten-Commitmentverfahren zu konstruieren, die gegen unbeschränkte Angreifer sicher sind. Der Einsatz von Quantenkanälen erlaubt es jedoch, Commitmentverfahren unter wesentlich schwächeren Annahmen, als klassisch nötig sind, zu konstruieren.

## Bounded- und Noisy-Quantum-Storage-Modell

Eine Möglichkeit, Quantencommitment und Quanten-OT zu erhalten, die gegen Angreifer ohne Laufzeitbeschränkung sicher sind, besteht darin, den Speicherplatz des Angreifers zu beschränken. Im Bounded-Quantum-Storage-Modell (BQSM) darf der Angreifer zwar eine beliebige Menge an klassischer Information speichern, sein Quantenspeicher ist jedoch durch eine Konstante Q beschränkt.

Im BQSM lassen sich sichere Commitment- und OT-Protokolle konstruieren. Die zugrundeliegende Idee ist, dass die kommunizierenden Parteien mehr als Q Qubits austauschen. Da der Angreifer maximal Q davon speichern kann, muss er den Rest messen oder verwerfen. Das erlaubt das Umgehen des oben erwähnten Unmöglichkeitsresultats. Die ehrlichen Protokollteilnehmer müssen dabei, ähnlich wie beim Quantenschlüsselaustausch, keine Quanteninformationen speichern; im Prinzip können die Protokolle also mit der existierenden Technologie bereits realisiert werden. Die dabei übertragene Datenmenge ist ein konstantes Vielfaches der Schranke Q.

Der Vorteil des BQSM ist, dass die Annahme des beschränkten Quantenspeichers ziemlich realistisch ist. Mit heutiger Technologie ist bereits das hinreichend lange Speichern eines einzigen Qubits eine Herausforderung. Die genaue Bedeutung von „hinreichend lange“ hängt dabei vom Protokoll ab, durch Einfügen einer Pause kann der Zeitraum aber beliebig verlängert werden.

Eine Verallgemeinerung des BQSM ist das Noisy-Storage-Modell von Wehner, Schaffner und Terhal. In diesem Modell ist der Quantenspeicher des Angreifers nicht beschränkt, er wird aber als verrauschter Kanal (englisch noisy channel) modelliert, d. h., es wird angenommen, dass beim Speichern Bitfehler auftreten. Die Stärke des Rauschens ist dabei ein Parameter, für hinreichend starkes Rauschen können die gleichen Primitive realisiert werden wie im BQSM, das als Spezialfall angesehen werden kann.

Unter klassischen Bedingungen können ähnliche Ergebnisse erzielt werden wie im BQSM, wenn die Größe des klassischen Speichers als beschränkt angenommen wird. Die ehrlichen Protokollteilnehmer müssen dabei allerdings Daten in der Größenordnung der Quadratwurzel der Schranke speichern. Da bei den heutigen Speicherpreisen die Schranke für den Angreifer entsprechend hoch angesetzt werden muss, sind diese Protokolle nicht praktikabel.

## Positionsbasierte Quantenkryptographie

Positionsbasierte Kryptographie erlaubt es, den Aufenthaltsort einer Partei als Berechtigungsnachweis zu verwenden. Zum Beispiel kann eine Nachricht so verschlüsselt werden, dass sie nur gelesen werden kann, wenn sich der Empfänger an einem bestimmten Ort befindet. Bei der Positionsverifizierung möchte eine Partei beweisen, dass sie sich an einem bestimmten Ort aufhält. Dies ist mit klassischen Protokollen unmöglich, wenn alle verifizierenden Parteien unehrlich sind und zusammenarbeiten. Es kann also nur Verfahren geben, die gegen in irgendeiner Weise beschränkte Angreifer sicher sind.

Die ersten positionsbasierten Quantenverfahren wurden 2002 unter dem Namen Quantum Tagging untersucht, aber erst 2010 veröffentlicht. Nachdem 2010 noch weitere Protokolle vorgestellt wurden, konnte ein allgemeines Unmöglichkeitsresultat gezeigt werden: Wenn die Angreifer einen beliebig großen verschränkten Quantenzustand teilen, können sie immer vorgeben an einer bestimmten Position zu sein. Das schließt jedoch die Existenz von Protokollen in einem Bounded- oder Noisy-Quantum-Storage-Modell nicht aus.

## Post-Quanten-Kryptographie

Gegenwärtig können nur extrem eingeschränkte Quantencomputer konstruiert werden. Da es vorstellbar ist, dass in der Zukunft praktisch einsetzbare Quantencomputer gebaut werden können, ist es wichtig, kryptographische Verfahren zu untersuchen, die auch gegen Angreifer mit einem Quantencomputer sicher sind. Dieses Forschungsgebiet wird Post-Quanten-Kryptographie genannt.

