Master Thesis MSTR-2025-25

BibliographyHellmich, Josef Aron: Klassische Reduzierbarkeit von GapSVP auf (Ring-)LWE.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 25 (2025).
53 pages, german.
Abstract

GapSVP ist eines der fundamentalen Probleme in der gitterbasierten Kryptographie. In der vorliegenden Masterarbeit untersuchen wir, inwiefern sich GapSVP in klassischer Weise auf Varianten des LWE-Problems reduzieren lässt. Hierzu analysieren wir eine bestehende klassische Reduktion einer Variante von GapSVP auf die Standardversion von LWE und diskutieren ihre Qualität kritisch. Hierbei zeigen wir, dass weiterer Forschungsbedarf hinsichtlich einer entsprechenden klassischen Reduktion besteht. Darüber hinaus beweisen wir, dass GapSVP auf Idealgittern (den Gittern, die von Ring-LWE verwendet werden) ein unsicheres Problem ist und leiten daraus ab, dass es keine sinnvolle klassische Reduktion von GapSVP auf Ring-LWE geben kann.

Department(s)University of Stuttgart, Institute of Information Security
Superviser(s)Küsters, Prof. Ralf; Reisert, Dr. Pascal
Entry dateAugust 13, 2025
New Report   New Article   New Monograph   Computer Science