Post-Quanten-Kryptografie

Gitter

Ein Gitter ist vergleichbar mit einem Vektorraum.

In krypto­grafischen Anwendungen sind die Vektoren a_i Elemente von ℤ_q^m, also m-Tupel mit Komponenten aus ℤ_q, wobei q eine Primzahl oder eine Zweierpotenz ist. Die Vektoren werden als Spalten­vektoren geschrieben. Die n Basis­vektoren eines Gitters lassen sich als m×n-Matrix

A  =  [a₀ ... a_n-1]

schreiben.

Beispiel:  Ein Gitter L vom Rang 3 wird erzeugt von n = 3 Basis­vektoren a₀, a₁, a₂ der Dimension m = 5 mit Komponenten aus ℤ₁₇. Die entsprechende 5×3-Matrix A lautet

A  =

5 10 8 2 1 8 12 12 3 11 4 16 12 7 6

Einen beliebigen Punkt t in einem Gitter L stellen Sie als Kombination der Basis­vektoren a₀, ..., a_n-1 dar, indem Sie geeignete Koeffizienten s₀, ..., s_n-1  ∈  ℤ_q wählen:

s₀·a₀ +  ...  + s_n-1·a_n-1  =  t

In Matrix­schreibweise lautet die Darstellung

A · s  =  t

Hierbei bilden Sie die Matrix A aus den Basis­vektoren, den Vektor s aus den Koeffizienten s₀, ..., s_n-1 und den Vektor t aus den Koordinaten des Punkts t.

Beispiel:  Mit der Matrix A aus dem vorherigen Beispiel und Koeffizienten s₀ = -2, s₁ = 1, s₂ = 1 erhalten Sie beispiels­weise den folgenden Punkt t des Gitters. Beachten Sie, dass die Berechnungen modulo q = 17 durchgeführt werden, denn der zugrunde liegende Ring (bzw. hier Körper) ist ℤ₁₇.

A · s   =   5 10 8 2 1 8 12 12 3 11 4 16 12 7 6

·  -2 1 1

=     8 5 8 15 6

=   t

Wie finden Sie geeignete Koeffizienten s₀, ..., s_n-1, wenn Sie einen bestimmten Punkt t des Gitters als Kombination der Basis­vektoren a₀, ..., a_n-1 darstellen wollen? Dies läuft auf die Lösung eines linearen Gleichungs­systems hinaus. Angenommen, Sie kennen die Werte für s₀, ..., s_n-1 in obigem Beispiel nicht. Sie lösen dann beliebige 3 von den 5 Gleichungen mit den 3 Unbekannten s₀, s₁, s₂, standard­mäßig mit dem gaußschen Eliminations­verfahren.

Noise

Ein Gleichungs­system mit n Unbekannten zu lösen ist leicht, auch wenn n sehr groß ist. Schwer wird es dann, wenn Sie einen zusätzlichen Fehlervektor (engl.: error vector) e mit Komponenten e_i ∈ {-1, 0, 1} addieren, auch als Rauschen (engl.: noise) bezeichnet.

A · s  +  e  =  t

Für das Beispiel oben gilt dann: Je nach dem, welche 3 von den 5 Gleichungen mit 3 Unbekannten Sie lösen, erhalten Sie unterschiedliche Lösungen – insgesamt also keine konsistente Lösung des gesamten Gleichungs­systems. Dies liegt daran, dass der resultierende Vektor t kein Punkt des Gitters ist. Er liegt aber nahe an einem Punkt des Gitters – nahe an welchem, ist schwer zu entscheiden (closest vector problem – CVP).

Auf diese Weise erhalten Sie das sogenannte Learning-With-Errors-Problem (LWE):

Der Begriff "Learning", also "Lernen", entstammt dem Bereich des maschinellen Lernens. Dort geht es vielfach darum, aus Beispielen zu lernen, also eine gemeinsame Struktur daraus abzuleiten. Beim LWE-Problem besteht diese Struktur aus den ursprüng­lichen Gleichungen, und die Beispiele sind die durch den Fehlervektor e verrauschten ursprüng­lichen Gleichungen.

Literatur

Die hier gewählte Darstellung folgt dem Buch

[PPG 24]   C. Paar, J. Pelzl, T. Güneysu: Understanding Crytography. 2. Auflage, Springer (2024)