Learning with errors

Learning with errors (LWE) ist ein Problem aus dem Bereich der Kryptographie, das in verschiedenen kryptographischen Anwendungen eingesetzt wird. Es wurde erstmals von Oded Regev im Jahr 2005 eingeführt. Regev wurde 2018 für seine Arbeit zum LWE-Problem und zur gitterbasierten Kryptographie mit dem Gödel-Preis ausgezeichnet.

Definition

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 $A$ und einen Vektor $\vec{b}$ , der durch Multiplikation von $A$ mit einem unbekannten Vektor $\vec{s}$ und der Addition eines Fehlervektors $\vec{e}$ entstanden ist. Die Aufgabe besteht nun darin, den Vektor $\vec{s}$ aus $A$ und $\vec{b}$ zu rekonstruieren. Es ergibt sich also folgende Gleichung:

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

Alle Operationen werden im Körper $ℤ_{p}$ mit Primzahl $p$ durchgeführt, also im Restklassenring modulo $p$ . Demnach gilt also $\vec{s} \in ℤ_{p}^{n}$ und $\vec{b}, \vec{e} \in ℤ_{p}^{m}$ sowie $A \in ℤ_{p}^{m \times n}$ mit $n, m \in ℕ$ .

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

\begin{matrix} b_{1} & = {\vec{a}}_{1} \cdot \vec{s} + e_{1} & mod p \\ b_{2} & = {\vec{a}}_{2} \cdot \vec{s} + e_{2} & mod p \\ ⋮ \\ b_{m} & = {\vec{a}}_{m} \cdot \vec{s} + e_{m} & mod p \end{matrix}

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

Für ein konkretes Learning-with-errors-Problem $L W E_{p, χ}$ mit einer Primzahl $p$ und einer Wahrscheinlichkeitsverteilung $χ$ werden die Vektoren ${\vec{a}}_{1}, \dots, {\vec{a}}_{m}$ zufällig unabhängig gleichverteilt aus $ℤ_{p}^{n}$ ausgewählt und die Fehlerterme $e_{1}, \dots, e_{m}$ werden zufällig unabhängig nach der Wahrscheinlichkeitsverteilung $χ$ , typischerweise einer diskreten Gaußverteilung, ausgewählt.

Anwendung

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 und das digitale Signaturverfahren CRYSTALS-Dilithium 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. Dabei dient $n$ als Sicherheitsparameter, der die Dimension des Geheimvektors und damit das Sicherheitsniveau des Systems bestimmt. Davon abhängig wird

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

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

Öffentlicher Schlüssel: Generierung des öffentlichen Schlüssels $(A, \vec{b})$
Um den öffentlichen Schlüssel zu generieren, werden die Vektoren ${\vec{a}}_{1}, \dots, {\vec{a}}_{m}$ unabhängig gleichverteilt aus $ℤ_{p}^{n}$ gewählt und die Werte $e_{1}, \dots, e_{m}$ unabhängig entsprechend der Wahrscheinlichkeitsverteilung $χ$ aus $ℤ_{p}$ . Der öffentliche Schlüssel besteht dann aus der Matrix $A$ , deren Zeilen die Vektoren ${\vec{a}}_{i}$ sind, sowie dem Vektor $\vec{b}$ .

Verschlüsseln

Für jedes Bit einer zu verschlüsselnden Nachricht wird eine zufällige Untermenge

S \subset {1, 2, \dots, m}

ausgewählt.

Wenn das zu verschlüsselnde Bit 0 ist, dann wird es als das Paar $(\sum_{i \in S} {\vec{a}}_{i}, \sum_{i \in S} b_{i})$ verschlüsselt.
Wenn das zu verschlüsselnde Bit 1 ist, dann wird es als das Paar $(\sum_{i \in S} {\vec{a}}_{i}, ⌊ \frac{p}{2} ⌋ + \sum_{i \in S} b_{i})$ verschlüsselt.

Entschlüsseln: Das entschlüsselte Bit aus dem Paar $(\vec{a}, b)$ ist $0$ , wenn $b - \vec{a} \cdot \vec{s}$ modulo $p$ näher bei $0$ als bei $⌊ \frac{p}{2} ⌋$ liegt. Ansonsten ist das entschlüsselte Bit $1$ .

Literatur

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.

Einzelnachweise

