Die Community zu .NET und Classic VB.
Menü

Gitter und Popcorn

 von 

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.