Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Institut für Informatik

Die Verteidigung findet auch digital per Zoom statt. Eine Zoom-Einladung finden Sie hier. (nur mit Informatik-Account)

Abstract:

Diese Arbeit untersucht die Sicherheit des neuen NIST-Standards für asymmetrische Kryptografie gegen Schwachstellen durch klassische Gitterreduktionsalgorithmen. Der Modular-Lattice-Based Key-Encapsulation-Mechanismus (ML-KEM) Standard basiert auf dem mathematischen Learning with Errors (LWE) Problem. Wir erzeugen LWE-Instanzen und reduzieren sie auf das Problem des kürzesten Vektors (SVP). Anschließend wird die Gitterbasis mit dem LLL- oder BKZ-Algorithmus reduziert, um
das SVP zu lösen. Wir untersuchen somit die Sicherheit einer LWE Instanz für verschiedene Parameter.

In this work, we study the security of the latest National Institute of Standards and Technology asymmetric cryptography standard, the Modular-Lattice-Based Key-Encapsulation-Mechanism (ML-KEM) published in 2024. This standard is based on the mathematical learning with error (LWE) problem, a system of linear equations over a ring where a perturbation is added to one side of the equation. This problem can be embedded into an instance of the shortest vector problem (SVP). We use classical lattice reduction algorithms such as the Lenstra-Lenstra-Lovasz (LLL) and Block Korkine–Zolotarev (BKZ) algorithms to reduce the lattice base and compute approximate solutions of the SVP. We study for which parameters of the LWE instance these algorithms solve the shortest vector problem so that we can extract the private key of the LWE instance.