↑ Oded Regev: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing. STOC '05. Association for Computing Machinery, 2005, ISBN 1-58113-960-8, S. 84–93, doi:10.1145/1060590.1060603.
1 2 3 4 5 6 7 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.
↑ 2018 Gödel Prize. In: European Association for Theoretical Computer Science. European Association for Theoretical Computer Science, abgerufen am 12. Februar 2026.
1 2 Carl Richard Theodor Schneider: Backdoors in cryptography. Ruhr-Universität Bochum, Universitätsbibliothek, 2025, S. 21, doi:10.13154/294-12053, urn:nbn:de:hbz:294-120539.
↑ National Institute of Standards and Technology: Module-Lattice-Based Key-Encapsulation Mechanism Standard. National Institute of Standards and Technology, 2024, NIST FIPS 203, doi:10.6028/NIST.FIPS.203.
↑ National Institute of Standards and Technology: Module-Lattice-Based Digital Signature Standard. National Institute of Standards and Technology, 2024, NIST FIPS 204, doi:10.6028/NIST.FIPS.204.
1 2 Julius Hermelink: Side-Channel and Fault Attacks in Modern Lattice-Based Cryptography. Universitätsbibliothek der Universität der Bundeswehr München, 2024, S. 24, urn:nbn:de:bvb:706-9934.
↑ Adeline Langlois, Damien Stehlé: Worst-case to average-case reductions for module lattices. In: Designs, Codes and Cryptography. Band 75, Nr. 3. Springer Science and Business Media LLC, 2015, ISSN 1573-7586, S. 565–599, doi:10.1007/s10623-014-9938-4.
↑ Daniele Micciancio: Closest Vector Problem. In: Henk C. A. van Tilborg (Hrsg.): Encyclopedia of Cryptography and Security. Springer US, 2005, ISBN 0-387-23483-7, S. 79–80, doi:10.1007/0-387-23483-7_66 (ucsd.edu [PDF]).

[Regev2005-1] Oded Regev: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing. STOC '05. Association for Computing Machinery, 2005, ISBN 1-58113-960-8, S. 84–93, doi:10.1145/1060590.1060603.

[Regev2009-2] 1 2 3 4 5 6 7 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.

[Gödelpreis2018-3] 2018 Gödel Prize. In: European Association for Theoretical Computer Science. European Association for Theoretical Computer Science, abgerufen am 12. Februar 2026.

[Schneider2025-4] 1 2 Carl Richard Theodor Schneider: Backdoors in cryptography. Ruhr-Universität Bochum, Universitätsbibliothek, 2025, S. 21, doi:10.13154/294-12053, urn:nbn:de:hbz:294-120539.

[ML-KEM-5] National Institute of Standards and Technology: Module-Lattice-Based Key-Encapsulation Mechanism Standard. National Institute of Standards and Technology, 2024, NIST FIPS 203, doi:10.6028/NIST.FIPS.203.

[ML-DSA-6] National Institute of Standards and Technology: Module-Lattice-Based Digital Signature Standard. National Institute of Standards and Technology, 2024, NIST FIPS 204, doi:10.6028/NIST.FIPS.204.

[Hermelink2024-7] 1 2 Julius Hermelink: Side-Channel and Fault Attacks in Modern Lattice-Based Cryptography. Universitätsbibliothek der Universität der Bundeswehr München, 2024, S. 24, urn:nbn:de:bvb:706-9934.

[Langlois2014-8] Adeline Langlois, Damien Stehlé: Worst-case to average-case reductions for module lattices. In: Designs, Codes and Cryptography. Band 75, Nr. 3. Springer Science and Business Media LLC, 2015, ISSN 1573-7586, S. 565–599, doi:10.1007/s10623-014-9938-4.

[Micciancio2005-9] Daniele Micciancio: Closest Vector Problem. In: Henk C. A. van Tilborg (Hrsg.): Encyclopedia of Cryptography and Security. Springer US, 2005, ISBN 0-387-23483-7, S. 79–80, doi:10.1007/0-387-23483-7_66 (ucsd.edu [PDF]).

Learning with errors

Definition

Anwendung

Beispiel: Public-Key-Kryptosystem

Verwandte Probleme

Learning Parity with Noise (LPN)

Ring-Learning with errors (R-LWE)

Module Learning with Errors (M-LWE)

Closest Vector Problem (CVP)

Literatur

Einzelnachweise