Schnellere Algorithmen für harte Probleme wie Subset Sum, Syndromdekodierung in linearen Codes und dem Kürzesten Vektor Problem mit zahlreichen Anwendungen in der Komplexitätstheorie und der Kryptographie

• Antragsteller: Professor Dr. Alexander May
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2011 bis 2014
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 206738461

2010 stellten Howgrave-Graham und Joux eine neue Representationstechnik zum Lösen des Subset Sum Problems vor. Dabei wird eine eindeutige Lösung mit Hilfe von exponentiell vielen Representationen dargestellt. Unter diesen Darstellungen wird wiederum eine eindeutige Lösung mit gewissen Eigenschaften berechnet. Interessanterweise liefert dieses Aufblasen und Kürzen des Suchraums beim Subset Sum Problem eine signifikante Verbesserung der Zeitkomplexität von ∂(20.5n) auf ∂(20.337n).Unser Ziel ist eine generelle Analyse der Representationstechnik, die einen generischen Einsatz der Technik als allgemeines algorithmisches Tool erlaubt. Unsere erste Anwendung der Methode liefert bereits eine Verbesserung des besten bekannten Algorithmus zum Berechnen des Dekodierproblems in allgemeinen linearen Codes. Weitere wichtige Anwendungen der Representationstechnik sehen wir u.a. bei der Berechnung kürzester Vektoren in Gittern und bei einem neuen kombinatorischen Algorithmus für ein Problem in zyklischen Gittern, das dem NTRU Kryptosystem zugrunde liegt.Wir erwarten, dass eine hinreichend generische Formulierung der Representationstechnik viele weitere Anwendungen bei der Algorithmenkonstruktion für harte kombinatorische Suchprobleme innerhalb des SPP Algorithm Engineering liefert.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1307: Algorithm Engineering