Parallelizing and implementing algorithms for cryptanalysis on graphics cards

• Applicant: Professor Dr. Johannes Buchmann
• Subject Area: Theoretical Computer Science
• Term: from 2010 to 2013
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 181429555

Public-Key-Kryptographie ist unverzichtbar für unsere heutige IT-Infrastruktur. Im Jahr 1994 zeigte Schor, dass alle derzeit verwendeten Kryptosysteme - RSA, DSA, und ECDSA - unsicher werden, sobald große Quantencomputer gebaut werden können. Forscher gehen davon aus, dass große Quantencomputer in den nächsten 20-30 Jahren realisiert werden. Zwei der zahlreichen Kandidaten, die den Platz von RSA, DSA, und ECDSA in der Ära der Quantencomputer einnehmen können, sind Kryptosysteme basierend auf Gitterproblemen und dem Problem multivariate Gleichungssysteme zu lösen. Während gitterbasierte Kryptosysteme in der Regel beweisbar sicher sind, ermöglichen multivariate Kryptosysteme sehr effiziente Implementierungen, auch auf Ressourcen begrenzten Geräten. Der Sicherheitsparameter eines Kryptosystems wird üblicherweise mittels des besten Algorithmus zur Lösung des zugrunde liegenden Problems und einer Extrapolationsheuristik bestimmt. Es muss verhindert werden, dass Angreifer Zugang zu effizienteren Algorithmen haben, sonst könnten sie das Verfahren auch bei Verwendung vermeintlich sicherer Sicherheitsparameter brechen. Die Verbesserung der Effizienz solcher Algorithmen und die Einbeziehung neuer Technologien ist daher von größter Bedeutung. Dieses Projekt liefert verbesserte Algorithmen für die Suche nach kurzen Gittervektoren und das Lösen von multivariaten Gleichungssystemen und wird somit einen Beitrag für die Bestimmung der Sicherheitsparameter für gitterbasierte und multivariate Kryptosysteme leisten. Wir entwickeln parallelisierbare Algorithmen zum Lösen beider Probleme und implementieren sie auf Grafikkarten. Grafikkarten sind sehr gut für die Kryptanalyse geeignet, weil tausende von Prozessen parallel ausgeführt werden können und daher die Laufzeit drastisch reduziert werden kann.

• DFG Programme: Research Grants
• International Connection: Taiwan
• Participating Persons: Privatdozent Dr. Chen-Mou Cheng; Dr. Erik Dahmen; Professor Bo-Yin Yang, Ph.D.