Gitter und Popcorn

von Dario Stein

Gitter und Popcorn

Auf dem ActiveVB-Workshop in Essen habe ich in einem Vortrag angesprochen, wie man sogenannte Gitter zu Verschlüsselungszwecken einsetzen kann.

Ein Gitter ist eine regelmäßige Menge von Punkten (Vektoren) im Raum, die von endlich vielen Basisvektoren $Latex: v_1, \ldots v_n$ aufgespannt wird.

Abbildung 1: Gitterbasis

Das heißt, man bildet von diesen Basisvektoren beliebige ganzzahlige Kombinationen wie

$Latex: 2v_1, \quad v_1 + v_2, \quad -3v_1 - v_2 +9v_{42},\ldots$ Man kann also Gitterpunkte addieren und subtrahieren. Verschiedene Basen können ein- und dasselbe Gitter erzeugen, wenn sie sich gegenseitig ineinander ausdrücken lassen. Zum Beispiel erzeugen $Latex: v_1 = \begin{pmatrix}1\\0\end{pmatrix},v_2 = \begin{pmatrix}0\\1\end{pmatrix}$ das ganz normale ganzzahlige Einheitsgitter, also die Kreuzungspunkte des Karopapiers im Schulheft. Die Basis $Latex: w_1 = \begin{pmatrix}3\\1\end{pmatrix},w_2 = \begin{pmatrix}5\\2\end{pmatrix}$ liefert aber genau dasselbe Gitter, denn man erhält $Latex: 2w_1 - w_2 = \begin{pmatrix}1\\0\end{pmatrix}, \quad -5w_1 + 3w_2 = \begin{pmatrix}0\\1\end{pmatrix}.$

Abbildung 2: Einheitsgitter mit verschiedenen Basen

Schlimmmer noch, auch

$Latex: z_1 = \begin{pmatrix}4831\\220\end{pmatrix},z_2 = \begin{pmatrix}129361\\5891\end{pmatrix}$ erzeugt das Einheitsgitter. Erstaunlich: Man sieht dem Gitter nun gar nicht mehr an, dass es "kleine Punkte" wie $Latex: (0|1)$ enthält. Wie sollte man es dann zum Beispiel in der Praxis zeichnen oder untersuchen? Das wirft folgende Frage auf:

Shortest Vector Problem (SVP) Gegeben ist eine Basis eines Gitters. Was ist der kürzeste Vektor außer der Null (short vector), der mit der Basis aufgespannt werden kann?

Dürfte man beliebige reelle Koeffizienten vor die Vektoren multiplizieren, wäre das Problem ein einfaches lineares Gleichungssystem. Die Schwierigkeit liegt darin, dass wir nur ganze Zahlen benutzen dürfen. Tatsächlich wird die Lösung dieses Problems mit zunehmender Dimension und Länge der Basis so schwierig, dass einige Verschlüsselungssysteme darauf ihre Sicherheit bauen. Die Lösung des SVP hat Bezüge zu kombinatorischen Problemen wie dem Rucksackproblem!

Eindimensionales SVP

Ich lade hier zu einer kleinen Spielerei ein. Wir wollen sehen, was das SVP so schwierig machen könnte. Man könnte denken, dass es sich um ein recht stabiles Problem handelt: Wir geben einem Rechenverfahren $Latex: n$ Basisvektoren ein und erhalten einen short vector als Ausgabe. Wenn sich die Basis ein wenig ändert, ändert sich auch der short vector nur wenig. Das geht zum Beispiel mit der Basis $Latex: v_1, v_2$ vom Einheitsgitter, da sind die Basisvektoren nämlich selbst short vectors. Allgemein klappt das aber nicht! Die Basis $Latex: z_1, z_2$ oben besteht aus riesigen aber fast parallelen Vektoren, kleine Änderungen an der Basis ändern auch den short vector empfindlich.

Wir untersuchen das in dem Extremfall, dass die Vektoren tatsächlich parallel werden würden, dann haben wir nur noch ein eindimensionales Problem.

Gegeben sei eine Zahl $Latex: a>0$ . Sei $Latex: \Lambda_a$ die Menge, die von $Latex: a$ und der Zahl $Latex: 1$ aufgespannt wird, also $Latex: \Lambda_a = \{ k + \ell\cdot a | k, \ell = \ldots, -1, 0, 1, 2 \ldots \}.$

Wie sieht $Latex: \Lambda_a$ aus und was wäre dort ein short vector? Gucken wir uns mal ein paar Beispiele an:

Für $Latex: a = 1/3$ bekommen wir regelmäßige Punkte bei

$Latex: -1/3,\, 0,\, 1/3,\, 2/3,\, 1,\, 4/3,\, \ldots,$ das heißt, $Latex: a$ ist selbst short vector. Wie sieht die Situation für $Latex: a = 2/3$ aus? Hier ist $Latex: a$ kein short vector. Wir kriegen natürlich die Punkte $Latex: -2/3, 2/3, 4/3$ , usw., aber auch die Kombination $Latex: -2/3 + 1 = 1/3$ ist ein Gitterpunkt und somit auch alle Vielfachen von $Latex: 1/3$ . Tatsächlich ist wieder $Latex: \frac 1 3$ short vector, wir erhalten dasselbe Gitter wie oben.

Abbildung 3: Eindimensionales Gitter mit a=1/3

Wir veranschaulichen uns die Situation in einem kleinen Programm, indem wir mit dem Mauszeiger den Wert für $Latex: a$ vorgeben können.

Const s = 100

Private Sub Form_Load()
    AutoRedraw = True
    BackColor = vbWhite

    Scale (-0.1, 0.5)-(1.1, -0.5)

    Line (-0.1, 0)-(1.1, 0)
End Sub

