Weiterentwicklung gitterbasierter Nullstellenverfahren mit Anwendungen für RSA, Faktorisierung und in der Codierungstheorie, Konstruktion beweisbar sicherer kryptographischer Primitiven unter gitterbasierten Annahmen

• Applicant: Professor Dr. Alexander May
• Subject Area: Theoretical Computer Science
• Term: from 2007 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 52118229

Kryptographie liefert die Basistechnologie für die Welt der digitalen Kommunikation. Ohne kryptographische Public-Key Verfahren wären sichere E-Commerce Anwendungen, automatische Software-Updates oder sicherer EMail- Verkehr undenkbar. In der kommerziellen Praxis wird hauptsächlich das RSA Public-Key Kryptosystem eingesetzt, dessen Sicherheit auf dem Faktorisierungsproblem beruht. Daher ist es von entscheidender Bedeutung, sowohl die Sicherheit von RSA zu evaluieren als auch praktikable Alternativen zum RSA System vorzuschlagen. Das Projekt befasst sich mit Methoden zur Sicherheitsanalyse von RSA und dem zugrundeliegenden Faktorisierungsproblem. Die Ziele des Projektes lassen sich in zwei Bereiche aufteilen: 1. Sicherheitsanalyse: Um ein Public-Key Kryptosysteme wie RSA anzugreifen, wird dieses in Form von Polynomgleichungen modelliert. Eine Nullstellenbestimmung der Polynome liefert dann die geheimen Parameter des Systems. Zur effizienten Ermittlung der Nullstellen sollen gitterbasierte L¨osungsverfahren zum Einsatz kommen. Anwendungsbeispiele sind insbesondere Relaxierungen des Faktorisierungsproblems und RSA-Varianten. Das Projekt erforscht aber auch weitere Anwendungsmöglichkeiten in verwandten Bereichen, wie z.B. der Codierungstheorie.2. Algorithmische Weiterentwicklung von Nullstellenverfahren: Gitterbasierte Verfahren zum Lösen von Polynomgleichungen sind dazu geeignet, betragsmäßig kleine Nullstellen effizient zu bestimmen. Ziel des Projektes ist es, optimale Schranken für die Größe der Nullstellen zu erreichen und die Optimalität unter geeigneten Annahmen zu beweisen. Weiterhin werden Kriterien gesucht, um eine optimale Kombination von Polynomgleichungen eines Gleichungssystems zu erreichen. Unter Verwendung der entwickelten Schrankenanalyse werden beweisbar sichere kryptographische Verfahren entwickelt, deren Sicherheit auf der Schwierigkeit des Lösens von polynomiellen Gleichungssystemen jenseits der erreichbaren Schranken beruht.

• DFG Programme: Research Grants