Securely Instantiating Cryptographic Schemes Based on the Learning with Errors Assumption

Since its proposal by Regev in 2005, the Learning With Errors (LWE) problem was used as the underlying problem for a great variety of schemes. Its applications are many-fold, reaching from basic and highly practical primitives like key exchange, public-key encryption, and signature schemes to very advanced solutions like fully homomorphic encryption, group signatures, and identity based encryption. One of the underlying reasons for this fertility is the flexibility with that LWE can be instantiated. Unfortunately, this comes at a cost: It makes selecting parameters for cryptographic applications complicated. When selecting parameters for a new LWE-based primitive, a researcher has to take the influence of several parameters on the efficiency of the scheme and the runtime of a variety of attacks into consideration. In fact, the missing trust in the concrete hardness of LWE is one of the main problems to overcome to bring LWE-based schemes to practice. This thesis aims at closing the gap between the theoretical knowledge of the hardness of LWE, and the concrete problem of selecting parameters for an LWE-based scheme. To this end, we analyze the existing methods to estimate the hardness of LWE, and introduce new estimation techniques where necessary. Afterwards, we show how to transfer this knowledge into instantiations that are at the same time secure and efficient. We show this process on three examples:

• A highly optimized public-key encryption scheme for embedded devices that is based on a variant of Ring-LWE.
• A practical signature scheme that served as the foundation of one of the best lattice-based signature schemes based on standard lattices.
• An advanced public-key encryption scheme that enjoys the unique property of natural double hardness based on LWE instances similar to those used for fully homomorphic encryption.

Einer der Grundpfeiler unserer modernen digitalen Gesellschaft sind asymmetrische Verschlüsselungs- und Signaturverfahren. Asymmetrische Verfahren zeichnen sich dadurch aus, dass es nicht einen geheimen Schlüssel gibt, sondern ein Schlüsselpaar bestehend aus einem geheimen und einem öffentlichen Schlüssel. Der öffentliche Schlüssel erlaubt etwa das Verschlüsseln einer Nachricht oder das verifizieren einer Signatur, zum Entschlüsseln der Nachricht oder erzeugen der Signatur ist hingegen der geheime Schlüssel notwendig. Allen diesen Verfahren gemein ist dass ihre Sicherheit auf einem numerisch schwer zu lösenden Problem beruht. In nahezu allen heute in der Praxis benutzen Verfahren ist dieses Problem entweder das Faktorisieren großer Zahlen, oder das diskrete Logarithmus Problem in verschiedenen Gruppen. Die auf diesen Problemen beruhenden Verfahren sind effizient und werden für sicher gehalten, haben jedoch ein großes Problem: Wie Peter Shor 1994 zeigte, können sie von Quantencomputern in polynomieller Zeit gelöst werden. In einer Zukunft, in der Quantencomputer existieren (was zufolge vieler Experten bereits in 20 Jahren der Fall sein könnte), sind auf sie also zum sichern vertraulicher Kommunikation ungeeignet. Diese Arbeit befasst sich mit der Schwere des Learning With Errors (LWE) Problems. Auf LWE basierende Verfahren gehören zu den vielversprechendsten Kandidaten, um Faktorisierungs- und diskrete Logarithmus basierte Verfahren abzulösen. Sie sind sehr effizient und können nach dem aktuellen Stand der Forschung nicht von Quantencomputern angegriffen werden. Die Verfahren sind üblicherweise mithilfe eines Sicherheitsbeweises an LWE gebunden. Dieser besagt dass man eine bestimmte LWE Instanz lösen muss, um das Verfahren zu brechen. Über die theoretische Schwere von LWE ist bereits viel bekannt. Wie Regev bereits 2005 zeigte, sind zufällige Instanzen von LWE (asymptotisch) mindestens so schwer wie die schwersten Instanzen verschiedener, etablierter Gitterprobleme. Leider sagen weder Regev's Resultat über die asymptotische Schwere von LWE, noch der Sicherheitsbeweis etwas darüber aus, wie schwer diese LWE Instanz ist. Folglich ist es von erheblicher Bedeutung für Theorie und Praxis, die Schwere konkreter LWE Instanzen zu untersuchen, und aus diesen Erkenntnissen korrekte Parameter für die LWE-basierten Verfahren abzuleiten. Folglich ist diese Arbeit in zwei Abschnitte unterteilt. Der Erste präsentiert neue theoretische und experimentelle Ergebnisse über die Schwere von LWE. Es besteht aus neuen Resultaten über die Schwere von LWE Instanzen unter Einschränkungen, die in der Praxis auftreten (Kapitel 3), eine experimentelle Untersuchung der Parallelisierbarkeit eines der vielversprechendsten LWE-Lösers (Kapitel 4), ein neuer Algorithmus zum Lösen von LWE (Kapitel 5), und eine neue Methode zum experimentellen Vergleich verschiedener LWE-Löser (Kapitel 6). Der zweite Abschnitt zeigt anhand dreier Beispiele, wie sich die Erkenntnisse über die Schwere von LWE nutzen lassen, um Parameter für kryptographische Verfahren zu wählen. Die Verfahren sind ein Signaturverfahren (Kapitel 7), ein Verschlüsselungsverfahren (Kapitel 8), und ein Verschlüsselungsverfahren mit erweiterten Sicherheitseigenschaften (Kapitel 9).