Private Sub Form_MouseMove(Button As Integer, Shift As Integer, X As Single, Y As Single)
    Cls

    Line (-0.1, 0)-(1.1, 0)

    Caption = CStr(X)

    DrawWidth = 3
    For i = -s To s
        For j = -s To s
            PSet (i + j * X, 0)
        Next
    Next
    DrawWidth = 1
End Sub

Gucken wir uns die Situation für etwas veränderten Parameter $Latex: a=0.3$ an:

Abbildung 4: Eindimensionales Gitter mit a=0.3

Erstaunlich, aus drei Gitterpunkten in $Latex: [0,1)$ sind schon zehn geworden. Für den Wert $Latex: a=0.3015209$ erhalten wir stattdessen folgendes Bild: Fast der ganze Zahlenstrahl ist gefüllt!

Abbildung 5: Eindimensionales Gitter mit a=0.3015209

Rationale und irrationale Zahlen

Wie ist das möglich?

Wir haben festgestellt, dass sich für $Latex: a = 2/3$ Punkte im Abstand von $Latex: 1/3$ ergaben. Für $Latex: 0.3=3/10$ erhalten wir Punkte im Abstand von $Latex: 1/10$ . Mit etwas Überlegung kann man zeigen: Ist $Latex: a = p/q$ eine Bruchzahl mit gekürztem Zähler und Nenner, so ist tatsächlich stets $Latex: 1/q$ der short vector im Gitter. Man bildet ein geeignetes Vielfaches und zieht danach eine ganze Zahl ab, so dass man den Zähler auf $Latex: 1$ bekommt.

Und $Latex: 0.3015209$ ? Das ist als Bruchzahl $Latex: 3015209/10000000$ , also erhalten wir Punkte im Abstand von Zehnmillionsteln! Wenn das mal keine Abweichung ist.

Schlimmer noch? Was passiert, wenn sich $Latex: a$ überhaupt nicht als Bruchzahl darstellen lässt, also irrational ist, wie $Latex: \sqrt 2$ oder $Latex: \pi$ ? Dann kann es keinen short vector geben, die Abstände der Gitterpunkte werden stattdessen immer kleiner und kommen an jede Zahl beliebig nahe heran. Man könnte sagen, dass $Latex: 0$ der Gitterweite am nächsten kommt.

Die Funktion, die diese Weite von $Latex: \Lambda_a$ in Abhängigkeit von $Latex: a$ angibt, lautet also

$Latex: SV(a) = \begin{cases} 1/q, &a = p/q \text{ als gekuerzter Bruch } \\ 0, &a \text{ irrational }\end{cases}$

Die Popcorn-Funktion

Diese Funktion sieht auf den ersten Blick nicht auffällig aus, aber wir haben schon gesehen, wie extrem sie auf kleinste Änderungen von $Latex: a$ reagiert. Sie ist das absolute Gegenteil von stetig und es geht beliebig schlimm: Ein Beispiel: Für $Latex: a=1/2$ ist $Latex: SV(a) = 1/2$ . Die Zahl $Latex: b=499/1000$ unterscheidet sich von $Latex: a$ nur um ein Tausendstel, aber $Latex: SV(b) = 1/1000$ , was für ein Unterschied zu $Latex: SV(a)$ ! Dieses Beispiel kann man beliebig fortsetzen. Es gibt sogar in jedem noch so kleinen Abstand um $Latex: 1/2$ irrationale Zahlen $Latex: b$ mit $Latex: SV(b) = 0$ . Eine winzige Störung an der Basis $Latex: 1, a$ ändert also alles.

Die Funktion $Latex: SV$ ist die thomaesche Funktion , auf der Wikipedia-Seite finden wir auch ihren Graph gezeichnet. Der Gestalt des Graphs nach wird sie gemeinhin als Popcorn-Funktion bezeichnet.

Abbildung 6: Popcorn-Funktion

Wir haben gesehen, dass die Bestimmung von short vectors eine komplexe, nicht stetige sondern fraktalhafte Struktur hat.

Anmerkungen

Die Popcornfunktion ist ein tolles Gegenbeispiel in einer Analysisvorlesung. Sie hat die überraschende Eigenschaft, dass sie an jeder rationalen Stelle unstetig ist (das Argument haben wir oben gesehen). Noch interessanter ist jedoch, dass sie an jeder irrationalen Stelle stetig ist.
In der Definition von Gitter wird ein Fall wie $Latex: \Lambda_\pi$ , der die gesamte Zahlengerade füllt, normalerweise explizit ausgeschlossen. Man möchte, dass die Gitterpunkte wirklich getrennt liegen, und fordert daher linear unabhängige Basisvektoren. Wir haben gezeigt: $Latex: \Lambda_a$ ist genau dann tatsächlich ein Gitter, wenn $Latex: a$ rational ist, und zwar mit Basis $Latex: SV(a)$ .
Es gibt "gute" und "schlechte" Basen für Gitter, in guten Basen lässt sich das SVP leicht lösen und hängt stabil von der Basis ab. Die Aufgabe, eine beliebige Gitterbasis in eine gute zu transformieren, heißt Gitterreduktion (lattice reduction). Für 2D-Gitter (und in kleinen Dimensionen) gibt es gute Verfahren, welche aber in hohen Dimensionen scheitern, was die Sicherheit von gitterbasierten Kryptosystemen ausmacht.

Ihre Meinung

Falls Sie Fragen zu diesem Artikel haben oder Ihre Erfahrung mit anderen Nutzern austauschen möchten, dann teilen Sie uns diese bitte in einem der unten vorhandenen Themen oder über einen neuen Beitrag mit. Hierzu können sie einfach einen Beitrag in einem zum Thema passenden Forum anlegen, welcher automatisch mit dieser Seite verknüpft wird.