Post-Quanten-Kryptografie
Gitter-basierte Kryptografie
Gitter
Ein Gitter ist vergleichbar mit einem Vektorraum.
Definition:
Ein Gitter L (engl.: lattice) besteht aus linear unabhängigen Vektoren a0, ..., an-1 und allen Kombinationen (= ganzzahligen Linearkombinationen) dieser Vektoren
L = { z0·a0 + ... + zn-1·an-1 | zi ∈ ℤ }
Die Vektoren a0, ..., an-1 sind Elemente eines m-dimensionalen Vektorraums, sie bilden eine Basis des Gitters L, ihre Anzahl n wird als Rang des Gitters L bezeichnet.
Beispiel: Die Vektoren a0 = (1,2) und a1 = (3,1) und alle Kombinationen dieser beiden Vektoren bilden ein Gitter L. Eine Kombination der beiden Vektoren a0 und a1 ist zum Beispiel der Vektor
t = 3·(1,2) + (-1)·(3,1) = (3,6) – (3,1) = (0,5)
In diesem Beispiel ist m = n = 2.
Das folgende Bild 1 zeigt einen Ausschnitt dieses Gitters. Es ist eingebettet in den Raum ℤ2, hier als Karopapier dargestellt. Die Vektoren des Gitters L sind als dicke Punkte dargestellt. Der Vektor t ist rot dargestellt.
Bild 1: Gitter mit Basisvektoren (1,2) und (3,1)
In kryptografischen Anwendungen sind die Vektoren ai Elemente von ℤqm, also m-Tupel mit Komponenten aus ℤq, wobei q eine Primzahl oder eine Zweierpotenz ist. Die Vektoren werden als Spaltenvektoren geschrieben. Die n Basisvektoren eines Gitters lassen sich als m×n-Matrix
A = [a0 ... an-1]
schreiben.
Beispiel: Ein Gitter L vom Rang 3 wird erzeugt von n = 3 Basisvektoren a0, a1, a2 der Dimension m = 5 mit Komponenten aus ℤ17. Die entsprechende 5×3-Matrix A lautet
| A = |  |
|  |
Einen beliebigen Punkt t in einem Gitter L stellen Sie als Kombination der Basisvektoren a0, ..., an-1 dar, indem Sie geeignete Koeffizienten s0, ..., sn-1 ∈ ℤq wählen:
s0·a0 + ... + sn-1·an-1 = t
In Matrixschreibweise lautet die Darstellung
A · s = t
Hierbei bilden Sie die Matrix A aus den Basisvektoren, den Vektor s aus den Koeffizienten s0, ..., sn-1 und den Vektor t aus den Koordinaten des Punkts t.
Beispiel: Mit der Matrix A aus dem vorherigen Beispiel und Koeffizienten s0 = -2, s1 = 1, s2 = 1 erhalten Sie beispielsweise 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 ℤ17.
|
|
| = t |
Wie finden Sie geeignete Koeffizienten s0, ..., sn-1, wenn Sie einen bestimmten Punkt t des Gitters als Kombination der Basisvektoren a0, ..., an-1 darstellen wollen? Dies läuft auf die Lösung eines linearen Gleichungssystems hinaus. Angenommen, Sie kennen die Werte für s0, ..., sn-1 in obigem Beispiel nicht. Sie lösen dann beliebige 3 von den 5 Gleichungen mit den 3 Unbekannten s0, s1, s2, standardmäßig mit dem gaußschen Eliminationsverfahren.
Noise
Ein Gleichungssystem 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 ei ∈ {-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 Gleichungssystems. 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):
Definition: (LWE-Problem)
Gegeben ist eine Matrix A von n Basisvektoren ai ∈ ℤqm und ein Punkt t ∈ ℤqm.
Gesucht ist der Lösungsvektor s ∈ ℤqn des Gleichungssystems
A ·s + e = t
wobei e ein unbekannter Fehlervektor ist.
Literatur
Die hier gewählte Darstellung folgt dem Buch
[PPG 24] C. Paar, J. Pelzl, T. Güneysu: Understanding Crytography. 2. Auflage, Springer (2024)
Weiter mit: [LWE-Verschlüsselung]
H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 29.01.2025 Updated: 25.06.2025
Diese Webseiten sind größtenteils während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden