Effiziente Algorithmen Neue Verschlüsselungstechniken dank schwerer mathematischer Probleme

Der Start in den Urlaub beginnt für viele Menschen mit einer Herausforderung: Wie sollen all die Sachen in den Koffer, die Tasche oder den Rucksack passen? Mathematisch gesehen ist es tatsächlich nicht trivial, einen Algorithmus zu finden, der einen Rucksack so vollpackt, dass die Gegenstände darin zusammengenommen einen möglichst hohen Nutzen erfüllen.

„Die Entscheidung, eine Zahnbürste mitzunehmen, fällt sicher leicht“, sagt Prof. Dr. Eike Kiltz vom Lehrstuhl für Kryptographie. „Sie ist klein und hat einen hohen Nutzen. Aber was ist mit dem Föhn? Nehme ich den auch mit?“

Rucksackproblem seit über 100 Jahren ungelöst

Hinter dem Rucksack-Beispiel steckt ein schweres mathematisches Problem, für das Wissenschaftler seit über hundert Jahren keine effiziente Lösung gefunden haben. Allerdings wäre der Rucksack in ihrer Variante des Problems bedeutend größer als im wahren Leben.

Eike Kiltz beschäftigt sich mit genau solchen schweren Problemen der Mathematik. Basierend auf ihnen entwickelt er neue Verschlüsselungs- und Authentifizierungsverfahren, die quasi nicht zu knacken sind. „Wenn jemand es schaffen würde, die Verfahren zu brechen, könnte er auch ein mathematisches Problem lösen, an dem die schlausten Köpfe der Welt seit 100 oder 200 Jahren arbeiten“, vergleicht Kiltz.

Mit diesem Ansatz wählt der Wissenschaftler eine ganz andere Herangehensweise als üblich. Normalerweise werden neue kryptografische Verfahren nach dem Ad-hoc-Prinzip konzipiert. Kiltz erklärt: „Jemand denkt sich ein Verfahren aus, dann versuchen andere, es zu brechen. Schaffen sie es nicht, heißt es, dass es sicher ist.“

Die Bochumer Mathematiker basieren ihre Sicherheitsalgorithmen stattdessen auf Probleme, die schon seit ein paar hundert Jahren ungelöst sind. Die Algorithmen gestalten sie dabei so effizient, dass sie sich in Kleinstgeräte implementieren lassen, zum Beispiel in einen elektronischen Garagentoröffner. „Man hat lange gedacht, dass das nicht geht, weil die Chips in diesen Geräten nicht leistungsstark genug sind“, so Kiltz. 2011 veröffentlichte seine Gruppe jedoch ein Prototyp-Verfahren, das genau das konnte.

Effiziente Algorithmen für Kleinstgeräte

Nun arbeiten die Forscher daran, die Verfahren noch effizienter und für neue kryptografische Fragestellungen nutzbar zu machen. Großes Potenzial räumen sie dabei der sogenannten gitterbasierten Kryptografie ein. Sie fußt auf folgendem schweren mathematischen Problem. Stellen wir uns ein Gitter vor, das an einer Stelle einen Nullpunkt besitzt. Überall dort, wo sich zwei Linien kreuzen, liegen weitere Punkte, die wir Kreuzungspunkte nennen. Frage: Welcher Kreuzungspunkt liegt am nächsten beim Nullpunkt?

Für ein zweidimensionales Gitter ist dieses Problem leicht zu lösen; auch in einem dreidimensionalen Gitter könnten wir die Antwort relativ schnell finden. Aber je mehr Dimensionen hinzukommen, desto schwieriger wird die Aufgabe. Mit rund 500 Dimensionen lässt sich das Problem nicht mehr effizient lösen.

Je nachdem wie man die Parameter wählt, fällt das Gitterproblem in die Klasse der sogenannten NP-vollständigen Probleme. Diese umfasst die schwersten Probleme der Mathematik, zu denen auch das oben beschriebene Rucksackproblem gehört sowie eine Vielzahl weiterer Vertreter. Sie wären eine ideale Grundlage für möglichst sichere neue Verschlüsselungstechniken.

Für ihre Arbeit wählen die Mathematiker jedoch eine leicht vereinfachte Version des Gitterproblems. Die Aufgabe lautet dann nicht: Finde denjenigen Kreuzungspunkt im Gitter, der am nächsten zum Nullpunkt liegt. Sondern: Finde einen beliebigen Kreuzungspunkt, der in einem engen Radius um den Nullpunkt liegt.

Die Wissenschaftler testen dabei verschiedene Parameter, die das Gitterproblem ein wenig leichter oder schwerer machen, und versuchen, darauf basierend einen kryptografischen Algorithmus zu erarbeiten, der sich auch auf kleinen Geräten implementieren lassen würde.

Fast im Endstadium

Gitterbasierte Verfahren zur Authentifizierung haben die RUB-Forscher schon relativ weit entwickelt. „Wir sind fast im Endstadium“, fasst Eike Kiltz zusammen.

Authentifizierungsprotokolle werden immer dann gebraucht, wenn ein Objekt seine Identität beweisen muss, zum Beispiel der elektronische Garagenöffner. Schließlich muss sichergestellt sein, dass ein bestimmter Öffner nur das zugehörige Tor entriegelt. Im Protokoll könnte das so funktionieren: Der Öffner authentifiziert sich beim Garagentor, indem er beweist, dass er ein internes Geheimnis kennt, zum Beispiel einen Kreuzungspunkt nahe dem Nullpunkt im Gitter.

Kryptografische Protokolle sind aber nicht nur für die Authentifizierung nötig; auch Verschlüsselungen sind im Alltag ständig im Einsatz. Wenn zum Beispiel zwei Personen eine geheime Botschaft über das Internet austauschen wollen oder eine Smartcard mit dem Kartenlesegerät kommunizieren möchte, muss die Nachricht verschlüsselt sein, damit Dritte sie nicht mitlesen können.

Gitterbasierte Verfahren vielfältig einsetzbar

Für diesen Zweck könnten gitterbasierte Verfahren ebenfalls nützlich sein. Allerdings sind die darauf basierenden Verschlüsselungsprotokolle derzeit noch nicht effizient genug, um sie auf kleinen Geräten zu implementieren. Ein paar Jahre Arbeit müssten sie noch investieren, schätzt Eike Kiltz.

Mit einer eierlegenden Wollmilchsau vergleicht der Mathematiker die gitterbasierten Verfahren, weil sie so vielfältig einsetzbar sind. Sie taugen sowohl zur Verschlüsselung als auch zur Authentifizierung, funktionieren auf kleinen Geräten und würden sogar vor Angriffen durch Quantencomputer schützen, falls es diese eines Tages gäbe.

Neben ihrer anwendungsorientierten Arbeit betreiben die RUB-Mathematiker auch Grundlagenforschung. Sie versuchen, die Gitter mathematisch zu verstehen. Was macht das Gitterproblem so einzigartig schwer, dass alle bisherigen Techniken bei der Lösung versagen? Das ist eine der Fragen, die die Forscher umtreibt. Die Erkenntnisse könnten eines Tages in die anwendungsorientierte Arbeit einfließen.