Learning with errors

Das LWE-Problem bezieht sich auf die Schwierigkeit, aus linearen Gleichungen mit additivem Zufallsfehler einen unbekannten Geheimvektor zu rekonstruieren.

Im Detail: Angenommen, wir haben eine Matrix ${\displaystyle A}$ und einen Vektor ${\displaystyle {\vec {b}}}$, der durch Multiplikation von ${\displaystyle A}$ mit einem unbekannten Vektor ${\displaystyle {\vec {s}}}$ und der Addition eines Fehlervektors ${\displaystyle {\vec {e}}}$ entstanden ist. Die Aufgabe besteht nun darin, den Vektor ${\displaystyle {\vec {s}}}$ aus ${\displaystyle A}$ und ${\displaystyle {\vec {b}}}$ zu rekonstruieren. Es ergibt sich also folgende Gleichung:

${\displaystyle {\vec {b}}=A\cdot {\vec {s}}+{\vec {e}}}$

Alle Operationen werden im Körper ${\displaystyle \mathbb {Z} _{p}}$ mit Primzahl ${\displaystyle p}$ durchgeführt, also im Restklassenring modulo ${\displaystyle p}$. Demnach gilt also ${\displaystyle {\vec {s}}\in \mathbb {Z} _{p}^{n}}$ und ${\displaystyle {\vec {b}},{\vec {e}}\in \mathbb {Z} _{p}^{m}}$ sowie ${\displaystyle A\in \mathbb {Z} _{p}^{m\times n}}$ mit ${\displaystyle n,m\in \mathbb {N} }$.^[2][4]

Die Matrix-Vektor-Gleichung kann auch als ein lineares Gleichungssystem betrachtet werden. ${\displaystyle n}$ sei hierzu die Dimension des Geheimvektors ${\displaystyle {\vec {s}}}$ und ${\displaystyle m}$ die Anzahl der Gleichungen bzw. die Dimension der Vektoren ${\displaystyle {\vec {b}}}$ und ${\displaystyle {\vec {e}}}$. Die ${\displaystyle m\times n}$-Matrix ${\displaystyle A}$ bestehe aus den Zeilenvektoren ${\displaystyle {\vec {a}}_{1},{\vec {a}}_{2}\dots ,{\vec {a}}_{m}}$:^[2][4]

${\displaystyle {\begin{aligned}b_{1}&={\vec {a}}_{1}\cdot {\vec {s}}+e_{1}&\mod p\\b_{2}&={\vec {a}}_{2}\cdot {\vec {s}}+e_{2}&\mod p\\&\vdots \\b_{m}&={\vec {a}}_{m}\cdot {\vec {s}}+e_{m}&\mod p\\\end{aligned}}}$

Wäre bekannt, dass ${\displaystyle {\vec {e}}}$ der Nullvektor ${\displaystyle {\vec {0}}}$ ist, könnte das Gleichungssystem aus ${\displaystyle m}$ vielen Gleichungen in Polynomialzeit ${\displaystyle \operatorname {poly} (n)}$ mit einem Verfahren wie dem Gauß-Verfahren effizient gelöst werden, um ${\displaystyle {\vec {s}}}$ zu erhalten. Durch die Addition des Fehlervektors ${\displaystyle {\vec {e}}}$ wird das Problem aber deutlich schwerer; bekannte Algorithmen zur Lösung laufen in Exponentialzeit ${\displaystyle 2^{O(n)}}$.^[2]

Für ein konkretes Learning-with-errors-Problem ${\displaystyle LWE_{p,\chi }}$ mit einer Primzahl ${\displaystyle p}$ und einer Wahrscheinlichkeitsverteilung ${\displaystyle \chi }$ werden die Vektoren ${\displaystyle {\vec {a}}_{1},\dots ,{\vec {a}}_{m}}$ zufällig unabhängig gleichverteilt aus ${\displaystyle \mathbb {Z} _{p}^{n}}$ ausgewählt und die Fehlerterme ${\displaystyle e_{1},\dots ,e_{m}}$ werden zufällig unabhängig nach der Wahrscheinlichkeitsverteilung ${\displaystyle \chi }$, typischerweise einer diskreten Gaußverteilung, ausgewählt.^[2]

