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

Wie bei der Standard-LWE-Ver­schlüsselung wird beim Verschlüsseln etwas "Rauschen" hinzugefügt, hier ein zufälliges Fehler­polynom e. Dies führt dazu, dass ein Angreifer nicht ohne Weiteres die Berechnungen zurück abwickeln kann, denn er kennt das Fehler­polynom 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üng­licher 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ück­gewonnen wird.

Rechnen in einem Polynomring

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

Diese Art von Berechnungen entspricht genau der Arithmetik in einem Erweiterungs­körper, wie etwa beim AES-Ver­schlü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 Multi­plikation 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

Zugrunde­gelegt 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-Ver­schlüsselungsverfahrens, hier angewendet für die key encapsulation – der Klartext m ist gedacht als geheimer Schlüssel für ein symmetrisches Ver­schlü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-Ver­schlüsselung als m_i' = f(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' = f(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 = g(m_i') des Klartextes m ∈ {0, 1}ⁿ.

Wie bei der Standard-LWE-Ver­schlü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 n = 2³ und q = 37 fest, und Sie schreiben die Polynome aus R 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 Fehler­polynom 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 f und erhalten m'  =  f(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 = g(m_i') des Klartextes m ∈ {0, 1}ⁿ:

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

Wie gewünscht haben Sie den ursprüng­lichen 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)