Faster algorithms for hard problems like subset sum, syndrome decoding in linear codes and the shortest vector problem, with various applications in complexity theory and cryptography

点击翻译按钮获取中文摘要

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.