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.

Das LWE-Problem bezieht sich auf die Schwierigkeit, aus einer Reihe von Gleichungen mit fehlerbehafteten Variablen die ursprünglichen Variablen zu bestimmen. Im Detail: Angenommen, wir haben eine Matrix A und einen Vektor b, der durch Multiplikation von A und einem unbekannten Vektor s mit einer Fehlerrate e entstanden ist. Die Aufgabe besteht nun darin, den Vektor s aus A und b zu rekonstruieren.

Das LWE-Problem wird in der Kryptographie in verschiedenen Verfahren eingesetzt, insbesondere für den Bau von verschlüsselnden und signierenden Algorithmen. 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, was bedeutet, dass sie resistenter gegen bestimmte Angriffsmethoden sind.

Allerdings gibt es auch Angriffsmethoden, die speziell für LWE-Systeme entwickelt wurden, wie z. B. die „Short Integer Solution“ (SIS) und die „Learning Parity with Noise“ (LPN). Trotzdem ist LWE ein vielversprechendes Konzept und ein aktiver Forschungsbereich in der Kryptographie.

In der Praxis wird LWE bereits in verschiedenen Anwendungen eingesetzt, wie z. B. in der Post-Quantum-Kryptographie und der sicheren Datenübertragung. Auch wenn LWE noch nicht so etabliert ist wie andere kryptographische Verfahren, so wird es in Zukunft wahrscheinlich eine wichtige Rolle in der Kryptographie spielen.

Literatur

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