Treffer: A tool for the estimation of lattice parameters ; Ein Werkzeug zur Abschätzung von Gitterparametern

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 ...