Quantenkryptographie

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

Hauptartikel: Quantenschlüsselaustausch

Die am besten bekannte und einzige kommerziell verfügbare[1][2] 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.[3] Charles H. Bennett und Gilles Brassard stellten 1984 das erste Protokoll zum Quantenschlüsselaustausch vor.[4] 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.

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.

Quanten-Commitmentverfahren[Bearbeiten]

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.[5] Oblivious Transfer ist ein vollständiges Primitiv, da es die sichere Implementierung beliebiger verteilter Berechnungen erlaubt (sichere Mehrparteienberechnung).[6] (Die Ergebnisse von Crépeau und Kilian[5] und Kilian[6] 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[7] waren fehlerhaft. Es konnte gezeigt werden, dass es unmöglich ist, Quanten-Commitmentverfahren zu konstruieren, die gegen unbeschränkte Angreifer sicher sind.[8] 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[Bearbeiten]

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.[9] 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.[8] 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.[10] 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.[11]

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

Positionsbasierte Quantenkryptographie[Bearbeiten]

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.[14] 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.[15] Nachdem 2010 noch weitere Protokolle vorgestellt wurden,[16][17] konnte ein allgemeines Unmöglichkeitsresultat gezeigt werden:[18] 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-Quantum-Kryptographie[Bearbeiten]

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-Quantum-Kryptographie genannt.

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Cerberis Encryption Solution - Layer 2 Encryption with Quantum Key Distribution. id Quantique. Abgerufen am 12. April 2013.
  2. Products. MagiQ. Abgerufen am 12. Februar 2013.
  3. Stephen Wiesner: Conjugate coding. In: ACM (Hrsg.): SIGACT News. 15, Nr. 1, New York, NY, USA, 1983, S. 78–88. doi:10.1145/1008908.1008920. Manuscript written ca.~1970
  4. Charles H. Bennett, Gilles Brassard: Quantum cryptography: Public-key distribution and coin tossing. In: Proceedings of IEEE International Conference on Computers, Systems and Signal Processing 1984 . IEEE Computer Society, 1984, S. 175–179.
  5. a b Claude Crépeau, Kilian Joe: Achieving Oblivious Transfer Using Weakened Security Assumptions (Extended Abstract). In: FOCS 1988. IEEE, 1988, S. 42–52.
  6. a b Kilian Joe: Founding cryptography on oblivious transfer. In: STOC 1988. ACM, 1988, S. 20–31.
  7. Brassard Gilles, Claude Crépeau, Jozsa Richard, Denis Langlois: A Quantum Bit Commitment Scheme Provably Unbreakable by both Parties. In: FOCS 1993. IEEE, 1993, S. 362–371.
  8. a b Dominic Mayers: Unconditionally Secure Quantum Bit Commitment is Impossible. In: APS (Hrsg.): Physical Review Letters. 78, Nr. 17, 1997, S. 3414–3417. arXiv:quant-ph/9605044. Bibcode: 1997PhRvL..78.3414M. doi:10.1103/PhysRevLett.78.3414. Preprint at arXiv:quant-ph/9605044v2
  9. Ivan Damgård, Serge Fehr, Louis Salvail, Christian Schaffner: Cryptography In the Bounded Quantum-Storage Model. In: FOCS 2005. IEEE, 2005, S. 449–458. A full version is available at arXiv:quant-ph/0508222.
  10. Stephanie Wehner, Christian Schaffner, Barbara M. Terhal: Cryptography from Noisy Storage. In: APS (Hrsg.): Physical Review Letters. 100, Nr. 22, 2008, S. 220502. arXiv:0711.2895. Bibcode: 2008PhRvL.100v0502W. doi:10.1103/PhysRevLett.100.220502. PMID 18643410. A full version is available at arXiv:0711.2895.
  11. Robert Koenig, Stephanie Wehner, Juerg Wullschleger: Unconditional security from noisy quantum storage. Abgerufen am 18. April 2013.
  12. Christian Cachin, Claude Crépeau, Julien Marcil: Oblivious Transfer with a Memory-Bounded Receiver. In: FOCS 1998. IEEE, 1998, S. 493–502.
  13. Stefan Dziembowski, Maurer Ueli: On Generating the Initial Key in the Bounded-Storage Model. In: Eurocrypt 2004. Springer, 2004, S. 126–137.
  14. Nishanth Chandran, Moriarty, Ryan; Goyal, Vipul; Ostrovsky, Rafail: Position-Based Cryptography 2009. A full version is available at IACR eprint:2009/364.
  15. Adrian Kent, Bill Munro, Tim Spiller: Quantum Tagging with Cryptographically Secure Tags. 2010. Abgerufen am 18. April 2013.
  16. Hoi-Kwan Lau, Hoi-Kwong Lo: Insecurity of position-based quantum-cryptography protocols against entanglement attacks. In: APS (Hrsg.): Physical Review A. 83, 2010, S. 012322. arXiv:1009.2256. doi:10.1103/PhysRevA.83.012322. A full version is available at arXiv:1009.2256.
  17. Robert A. Malaney: Location-dependent communications using quantum entanglement. In: Physical Review A. 81, 2010, S. 042319. doi:10.1103/PhysRevA.81.042319.
  18. Harry Buhrman, Chandran, Nishanth; Fehr, Serge; Gelles, Ran; Goyal, Vipul; Ostrovsky, Rafail; Schaffner, Christian: arXiv:1009.2490 Position-Based Quantum Cryptography: Impossibility and Constructions. 2010. Abgerufen am 18. April 2013.