Post-Quanten-Kryptografie

Die Matrix-Operationen des Standard-Learning-With-Errors-Problems werden beim Ring-Learning-With-Errors-Problem durch Polynom-Operationen ersetzt. Die Bezeichnung Ring-LWE bezieht sich darauf, dass die Berechnungen in einem Polynomring durchgeführt werden.

Die Verschlüsselung mit Ring-LWE verläuft sehr ähnlich wie die Verschlüsselung mit Standard-LWE, mit dem Unterschied, dass nicht nur ein einziges Bit, sondern ein Bitvektor der Länge n verschlüsselt wird. Daher eignet sich das Verfahren sehr gut zur verschlüsselten Übertragung eines geheimen Schlüssels für ein symmetrisches Verschlüsselungsverfahren wie etwa AES. Dieser Vorgang wird auch als key encapsulation bezeichnet – der Schlüssel für das symmetrische Verschlüsselungsverfahren wird gleichsam eingekapselt, bevor er übertragen wird.

Wie bei der Standard-LWE-Verschlüsselung wird beim Verschlüsseln etwas "Rauschen" hinzugefügt, hier ein zufälliges Fehlerpolynom e. Dies führt dazu, dass ein Angreifer nicht ohne Weiteres die Berechnungen zurück abwickeln kann, denn er kennt das Fehlerpolynom e nicht. Andererseits führt es dazu, dass beim Entschlüsseln nicht wieder exakt dasselbe herauskommt, was beim Verschlüsseln hineingesteckt worden ist, sondern nur ungefähr dasselbe, gleichsam ein etwas "verrauschter" ursprünglicher Klartext. Dieses Rauschen lässt sich jedoch mithilfe einer geeigneten Codierung der Bits 0 und 1 herausfiltern, sodass der Klartext wieder klar und deutlich zurückgewonnen wird.

Rechnen in einem Polynomring

Der in diesem Zusammenhang gebräuchlichste Polynomring ist der Ring R  =  ℤ_q[x] / (xⁿ +1). Dabei wird der Ring (oder Körper) ℤ_q zugrundegelegt, und es werden alle Polynome mit Koeffizienten aus ℤ_q vom Grad kleiner als n gebildet. Die Zahl n ist eine Zweierpotenz. Die Rechenoperationen Addition, Subtraktion und Multiplikation werden in Form von Polynomarithmetik durchgeführt, wobei das Ergebnis einer Multiplikation stets modulo des Polynoms xⁿ + 1 reduziert wird, sodass stets wieder ein Polynom vom Grad  < n herauskommt. Da ℤ_q zugrundegelegt ist, werden alle Berechnungen mit den Koeffizienten modulo q durchgeführt.

Diese Art von Berechnungen entspricht genau der Arithmetik in einem Erweiterungskörper, wie etwa beim AES-Verschlüsselungsverfahren.

Beispiel

Es sei q = 17 und n = 2. Betrachten Sie die Polynome

a  =  12·x + 7   und   b  =  6·x + 4

Dann erhalten Sie für die Addition, bei den Koeffizienten modulo 17 gerechnet

a + b  =  12·x + 7  +  6·x + 4  =  (12+6)·x + (7+4)  =  18·x + 11  =  x + 11

Für die Multiplikation erhalten Sie, modulo x² + 1 gerechnet und bei den Koeffizienten modulo 17 gerechnet

a · b  =

(12·x + 7) · (6·x + 4)  =

72·x² + 48·x + 42·x + 28  = 

72·(-1) + 90·x + 28  =

90·x – 72 + 28  =

90·x – 44  =

5·x + 7

Im letzten Schritt wurden die Koeffizienten modulo 17 reduziert.

Ring-LWE-Problem

Verschlüsseln mit Ring-LWE

Zugrundegelegt ist der Ring R  =  ℤ_q[x] / (xⁿ +1) wie oben mit q Primzahl und n Zweierpotenz.

Schlüssel erzeugen

Ausgabe:

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

Methode:

1. Wähle zufällig ein Polynom a ∈ R.
2. Erzeuge ein zufälliges Polynom s ∈ R, dessen Koeffizienten relativ "kleine" Werte sind.
3. Erzeuge ein zufälliges Fehlerpolynom e ∈ R mit "sehr kleinen" Koeffizienten, z.B. 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.

Das folgende Bild 1 zeigt den Ablauf des Ring-LWE-Verschlüsselungsverfahrens, hier angewendet für die key encapsulation – der Klartext m ist gedacht als geheimer Schlüssel für ein symmetrisches Verschlüsselungsverfahren wie etwa AES. Am Ende der Berechnung verfügen beide Kommunikationspartner A und B über den gleichen geheimen Schlüssel m.

Vor dem eigentlichen Verschlüsseln werden die Bits m_i des Klartextes zunächst wie bei der Standard-LWE-Verschlüsselung als m_i' = c(m_i) = m_i · q div 2 codiert.

Verschlüsseln

Eingabe:

Öffentlicher Schlüssel (t, a) und Klartext m ∈ {0, 1}ⁿ

