Post-Quanten-Kryptografie

Zugrunde­gelegt ist ein Gitter L, das in den Raum ℤ_q^m eingebettet ist. Hierbei ist q eine Primzahl, alle Berechnungen werden modulo q durchgeführt. Das Gitter wird durch n Basis­vektoren a₀, ..., a_n-1 ∈ ℤ_q^m beschrieben; diese werden zu einer m×n-Matrix A zusammen­gefasst.

Das Learning-With-Errors-Problem (LWE)

Auf Grundlage eines Gitters erhalten Sie das sogenannte Learning-With-Errors-Problem (LWE):

Verschlüsseln mit LWE

Öffentlichen und privaten Schlüssel erzeugen

Mit folgenden Schritten erzeugen Sie als Empfänger einen öffentlichen Schlüssel und einen zugehörigen privaten Schlüssel.

Schlüssel erzeugen

Ausgabe:

Öffentlicher Schlüssel (t, A) und privater Schlüssel s

Methode:

1. Wähle n zufällige Spaltenvektoren a_i ∈ ℤ_q^m und bilde daraus die Matrix A  =  [a₀, ..., a_n-1].
2. Erzeuge einen zufälligen geheimen Schlüssel s ∈ ℤ_qⁿ, wobei dessen Komponenten s_i relativ "kleine" Werte sind, zum Beispiel |s_i|  ≤  q div 8.
3. Erzeuge einen zufälligen Fehlervektor e ∈ ℤ_q^m, ebenfalls mit "sehr kleinen" Werten, zum Beispiel aus der Menge {-1, 0 , 1}.
4. Berechne   t  =  A · s  +  e.
5. Gib (t, A) als öffentlichen Schlüssel und s als privaten Schlüssel zurück.

Die Wahr­schein­lich­keit ist sehr groß, dass die zufällig gewählten Basis­vektoren a₀, ..., a_n-1 tatsächlich linear unabhängig sind.

Verschlüsseln und ent­schlüsseln

Ein Sender ver­schlüsselt den Klartext m mit dem öffentlichen Schlüssel des Empfängers. Im einfachsten Fall besteht im Folgenden der Klartext nur aus einem einzigen Bit. d.h. m ∈ {0, 1}.

Der beim Verschlüsseln erzeugte Geheimtext besteht aus zwei Teilen: dem ver­schlüsselten Bit c und einem Hilfsvektor h. Etwas Ähnliches haben Sie bereits beim Verschlüsselungs­verfahren von ElGamal gesehen. Auch dort benötigt der Empfänger außer dem eigentlichen Geheimtext noch einen zusätzlichen Wert zum Entschlüsseln.

Bild 1 zeigt den Ablauf des LWE-Verschlüsselungs­verfahrens.

Vor dem eigentlichen Verschlüsseln wird das Bit m zunächst in eine Zahl m' ∈ ℤ_q codiert. Später nach dem Entschlüsseln wird diese Zahl wieder zurück in ein Bit dekodiert.

Bits codieren

Um einen Klartext m ∈ {0, 1} zu codieren, bilden Sie zunächst mithilfe einer Abbildung c die Menge {0, 1} in die Menge ℤ_q = {0, ..., q-1} ab, und zwar durch

m'  =  c(m)  =  m · q div 2  =

0     falls m = 0 q div 2     falls m = 1

Hierbei bedeutet div die ganzzahlige Division. Beispiels­weise bilden Sie für q = 17 die 0 auf die 0 und die 1 auf die 8 ab.

Zum Dekodieren bilden Sie mit einer Abbildung d alle q div 2 Zahlen aus ℤ_q, die zu 0 benachbart sind, zurück auf die 0 ab, und alle restlichen Zahlen, die zu q div 2 benachbart sind, zurück auf die 1.

