A tool for the estimation of lattice parameters

Abstract

This work introduces a new tool that can be used to find secure parameters for schemes based on the Learning with Errors (LWE) and the Short Integer Solution (SIS). Since the proposal of worst-case to average-case reductions from certain hard lattice problems to SIS and LWE respectively, both SIS and LWE have led to a plethora of cryptograpic schemes. Lattice based cryptography is highly in demand particularly in the context of post-quantum cryptography, as the era of quantum computing will render several widely applied schemes, such as RSA, insecure. To use LWE and SIS in practice, we first must establish their concrete hardness, given a set of paramters, by applying runtime estimates for the currently best known algorithms that solve LWE and SIS. This has been done for LWE in the LWE Estimator by Albrecht et al. (JMC 2015) and subsequent works. However, at this point, there is no unified tool that provides estimates for both LWE and SIS as well as their ring and module variants. We aim to close this gap with a new Python library. Our tool includes previous estimates for LWE from the LWE Estimator and adds new attack estimates for SIS. In this thesis, we give an overview of the LWE and SIS problems and describe various algorithms that that can be used to solve them. In addition, we present current popular cost models that many estimates rely on from the literature. At the core of our tool is a generic paramter search function that is both simple to use and allows for extensive customization. Our tool supports important problem variants in several p-norms, norm bound estimates and distribution classes.

In dieser Arbeit stellen wir ein neues Werkzeug vor, mit dem sichere Parameter für Systeme gefunden werden können, die auf den Learning with Errors (LWE) und Short Integer Solution (SIS) Problemen basieren. Seit ihrer Einführung mit Reduktionen von bestimmten worst-case harten Gitterproblemen haben sowohl SIS als auch LWE zu einer Fülle von kryptographischen Schemata geführt. Da einige herkömmliche Verfahren wie RSA von Quantencomputern effizient gebrochen werden können sind, sind gitterbasierte Systeme, die auf stärkeren Härteannahmen beruhen, sehr gefragt. Um LWE und SIS in der Praxis einsetzen zu können, müssen wir zunächst ihre konkrete Sicherheitsstufe für gegebene Parameter bestimmen, indem wir Laufzeitschätzungen für die derzeit besten bekannten Algorithmen zur Lösung von LWE und SIS anwenden. Dies wurde für LWE im LWE Estimator von Albrecht et al. (JMC 2015) und nachfolgenden Arbeiten getan. Bislang gibt es jedoch kein einheitliches Tool, das Schätzungen für LWE und SIS sowie deren Ring- und Modulnvarianten liefert. Wir wollen diese Lücke mit einer neuen Python-Bibliothek schließen. Unser Werkzeug bindet frühere Schätzungen für LWE aus dem LWE Estimator mit ein und ergänzt neue Angriffsschätzungen für SIS. In dieser Arbeit geben wir einen Überblick über die LWE- und SIS-Probleme und beschreiben verschiedene Algorithmen, die zu ihrer Lösung verwendet werden können. Für LWE lassen sich die Algorithmen in drei Kategorien aufteilen: direkte Lösungsstrategien, Angriffe über eine Reduktion auf das Bounded-Distance-Decoding Problem (BDD), auch Primal Attacks genannt, und Angriffe über SIS, das "duale" Problem zu LWE. In die Kategorie von direkten Angriffen fallen der Meet-in-the-Middle Algorithmus (MITM) und ein Algorithmus nach Arora und Ge. Beide Algorithmen haben eine sehr lange Laufzeit und sind daher in der Praxis von geringer Relevanz. Allerdings kann MITM sehr schnell abgeschätzt werden und wird deshalb in unserer Bibliothek als Vorfilter verwendet, falls er in der Konfiguration ausgewählt wird. Zur Lösung von BDD kann das Problem weiter auf das unique Shortest Vector Problem (uSVP) reduziert werden, welches über sogenannte Gitterreduktionsalgorithmen (engl. lattice reduction) gelöst werden kann. Der beste Gitterreduktionsalgorithmus ist der Block-Korkin-Zolatarev Algorithmus (BKZ), der intern einen SVP-Löser in kleineren Dimensionen verwendet. Um die Laufzeit von BKZ zu schätzen, benötigen wir Kostenmodelle der SVP-Löser. Wir stellen eine Übersicht der aktuellen Befunde aus der Literatur vor und fassen diese in unserem Werkzeug zusammen. Ein weiterer Algorithmus in der BDD Kategorie ist der Decoding Angriff, der Gitterreduktion mit einem Dekodierteil kombiniert. In unseren Tests liefern die Schätzungen für den Primal uSVP Algorithmus die besten Laufzeitresultate mit einer sehr kleinen Laufzeit. Primal uSVP ist deshalb Teil unserer Standardkonfiguration. Der Blum-Kalai-Wasserman Algorithmus (BKW) ist ein kombinatorischer Algorithmus, der LWE über SIS lösen kann. Eine Variante davon wird vom LWE Estimator geschätzt und erzielt gute Ergebnisse. Allerdings benötigt die Schätzung längere Zeit. Wir verwenden eine einfachere Variante zur Lösung von SIS Problem in unserem Werkzeug, die jedoch im Vergleich zu einem besseren dualen Angriff zu deutlich höheren Kostenschätzungen führt. Deshalb ist nur der duale Angriff Teil unsrer Standardkonfiguration für SIS. Der duale Angriff kann auch auf LWE angewandt werden und hat ebenfalls niedrige Laufzeitkosten, jedoch schließt er in unseren Tests nicht so gut wie der Primal uSVP Algorithmus ab.

Das Herzstück unseres Werkzeugs ist eine generische Parametersuchfunktion, die sowohl einfach zu bedienen ist als auch umfangreiche Anpassungen ermöglicht. Es ist möglich, primitive Bausteine aus komplexeren Anwendungen zu kombinieren und auf eine kompakte und übersichtliche Weise der Suchfunktion zu übergeben. Die Suchfunktion schätzt die Sicherheitsstufe von Probleminstanzen eines gegebenen Parametersatzes und endet, sobald ein Parametersatz, für den alle spezifizierten Probleminstanzen sicher sind, gefunden wurde. Um eine effizientere Suche zu gewährleisten, priorisieren wir Schätzungsfunktionen, die schnell ein Ergebnis liefern und niedrigere Kosten ausgeben, analog für Kostenmodelle. Wir definieren Klassen für alle gängigen Problemvarianten und zusätzlich Klassen, um statistisch sichere Probleminstanzen zu erzeugen. Weiterhin unterstützt unser Werkzeug verschiedene p-Normen, Normabschätzungen und Verteilungen. Zuletzt zeigen wir die Funktionalität unserer Bibliothek anhand einiger Anwendungsbeispiele.