Das LWE-Problem wird in der Kryptographie in verschiedenen Verfahren eingesetzt, insbesondere für die Konstruktion von Verschlüsselungs- und Signaturverfahren. Der Grund dafür liegt in der Annahme, dass das LWE-Problem schwer genug ist, um als Basis für kryptographische Verfahren genutzt zu werden, aber gleichzeitig effizient genug, um in der Praxis eingesetzt zu werden.

Ein bekanntes Anwendungsgebiet von LWE ist die Entwicklung von Public-Key-Kryptographie-Systemen, wie z. B. den „Learning with Errors Key Exchange“ (LWE-KEX) oder „Learning with Errors Encryption“ (LWE-E). Diese Verfahren sind besonders interessant, da sie im Gegensatz zu traditionellen Public-Key-Kryptographie-Systemen wie RSA oder Diffie-Hellman nicht auf der Faktorisierung großer Zahlen oder dem diskreten Logarithmusproblem basieren. Für LWE-basierte Verfahren sind bislang keine effizienten Quantenalgorithmen bekannt, im Gegensatz zu RSA oder Diffie-Hellman, die durch den Shor-Algorithmus gebrochen werden können.

LWE ist ein vielversprechendes Konzept und ein aktiver Forschungsbereich in der Kryptographie. In der Praxis wird LWE bereits in verschiedenen Anwendungen eingesetzt, etwa innerhalb des Bereichs der Post-Quanten-Kryptographie und als Basis für sichere Datenübertragung.

Im Rahmen der Post-Quanten-Kryptographie-Standardisierung des NIST wurden 2024 das Schlüsselkapselungsverfahren CRYSTALS-Kyber^[5] und das digitale Signaturverfahren CRYSTALS-Dilithium^[6] standardisiert. Beide Verfahren basieren auf dem mit LWE verwandten Problem Module Learning with errors (M-LWE).

Beispiel: Public-Key-Kryptosystem

Regev beschreibt 2009 bereits ein Learning-with-errors-basiertes Public-Key-Kryptosystem, bei dem ein privater und ein öffentlicher Schlüssel generiert werden, um dann zu ver- und entschlüsseln.^[2] Dabei dient ${\displaystyle n}$ als Sicherheitsparameter, der die Dimension des Geheimvektors und damit das Sicherheitsniveau des Systems bestimmt. Davon abhängig wird

• die Primzahl ${\displaystyle p}$ zwischen ${\displaystyle n^{2}}$ und ${\displaystyle 2n^{2}}$,
• ${\displaystyle m=(1+\varepsilon )(n+1)\log p}$ mit einem beliebigen ${\displaystyle \varepsilon >0}$ sowie
• die Wahrscheinlichkeitsverteilung ${\displaystyle \chi }$ als eine diskrete Gaußverteilung mit Erwartungswert ${\displaystyle 0}$ festgelegt.

Privater Schlüssel

Um einen privaten Schlüssel zu generieren, wird ein zufälliger Vektor ${\displaystyle {\vec {s}}}$ aus ${\displaystyle \mathbb {Z} _{p}^{n}}$ gewählt. Dieser Vektor ${\displaystyle {\vec {s}}}$ ist der private Schlüssel.

Öffentlicher Schlüssel

Um den öffentlichen Schlüssel zu generieren, werden die Vektoren ${\displaystyle {\vec {a}}_{1},\dots ,{\vec {a}}_{m}}$ unabhängig gleichverteilt aus ${\displaystyle \mathbb {Z} _{p}^{n}}$ gewählt und die Werte ${\displaystyle e_{1},\dots ,e_{m}}$ unabhängig entsprechend der Wahrscheinlichkeitsverteilung ${\displaystyle \chi }$ aus ${\displaystyle \mathbb {Z} _{p}}$. Der öffentliche Schlüssel besteht dann aus der Matrix ${\displaystyle A}$, deren Zeilen die Vektoren ${\displaystyle {\vec {a}}_{i}}$ sind, sowie dem Vektor ${\displaystyle {\vec {b}}}$.