m  =  d(m')  =

0     falls - (q div 4)  ≤  m'  <  q div 4 1     sonst

Für q = 17 sind die Zahlen -4, ..., 3 zu 0 benachbart; die restlichen Zahlen 4, ..., 12 sind zu 8 benachbart. Da q ungerade ist, hat die 8 einen Nachbarn mehr als die 0. Bild 2 zeigt anschaulich diese Zuordnung.

Verschlüsseln

Eingabe:

Öffentlicher Schlüssel (t, A) des Empfängers, Klartext m ∈ {0, 1}

Ausgabe:

Geheimtext (c, h) mit c ∈ ℤ_q und h ∈ ℤ_qⁿ

Methode:

1. Codiere das Klartextbit m durch m' = c(m) ∈ ℤ_q.
2. Wähle zufällige kleine Werte und bilde daraus Vektoren r ∈ ℤ_q^m und e ∈ ℤ_qⁿ, wähle zudem einen kleinen Wert e'.
3. Berechne   h  =  A^T · r  +  e.
4. Berechne   c  =  t^T · r  +  e'  +  m'.
5. Gib den Geheimtext (c, h) zurück.

Entschlüsseln

Eingabe:

Privater Schlüssel s ∈ ℤ_qⁿ des Empfängers, Geheimtext (c, h)

Ausgabe:

Klartextbit m ∈ {0, 1}

Methode:

1. Berechne   m'  =  c – s^T·h.
2. Dekodiere m' und gib das Ergebnis m = d(m') zurück.

Beispiel mit kleinen Zahlen

Anhand des folgenden Beispiels vollziehen Sie den Gang der Berechnungen mit kleinen Zahlen nach. Das Gitter L hat den Rang n = 3, es ist eingebettet in den m-dimensionalen Raum ℤ_q^m, hierbei ist m = 5. Die Zahl q ist gleich 17.

Schlüssel erzeugen

In Schritt 1 erzeugen Sie n = 3 zufällige Spalten­vektoren der Länge m = 5 mit Komponenten aus ℤ₁₇ und bilden daraus die Matrix A:

A  =

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

In Schritt 2 erzeugen Sie den Vektor s ∈ ℤ_q³ und den Fehlervektor e ∈ ℤ_q⁵ aus "kleinen" Werten:

s  =   -2 1 1

e  =   1 1 0 -1 1

Dann berechnen Sie in Schritt 3, jeweils immer modulo 17

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

· -2 1 1

+  1 1 0 -1 1

=   9 6 8 14 7

Nun haben Sie den öffentlichen Schlüssel (t, A) und den privaten Schlüssel s erhalten.

Verschlüsseln

Angenommen, Sie wollen das Bit m = 1 verschlüsseln.

Zunächst codieren Sie in Schritt 1 das Klartextbit m = 1 durch m'  =  c(m)  =  17 div 2  =  8.

Dann bilden Sie in Schritt 2 die Vektoren r und e sowie den Wert e'.

r  =   1 1 1 0 -1

e  =   0 1 0

e'  =  -1

In Schritt 3 berechnen Sie

h   =   AT · r  +  e   =   5 2 12 11 12 10 1 12 4 7 8 8 3 16 6

· 1 1 1 0 -1

+  0 1 0

=   7 0 13

In Schritt 4 berechnen Sie

c   =   tT · r  +  e'  +  m'   =   [ 9  6  8 14  7 ]

· 1 1 1 0 -1

+  (-1)  +  8   =   6

Nun senden Sie den Geheimtext (c, h) = (6, [7  0 13]^T) an den Empfänger.

Entschlüsseln

Als Empfänger berechnen Sie

m'   =   c – sT·h   =   6  –  [-2  1  1]

· 7 0 13

=   7

Dann dekodieren Sie m' = 7 zu m = d(7) = 1 und erhalten so das Klartextbit m = 1 zurück.

Sicherheit

Wenn Sie als Angreifer aus dem öffentlichen Schlüssel (t, A) den privaten Schlüssel s berechnen wollen, müssen Sie die Gleichung

A · s  +  e  =  t

lösen. Dies entspricht genau dem LWE-Problem. Ein LWE-Problem mit geeignet gewählten Parametern zu lösen, gilt jedoch als undurch­führ­bar, sowohl mit einem konventionellen Digitalcomputer als auch mit einem Quanten­computer.

Ent­sprechendes gilt, wenn Sie als Angreifer den Klartext direkt aus dem Geheimtext berechnen wollen.

Bewertung des Verfahrens

• Der Geheimtext, der durch Ver­schlüsselung nur eines einzigen Bits entsteht, erreicht eine beträchtliche Länge, insbesondere dann, wenn das Verfahren mit realistischen Parametern angewendet wird.
• Es ist natürlich zu wenig, nur ein einziges Bit zu verschlüsseln. Gebraucht wird ein Verfahren, das eine längere Bitfolge verschlüsseln kann.
• Auch ist die Datenmenge zu groß, die für den öffentlichen Schlüssel erforderlich ist, immerhin eine m×n-Matrix, wobei in realistischen Anwendungen die Dimensionen m und n in die Hunderte gehen können.

Literatur

Die hier gewählte Darstellung folgt dem Buch

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