Grover-Algorithmus

Bitte beachten Sie die Abgrenzungen zwischen Quantenkryptologie, Quantenkryptografie, Quantenkryptoanalyse und Post-Quanten-Kryptografie, wie sie auf der Index-Seite nachzulesen ist.

Dieser Beitrag gehört zum Thema Quantenkryptoanalyse. Quantenkryptoanalyse ist das, was man gemeinhin unter Kryptoanalyse, also das Knacken von Chiffren, versteht, nur halt mit Quantencomputern statt mit herkömmlichen Computern.

Sie sollten vorher den Beitrag Quantencomputer und wie sie funktionieren und die Einleitung zur Quantenkryptoanalyse gelesen haben, um sich einen Überblick zu verschaffen.

Der Grover-Algorithmus ist nach Lov Grover benannt, der diesen 1996 in seiner Arbeit A fast quantum mechanical algorithm for database search ⁽¹⁾ veröffentlichte. Der Algorithmus bezieht sich auf die Suche nach einem Eintrag in einer unsortierten Datenbank und kann wie folgt zusammengefasst werden:

Stellen Sie sich ein Telefonbuch mit N Namen vor, die in völlig zufälliger Reihenfolge angeordnet sind. Um die Telefonnummer einer Person mit einer Wahrscheinlichkeit von 50 % zu finden, muss jeder klassische Algorithmus (ob deterministisch oder probabilistisch) [im Mittel] mindestens N/2 Namen untersuchen. Quantenmechanische Systeme können sich in einer Überlagerung von Zuständen befinden und gleichzeitig mehrere Namen untersuchen. Durch die richtige Einstellung der Phasen der verschiedenen Operationen verstärken sich erfolgreiche Berechnungen gegenseitig, während andere zufällig ineinandergreifen. Das Ergebnis ist, dass die gewünschte Telefonnummer in nur O(Wurzel(N)) Schritten ermittelt werden kann. Der Algorithmus liegt innerhalb eines kleinen konstanten Faktors des schnellstmöglichen quantenmechanischen Algorithmus.

Im Ergebnis heißt das, dass ein Quantencomputer eine Suche in einer unsortierten Liste mit N Einträgen in O (√ N) Schritten und mit O (log N) Speicherbedarf gefunden werden kann ⁽²⁾. Ein herkömmlicher Computer braucht hingegen im Mittel N/2 Schritte. Der Quantenalgorithmus ist damit wesentlich schneller und erzielt einen quadratischen Geschwindigkeitsvorteil.

Wie die meisten Quantenalgorithmen ist der Grover-Algorithmus ein probabilistischer Algorithmus, d. h., er gibt die korrekte Antwort mit hoher Wahrscheinlichkeit, wobei die Wahrscheinlichkeit einer fehlerhaften Antwort durch wiederholte Ausführung des Algorithmus verkleinert werden kann.

Die Funktionsweise des Grover-Algorithmus ist die Folgende:

• Superposition herstellen: Zunächst wird ein Quantensystem so vorbereitet, dass es alle möglichen Einträge gleichzeitig repräsentiert. Das bedeutet, alle Positionen in der Liste werden "auf einmal" in einem Zustand (Superposition) abgebildet.
  
  
• Markierung des gesuchten Eintrags (Orakel): Ein spezielles Programmteil, das "Orakel", erkennt den gesuchten Eintrag und ändert nur dessen Zustand - genauer gesagt, es dreht dessen Phase um (eine Art "Negativzeichen").
  
  
• Amplitude verstärken: Anschließend wird ein weiterer Schritt (manchmal "Diffusionsoperator" genannt) ausgeführt, der die Wahrscheinlichkeit (Amplitude) des gesuchten Eintrags verstärkt und die der anderen Einträge verringert.
  
  
• Wiederholung: Diese beiden Schritte - Phase umkehren und Amplituden verstärken - werden mehrmals wiederholt. Dadurch wird der gesuchte Eintrag immer wahrscheinlicher. Die höchste Wahrscheinlich wird bei ca. √ N Schritten erreicht sein. Danach fällt die Wahrscheinlichkeit wieder.
  
  
• Messung: Am Ende misst man das System. Aufgrund der verstärkten Amplitude des gesuchten Eintrags ist die Wahrscheinlichkeit sehr hoch, dass man genau diesen Eintrag erhält.
  
  

Zusammenfassend kann man sagen: Der Grover-Algorithmus nutzt die besonderen Eigenschaften der Quantenmechanik - insbesondere Superposition und Interferenz - um gezielt den richtigen Eintrag in einer unsortierten Liste hervorzuheben und somit viel schneller zu finden, als es mit klassischen Methoden möglich wäre.

Gleichzeitig begrenzt er den Geschwindigkeitsvorteil auf das Quadrat gegenüber herkömmlichen Computern. Im Umkehrschluss heißt dass, dass Verschlüsselungsverfahren, für die es sonst keine speziellen Quantenalgorithmen (wie z. B. den Shor-Algorithmus) gibt, in der Wurzel der Zeit geknackt werden können.

Bei symmetrischen Verschlüsselungsverfahren wie AES kann man das dadurch ausgleichen, indem man die benutze Schlüssellänge verdoppelt, da der Rechenaufwand bei Verdoppelung exponentiell ansteigt. In der Praxis heißt das: ein AES-256 Chiffrat per Brute Force zu knacken dauert mit Quantencomputern und dem Grover-Algorithmus so lange wie ein AES-128-Chiffrat mit herkömmlichen Computer zu knacken (die Wurzel aus 2²⁵⁶ ist 2¹²⁸).

Quellen, Literaturverweise und weiterführende Links