Verschlüsseln

Für jedes Bit einer zu verschlüsselnden Nachricht wird eine zufällige Untermenge ${\displaystyle S\subset \{1,2,\dots ,m\}}$ ausgewählt.

• Wenn das zu verschlüsselnde Bit 0 ist, dann wird es als das Paar ${\displaystyle \left(\sum _{i\in S}{\vec {a}}_{i},\ \sum _{i\in S}b_{i}\right)}$ verschlüsselt.
• Wenn das zu verschlüsselnde Bit 1 ist, dann wird es als das Paar ${\displaystyle \left(\sum _{i\in S}{\vec {a}}_{i},\ \left\lfloor {\frac {p}{2}}\right\rfloor +\sum _{i\in S}b_{i}\right)}$ verschlüsselt.

Entschlüsseln

Das entschlüsselte Bit aus dem Paar ${\displaystyle ({\vec {a}},b)}$ ist ${\displaystyle 0}$, wenn ${\displaystyle b-{\vec {a}}\cdot {\vec {s}}}$ modulo ${\displaystyle p}$ näher bei ${\displaystyle 0}$ als bei ${\displaystyle \left\lfloor {\frac {p}{2}}\right\rfloor }$ liegt. Ansonsten ist das entschlüsselte Bit ${\displaystyle 1}$.

Learning Parity with Noise (LPN)

LPN kann als Spezialfall von LWE mit ${\displaystyle p=2}$ und einer Bernoulli-verteilten Fehlerkomponente aufgefasst werden, wobei ein Fehlerterm ${\displaystyle e_{i}}$ mit Wahrscheinlichkeit ${\displaystyle \varepsilon }$ gleich ${\displaystyle 1}$ ist.^[2]

Ring-Learning with errors (R-LWE)

Ring-LWE ist eine Variante von LWE, die statt mit Vektoren über ${\displaystyle \mathbb {Z} _{p}}$ mit Polynomen über einem geeigneten Polynomring arbeitet.^[7]

Module Learning with Errors (M-LWE)

Module-LWE ist eine Variante von LWE und eine Verallgemeinerung von Ring-LWE.^[7] Statt einzelner Polynomringe werden Modulstrukturen verwendet. Ein Modul ist wiederum eine algebraische Struktur, die Ringe und Vektorräume generalisiert.^[8]

Closest Vector Problem (CVP)

Gegeben sei ein Gitter und ein Zielpunkt. Es soll der Gitterpunkt gefunden werden, der am nächsten am Zielpunkt liegt.^[9] (Siehe Abbildung)

Man kann die Gleichung des LWE-Problems

${\displaystyle {\vec {b}}=A\cdot {\vec {s}}+{\vec {e}}}$

in diesem Kontext wie folgt betrachten: Die Matrix ${\displaystyle A}$ enthält die Basisvektoren eines Gitters als Zeilen. ${\displaystyle A\cdot {\vec {s}}}$ beschreibt einen Gitterpunkt als die Linearkombination der Basisvektoren mit den Koeffizienten aus ${\displaystyle {\vec {s}}}$. ${\displaystyle {\vec {b}}}$ ist der Zielpunkt, der nahe an einem Gitterpunkt ${\displaystyle A\cdot {\vec {s}}}$ liegt. Mit LWE soll der Vektor ${\displaystyle {\vec {s}}}$ gefunden werden, der durch Linearkombination der Basisvektoren den zu ${\displaystyle {\vec {b}}}$ nächsten Gitterpunkt ergibt.

• Oded Regev: On lattices, learning with errors, random linear codes, and cryptography. In: Journal of the ACM. Band 56, Nr. 6, 2009, 34, doi:10.1145/1568318.1568324.
• Chris Peikert: Lattice Cryptography for the Internet. Springer International Publishing, 2014, ISBN 978-3-319-11658-7, S. 197–218, doi:10.1007/978-3-319-11659-4_12.