Kryptanalyse von Post-Quantum Gitter- und Code-basierten Primitiven: Praktische Rekorde und theoretische Verbesserungen.

• Antragsteller: Professor Dr. Alexander May
• Fachliche Zuordnung: Sicherheit und Verlässlichkeit, Betriebs-, Kommunikations- und verteilte Systeme
• Förderung: Förderung seit 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 465120249

Unser Projekt befasst sich mit Kryptanalyse von gitter- und codebasierten Post-Quanten Kryptosystemen. Unsere Forschungsfragestellungen umfassen drei Aspekte: (1) Kryptanalyse des NTRU Kryptosystems als wichtigster Vertreter praktischer gitterbasierter Verschlüsselung(2) Kryptanalyse des McEliece Kryptosystems als wichtigster Vertreter codebasierter Verschlüsselung (3) Konstruktion von Gittern mit großer Kissing Number.Wir betrachten das NTRU Verfahren als den historisch etabliertesten gitterbasierten Vertreter, der trotzdem kryptanalytisch nur sehr unzureichend verstanden ist. Ziel unserer Forschung ist eine gründliche Untersuchung der Sicherheitsgarantien der NTRU Annahme mittels(1a) Verbesserung von kombinatorischen Angriffen wie Meet-in-the-Middle und BKW,(1b) Durchführung von Angriffen auf mittlere und hohe Sicherheitslevel von NTRU Parametern,(1c) Entwicklung von Quantenspeedups für die erzielten Verbesserung.Bezüglich des McEliece Kryptosystems (2a) integrieren wir alle theoretischen Verbesserungen der letzten Dekade beim Dekodieren linearer Codes in eine Open-Source Implementierung.(2b) führen wir umfangreiche Angriffe durch (CPU und GPU), um zahlreiche derzeit existierende Dekodierrekorde zu brechen.(2c) entwickeln wir einen öffentlich zugänglichen McEliece Security Estimator sowohl für Forscher als auch für praktische Anwender. Unsere Forschung zu großen Kissing Numbers von Gittern besitzt Anwendungen sowohl in der Theorie als auch in der Praxis. Auf der theoretischen Seite wollen wir die Frage klären, ob kürzlich entwickelte Konstruktionen einen optimalen Exponenten liefern. Diese Fragestellung hat praktische Anwendungsaspekte in der Kryptanalyse, da Gitter mit großer Kissing Number die Konstruktion guter sphärischer Codes ermöglichen, die wiederum in den schnellsten Algorithmen für das Kürzeste-Vektor Problem eingesetzt werden - dem wichtigen Tool für die Kryptanalyse gitterbasierter Verfahren. Wir adressieren die kryptanalytische Anwendbarkeit von Gitter mit großer Kissing Number, indem wir deren effiziente Dekodierbarkeit untersuchen.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Russische Föderation
• Partnerorganisation: Russian Science Foundation, bis 3/2022
• Kooperationspartnerin: Dr. Elena Kirshanova, bis 3/2022