Wie funktioniert gitterbasierte Kryptographie und warum können Quantencomputer sie nicht knacken?
Um die Funktionsweise der gitterbasierten Kryptographie zu verstehen, müssen wir uns von der klassischen Zahlentheorie (wie Primfaktorzerlegung) verabschieden und in die Geometrie eintauchen.
Ein mathematisches Gitter (Lattice) ist im Grunde ein unendlich ausgedehntes Raster aus Punkten. In einem zweidimensionalen Raum (wie einem Blatt Papier) können Sie sich das wie das Muster auf kariertem Papier oder die Kreuzungspunkte eines Maschendrahtzauns vorstellen. Diese Punkte werden durch sogenannte Basisvektoren aufgespannt – das sind Pfeile, die vom Nullpunkt (Ursprung) zu bestimmten Punkten zeigen. Durch die Addition und Subtraktion dieser Basisvektoren kann man jeden einzelnen Punkt im gesamten Gitter erreichen.
Das Herzstück: Das Shortest Vector Problem (SVP)
Das fundamentale Rätsel, auf dem die Sicherheit der gitterbasierten Kryptographie beruht, ist das Shortest Vector Problem (SVP). Die Aufgabe klingt trügerisch einfach: Finde den Gitterpunkt, der dem Nullpunkt (Ursprung) am nächsten liegt. Anders ausgedrückt: Finde den kürzesten Vektor, der nicht die Länge null hat.
Probieren Sie es im folgenden Simulator für den zweidimensionalen Raum selbst aus: In zwei oder drei Dimensionen kann unser Auge (oder ein normaler Computer) dieses Problem meist sofort lösen. Der Trick der Kryptographie liegt jedoch in der Dimensionierung.
Der Dimensions-Trick („Gute“ vs. „Schlechte“ Basis)
Moderne Post-Quanten-Kryptographie nutzt Gitter, die nicht 2D oder 3D sind, sondern in einem Raum mit 500 bis 1000 Dimensionen existieren.
Zudem gibt es für jedes Gitter unendlich viele verschiedene Basisvektoren, die dieselben Punkte aufspannen:
- Die „gute“ Basis (Der private Schlüssel): Das sind Vektoren, die sehr kurz sind und fast im 90-Grad-Winkel zueinander stehen. Wenn Sie diese Basis kennen, ist es trivial, den kürzesten Vektor zu finden oder Entschlüsselungen vorzunehmen.
- Die „schlechte“ Basis (Der öffentliche Schlüssel): Das sind Vektoren, die extrem lang sind, wild kreuz und quer zeigen und fast parallel verlaufen.
Wenn Bob Alice eine verschlüsselte Nachricht senden will, nutzt er die „schlechte“ Basis (den öffentlichen Schlüssel), um die Nachricht als einen Punkt in diesem 1000-dimensionalen Gitter zu verbergen, der leicht neben einem echten Gitterpunkt liegt.
Um die Nachricht zu entschlüsseln, muss man herausfinden, zu welchem echten Gitterpunkt dieser Punkt gehört – das sogenannte Closest Vector Problem (CVP), welches direkt mit dem SVP verwandt ist.
Wer nur die lange, extrem verwirrende „schlechte“ Basis kennt, verläuft sich in den hunderten Dimensionen. Der Rechenaufwand wächst mit jeder Dimension so gigantisch an, dass selbst Supercomputer nach Milliarden Jahren keine Lösung finden. Alice hingegen besitzt die „gute“ Basis (ihren privaten Schlüssel) und kann das geometrische Chaos sofort auflösen.
Warum Quantencomputer hier scheitern
Warum ist nun gerade dieses Problem sicher vor Quantencomputern, während RSA (Primfaktorzerlegung) es nicht ist?
Das liegt an der grundlegenden Arbeitsweise des Shor-Algorithmus, der RSA bedroht. Dieser Algorithmus ist ein Meister darin, versteckte Periodizitäten (sich wiederholende Muster in Kreisläufen) zu finden. Primfaktorzerlegung lässt sich mathematisch in ein solches periodisches Problem übersetzen. Der Quantencomputer nutzt Überlagerung (Superposition), um alle Perioden gleichzeitig zu betrachten, und Interferenz, um die falsche Perioden auszulöschen, wodurch die richtige Lösung extrem schnell „übrig bleibt“.
Das Shortest Vector Problem hat jedoch keine solche zyklische, periodische Struktur. Es ist ein rein geometrisches, räumliches Optimierungsproblem ohne das spezifische mathematische Muster, das Quantencomputer für ihre exponentielle Beschleunigung benötigen.
Bisher hat kein Mathematiker und kein Kryptograph der Welt einen Quantenalgorithmus gefunden, der das Finden des kürzesten Vektors in einem hochdimensionalen Gitter signifikant beschleunigt. Ein Quantencomputer müsste bei diesem Problem (nach heutigem Stand der Wissenschaft) ähnlich mühsam vorgehen wie ein klassischer Computer, wodurch die gitterbasierte Kryptographie ihre Sicherheit behält.