Ausgabe:

Geheimtext (c, h)

Methode:

1. Codiere die n Klartextbits m_i als m_i' = c(m_i) und verwende diese Werte als Koeffizienten für das Polynom m'.
2. Wähle zufällige kleine Werte aus ℤ_q und bilde die Polynome r, e und e' mit diesen Werten als Koeffizienten.
3. Berechne   h  =  a · r  +  e.
4. Berechne   c  =  t · r  +  e'  +  m'.
5. Gib den Geheimtext (c, h) zurück.

Entschlüsseln

Eingabe:

Privater Schlüssel s und Geheimtext (c, h)

Ausgabe:

Klartext m ∈ {0, 1}ⁿ

Methode:

1. Berechne   m'  =  c  –  h · s.
2. Dekodiere die Koeffizienten m_i' des Polynoms m' zu den Komponenten m_i = d(m_i') des Klartextes m ∈ {0, 1}ⁿ.

Wie bei der Standard-LWE-Verschlüsselung werden beim Dekodieren alle Werte aus ℤ_q, die nahe an 0 liegen, also 0 ± 0, 1, 2, 3, ...  zum Bit 0 ausgewertet; alle Werte aus ℤ_q, die nahe an q div 2 liegen, also q div 2 ± 0, 1, 2, 3, ...  werden zum Bit 1 ausgewertet.

Beispiel mit kleinen Zahlen

Als Parameter legen Sie zunächst n = 2³ und q = 37 fest.

Der Übersichtlichkeit halber schreiben Sie die Polynome aus R auch einfach als Vektoren der Länge n = 8, also etwa

a  =  [7 10 9 4 6 28 11 13]     für     a   =   7  + 10·x + 9·x² + 4·x³ + 6·x⁴ + 28·x⁵ + 11·x⁶ + 13·x⁷

Schlüssel erzeugen

In Schritt 1 wählen Sie ein zufälliges Polynom a:

a  =  [7 10 9 4 6 28 11 13]

In Schritt 2 erzeugen Sie das Polynom s mit kleinen Werten als Koeffizienten:

s  =  [0 0 -2 0 1 0 -1 0]

In Schritt 3 erzeugen Sie das Fehlerpolynom e mit kleinen Werten als Koeffizienten:

e  =  [1 0 1 -1 1 1 -1 1]

In Schritt 4 berechnen Sie  t   =   a · s  +  e  und erhalten

t  =  [26 2 19 31 1 16 26 13]

Sie geben nun den öffentlichen Schlüssel (t, a)  =  ([26 2 19 31 1 16 26 13], [7 10 9 4 6 28 11 13]) und den privaten Schlüssel s  =  [0 0 -2 0 1 0 -1 0] zurück.

Verschlüsseln

Als Eingabe verwenden Sie den öffentlichen Schlüssel (t, a) des Empfängers sowie einen Klartext der Länge 8, also z.B. m  =  [0 0 0 1 0 1 1 0].

In Schritt 1 codieren Sie den Klartext m  =  [0 0 0 1 0 1 1 0] mit der Codierung c und erhalten m'  =  c(m)  =  [0 0 0 18 0 18 18 0].

In Schritt 2 bilden Sie die Polynome r, e und e' aus zufälligen kleinen Werten, also etwa

r  =  [0 2 2 -1 -1 2 -1 0]

e  =  [0 -1 -1 -1 -1 1 -2 0]

e'  =  [-2 -2 0 1 -1 0 0 1]

In Schritt 3 berechnen Sie   h  =  a · r  +  e, also

h   =   [7 10 9 4 6 28 11 13] · [0 2 2 -1 -1 2 -1 0] + [0 -1 -1 -1 -1 1 -2 0]   =   [24 18 7 12 30 29 29 2]

In Schritt 4 berechnen Sie   c  =  t · r  +  e' + m', also

c   =   [26 2 19 31 1 16 26 13] · [0 2 2 -1 -1 2 -1 0] + [-2 -2 0 1 -1 0 0 1] + [0 0 0 18 0 18 18 0]   =   [5 21 27 12 34 15 17 15]

Zum Schluss geben Sie den Geheimtext (c, h)  =  ([5 21 27 12 34 15 17 15], [24 18 7 12 30 29 29 2]) zurück.

Entschlüsseln

Als Eingabe verwenden Sie Ihren privaten Schlüssel s sowie den Geheimtext (c, h).

In Schritt 1 berechnen Sie   m'  =  c  –  h · s, also

m'   =   [5 21 27 12 34 15 17 15] – [24 18 7 12 30 29 29 2] · [0 0 -2 0 1 0 -1 0]   =   [7 34 0 21 32 19 20 5]

Dann dekodieren Sie die Koeffizienten m_i' des Polynoms m' zu den Komponenten m_i = d(m_i') des Klartextes m ∈ {0, 1}ⁿ:

m  =  [0 0 0 1 0 1 1 0]

Wie gewünscht haben Sie den ursprünglichen Klartext zurückerhalten.

Literatur

Die hier gewählte Darstellung folgt dem Buch

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