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

→ Hauptartikel: 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 mehr als über den vereinbarten Schlüssel.“ Die Größen 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

→ Hauptartikel: 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.

Weblinks

Wiktionary: Quantenkryptografie – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

• golem.de/specials/quantenkryptographie – Artikel zum Thema Quantenkryptografie auf Golem.de

Einzelnachweise

1. 5 Quantum Cryptography and Quantum Encryption Companies. nanalyze.com, abgerufen am 16. Februar 2018 (englisch). 
2. Stephen Wiesner: Conjugate coding. In: SIGACT News. 15. Jahrgang, Nr. 1. ACM, 1983, ISSN 0163-5700, S. 78–88, doi:10.1145/1008908.1008920 (englisch).  Manuscript written ca.~1970
3. Charles H. Bennett, Gilles Brassard, Brassard: Quantum cryptography: Public-key distribution and coin tossing. IEEE International Conference on Computers. In: Systems and Signal Processing 1984. IEEE Computer Society, 1984, S. 175–179 (englisch, @1@2Vorlage:Toter Link/researcher.watson.ibm.comresearcher.watson.ibm.com (Seite nicht mehr abrufbar. Suche in Webarchiven.)). 
   (reprinted in: Quantum cryptography: Public-key distribution and coin tossing. In: Theoretical Computer Science. 560. Jahrgang, P1, 2014, S. 7–11, doi:10.1016/j.tcs.2014.05.025 (englisch, sciencedirect.com [PDF]). )
4. Umesh Vazirani, Thomas Vidick: Fully Device-Independent Quantum Key Distribution. In: Phys. Rev. Lett. Band 113, 2014, S. 140501, doi:10.1103/PhysRevLett.113.140501, arxiv:1210.1810. 
5. Valerio Scarani, Helle Bechmann-Pasquinucci, Nicolas J. Cerf, Miloslav Dusek, Norbert Lutkenhaus, Momtchil Peev: The Security of Practical Quantum Key Distribution. In: Rev. Mod. Phys. Band 81, 2009, S. 1301, doi:10.1103/RevModPhys.81.1301, arxiv:0802.4155. 
6. Claude Crépeau, Kilian Joe, Joe: Achieving Oblivious Transfer Using Weakened Security Assumptions (Extended Abstract). FOCS 1988. IEEE, 1988, S. 42–52 (englisch). 
7. Kilian Joe: Founding cryptography on oblivious transfer. STOC 1988. ACM, 1988, S. 20–31, doi:10.1145/62212.62215 (englisch, @1@2Vorlage:Toter Link/dl.acm.orgdl.acm.org (Seite nicht mehr abrufbar. Suche in Webarchiven.) [PDF]). 
8. Brassard Gilles, Claude Crépeau, Jozsa Crépeau, Denis Langlois: A Quantum Bit Commitment Scheme Provably Unbreakable by both Parties. FOCS 1993. IEEE, 1993, S. 362–371, doi:10.1109/SFCS.1993.366851 (englisch, ieee.org). 
9. Dominic Mayers: Unconditionally Secure Quantum Bit Commitment is Impossible. In: Physical Review Letters. 78. Jahrgang, Nr. 17. APS, 1997, S. 3414–3417, doi:10.1103/PhysRevLett.78.3414, arxiv:quant-ph/9605044, bibcode:1997PhRvL..78.3414M (englisch). 
10. Ivan Damgård, Serge Fehr, Louis Fehr, Christian Schaffner: Cryptography In the Bounded Quantum-Storage Model. FOCS 2005. IEEE, 2005, S. 449–458 (englisch).  arxiv:quant-ph/0508222.
11. Stephanie Wehner, Christian Schaffner, Barbara M. Terhal: Cryptography from Noisy Storage. In: Physical Review Letters. 100. Jahrgang, Nr. 22. APS, 2008, S. 220502, doi:10.1103/PhysRevLett.100.220502, PMID 18643410, arxiv:0711.2895, bibcode:2008PhRvL.100v0502W (englisch, aps.org). 
12. Robert Koenig, Stephanie Wehner, Juerg Wullschleger: Unconditional security from noisy quantum storage. In: IEEE Trans. Inf. Th. 58. Jahrgang, Nr. 3, S. 1962–1984, arxiv:0906.1030 (englisch). 
13. Christian Cachin, Claude Crépeau, Julien Crépeau: Oblivious Transfer with a Memory-Bounded Receiver. FOCS 1998. IEEE, 1998, S. 493–502, doi:10.1109/SFCS.1998.743500 (englisch, ethz.ch [PDF]). 
14. Stefan Dziembowski, Maurer Ueli, Ueli: On Generating the Initial Key in the Bounded-Storage Model. Eurocrypt 2004. Band 3027, LNCS. Springer, 2004, S. 126–137 (englisch, ethz.ch [PDF]). 
15. Nishanth Chandran, Moriarty, Ryan; Goyal, Vipul; Ostrovsky, Rafail: Position-Based Cryptography. 2009 (englisch, A full version is available at IACR eprint:2009/364.). 
16. Adrian Kent, Bill Munro, Tim Spiller: Quantum Tagging with Cryptographically Secure Tags. In: Phys. Rev. A. 84. Jahrgang, 2011, S. 012326, arxiv:1008.2147 (englisch). 
17. Hoi-Kwan Lau, Hoi-Kwong Lo: Insecurity of position-based quantum-cryptography protocols against entanglement attacks. In: Physical Review A. 83. Jahrgang. APS, 2010, S. 012322, doi:10.1103/PhysRevA.83.012322, arxiv:1009.2256 (englisch, aps.org). 
18. Robert A. Malaney: Location-dependent communications using quantum entanglement. In: Physical Review A. 81. Jahrgang, 2010, S. 042319, doi:10.1103/PhysRevA.81.042319 (englisch). 
19. Harry Buhrman, Chandran, Nishanth; Fehr, Serge; Gelles, Ran; Goyal, Vipul; Ostrovsky, Rafail; Schaffner, Christian: Position-Based Quantum Cryptography: Impossibility and Constructions. In: SIAM J. Comput. 43. Jahrgang, Nr. 1, S. 150–178, doi:10.1137/130913687, arxiv:1009.2490 (englisch).