Wie lassen sich schwierige Probleme am besten lösen? Das ist die Kernfrage eines Teilgebiets der Informatik namens Computational Complexity Theory. Die Frage ist schwer zu beantworten, aber wenn man sie umdreht, wird es einfacher. Der schlechteste Ansatz ist fast immer Versuch und Irrtum, bei dem es darum geht, mögliche Lösungen auszuprobieren, bis eine funktioniert. Aber für manche Probleme scheint es einfach keine Alternativen zu geben – der schlechteste Ansatz ist auch der beste.

Forscher fragten sich schon lange, ob das jemals wirklich der Fall sei, sagte er Rahul Ilango, ein Doktorand, der Komplexitätstheorie am Massachusetts Institute of Technology studiert. „Man könnte sich fragen: ‚Gibt es Probleme, bei denen Rate-and-Check optimal ist?‘“

Komplexitätstheoretiker haben viele Rechenprobleme untersucht, und selbst die schwierigen Probleme geben oft zu, dass es eine Art cleveres Verfahren oder einen Algorithmus gibt, der das Finden einer Lösung ein wenig einfacher macht als reines Ausprobieren. Zu den wenigen Ausnahmen gehören sogenannte Komprimierungsprobleme, bei denen es darum geht, die kürzeste Beschreibung eines Datensatzes zu finden.

Aber im vergangenen November trafen sich zwei Forschergruppen unabhängig entdeckt ein weiterer Algorithmus für Komprimierungsprobleme – einer, der etwas schneller ist als die Prüfung aller möglichen Antworten. Der neue Ansatz basiert auf der Anpassung eines Algorithmus, der vor 25 Jahren von Kryptographen erfunden wurde, um ein anderes Problem anzugehen. Es gibt nur eine Einschränkung: Sie müssen den Algorithmus an die Größe Ihres Datensatzes anpassen.

„Das sind wirklich schöne und wichtige Ergebnisse“, sagte er Erich Allender, ein theoretischer Informatiker an der Rutgers University.

Härte definieren

Die neuen Ergebnisse sind die neuesten zur Untersuchung einer Frage, die erstmals in der Sowjetunion untersucht wurde, lange vor dem Aufkommen der Komplexitätstheorie. „Bevor ich in die Grundschule ging, haben die Leute in Russland das formuliert“, sagte Allender.

Das spezifische Rechenproblem, das diese sowjetischen Forscher untersuchten und das Problem der minimalen Schaltkreisgröße genannt wird, ähnelt einem Problem, mit dem Entwickler von Computerhardware ständig konfrontiert sind. Wenn Sie vollständige Spezifikationen zum Verhalten einer elektronischen Schaltung erhalten, können Sie dann die einfachste Schaltung finden, die diese Aufgabe erfüllt? Niemand wusste, wie man dieses Problem ohne „perebor“ lösen könnte – ein russisches Wort, das in etwa „erschöpfende Suche“ bedeutet.

Das Problem der minimalen Schaltungsgröße ist ein Beispiel für ein Komprimierungsproblem. Sie können das Verhalten einer Schaltung mit einer langen Bitfolge – Nullen und Einsen – beschreiben und dann fragen, ob es eine Möglichkeit gibt, dasselbe Verhalten mit weniger Bits zu reproduzieren. Die Überprüfung aller möglichen Schaltungslayouts würde Zeit in Anspruch nehmen, die exponentiell mit der Anzahl der Bits in der Zeichenfolge zunimmt.

Diese Art von exponentiellem Wachstum ist das bestimmende Merkmal eines schwierigen Rechenproblems. Aber nicht alle schwierigen Probleme sind gleich schwierig – einige verfügen über Algorithmen, die schneller sind als eine umfassende Suche, obwohl ihre Laufzeiten immer noch exponentiell ansteigen. In modernen Begriffen stellt sich die Frage, ob solche Algorithmen für Komprimierungsprobleme existieren.

Im Jahr 1959 behauptete ein bekannter Forscher namens Sergey Yablonsky, er habe bewiesen, dass eine umfassende Suche wirklich der einzige Weg sei, das Problem der minimalen Schaltkreisgröße zu lösen. Aber sein Beweis hinterließ einige Lücken. Einige Forscher bemerkten damals die Mängel, aber Yablonsky war einflussreich genug, um die meisten anderen davon abzuhalten, sich mit der Perebor-Frage zu befassen.

In den folgenden Jahrzehnten befassten sich nur wenige Forscher mit Kompressionsproblemen, und die Perebor-Frage war größtenteils als Fußnote in der Vorgeschichte der Komplexitätstheorie bekannt. Die Frage erlangte erst kürzlich große Aufmerksamkeit, nachdem Forscher einen merkwürdigen Zusammenhang zwischen Komprimierungsproblemen und den Grundlagen der Kryptographie entdeckt hatten.

Einbahnstraße

Die moderne Kryptographie nutzt schwierige Rechenprobleme, um geheime Nachrichten zu schützen. Aber Rechenhärte ist nur dann nützlich, wenn sie asymmetrisch ist – wenn es schwierig ist, codierte Nachrichten zu entschlüsseln, aber nicht schwierig, Nachrichten überhaupt zu verschlüsseln.

In jedem Kryptografieschema ist der Ursprung dieser Asymmetrie ein mathematisches Objekt, das als Einwegfunktion bezeichnet wird und Eingabebitfolgen in Ausgabefolgen gleicher Länge umwandelt. Bei einer Eingabe für eine Einwegfunktion ist es einfach, die Ausgabe zu berechnen, aber bei einer Ausgabe ist es schwierig, die Funktion umzukehren – das heißt, sie zurückzuentwickeln und die Eingabe wiederherzustellen.

„Kryptografen hätten gerne sehr, sehr effizient berechenbare Einwegfunktionen, die wirklich sehr, sehr schwer umzukehren sind“, sagte Allender. Viele mathematische Funktionen scheinen über diese Eigenschaft zu verfügen, und die Schwierigkeit, diese Funktionen umzukehren, ergibt sich aus der scheinbaren Schwierigkeit, verschiedene Rechenprobleme zu lösen.

Leider wissen Kryptographen nicht genau, ob eine dieser Funktionen wirklich schwer umzukehren ist – tatsächlich ist es möglich, dass echte Einwegfunktionen nicht existieren. Diese Unsicherheit bleibt bestehen, weil Komplexitätstheoretiker dies getan haben kämpfte 50 Jahre lang um zu beweisen, dass scheinbar schwierige Probleme wirklich schwierig sind. Wenn dies nicht der Fall ist und Forscher superschnelle Algorithmen für diese Probleme entdecken würden, wäre das für die Kryptographie katastrophal – so, als würden schnell fahrende Autos plötzlich in einer Einbahnstraße in beide Richtungen geleitet.

Auch wenn ein umfassendes Verständnis der Rechenhärte noch immer schwer zu erreichen ist, haben Kryptographen kürzlich aufregende Fortschritte auf dem Weg zu einer einheitlichen Theorie von Einwegfunktionen gemacht. Ein großer Schritt wurde im Jahr 2020 getan, als der Kryptograf der Universität Tel Aviv Rafael Pass und sein Doktorand Yanyi Liu bewiesen, dass es Einwegfunktionen gibt eng verbunden zu einem spezifischen Komprimierungsproblem, das als zeitbegrenztes Kolmogorov-Komplexitätsproblem bezeichnet wird.

Wenn dieses eine Problem für die meisten Eingaben wirklich schwer zu lösen ist, dann liefert das Ergebnis von Pass und Liu ein Rezept für die Konstruktion einer nachweislich harten Einwegfunktion – eine, die garantiert sicher ist, selbst wenn sich andere Rechenprobleme als weitaus einfacher erweisen als die Forscher erwartet hatten. Wenn es jedoch einen schnellen Algorithmus zur Lösung des zeitbegrenzten Kolmogorov-Komplexitätsproblems gibt, ist die Kryptographie zum Scheitern verurteilt und jede Funktion kann leicht invertiert werden. Eine Einwegfunktion, die auf der Härte dieses Problems basiert, ist die sicherste Funktion, die möglich ist – eine Einwegfunktion, die sie alle beherrscht.

Auf Datenstrukturen aufbauen

Die Entdeckung von Pass und Liu war das neueste Kapitel einer langen Forschungsreihe, die die Komplexitätstheorie nutzt, um die Grundlagen der Kryptographie besser zu verstehen. Aber es schlug auch eine Möglichkeit vor, diese Beziehung umzukehren: Die Äquivalenz zwischen dem zeitbegrenzten Kolmogorov-Komplexitätsproblem und der Funktionsinversion impliziert, dass Erkenntnisse über eines der beiden Probleme mehr über das andere verraten können. Kryptographen untersuchen seit Jahrzehnten Funktionsinversionsalgorithmen, um die Schwachstellen ihrer Verschlüsselungsmethoden besser zu verstehen. Forscher begannen sich zu fragen, ob diese Algorithmen helfen könnten, uralte Fragen der Komplexitätstheorie zu beantworten.

Wie viele Rechenprobleme kann die Funktionsinversion durch eine umfassende Suche gelöst werden. Fügen Sie bei gegebener Ausgabezeichenfolge einfach alle möglichen Eingaben in die Funktion ein, bis Sie diejenige gefunden haben, die die richtige Antwort liefert.

Im Jahr 1980 begann der Kryptograph Martin Hellman zu untersuchen, ob es möglich sei, es noch besser zu machen – die gleiche Frage, die die sowjetischen Mathematiker Jahrzehnte zuvor zu Komprimierungsproblemen gestellt hatten. Hellmann entdeckt Ja, das ist möglich – solange Sie bereit sind, im Vorfeld zusätzliche Arbeit zu leisten und mathematische Objekte, sogenannte Datenstrukturen, zu verwenden.

Eine Datenstruktur ist im Wesentlichen eine Tabelle, die Informationen über die zu invertierende Funktion speichert, und der Aufbau einer solchen erfordert die Berechnung der Ausgaben der Funktion für bestimmte strategisch ausgewählte Eingaben. All diese Berechnungen „könnten sehr lange dauern“, sagte er Ryan Williams, ein Komplexitätstheoretiker am MIT. „Aber die Idee ist, dass dies ein für alle Mal geschieht.“ Wenn Sie versuchen, dieselbe Funktion bei vielen verschiedenen Ausgaben umzukehren – beispielsweise um viele verschiedene Nachrichten zu dekodieren, die auf die gleiche Weise verschlüsselt sind – kann es sich lohnen, diese Arbeit im Voraus durchzuführen.

Das Speichern dieser zusätzlichen Informationen erfordert natürlich Speicherplatz. Wenn Sie diese Strategie also auf die Spitze treiben, könnten Sie am Ende ein schnelles Programm erhalten, das auf keinen Computer passt. Hellman entwarf eine clevere Datenstruktur, die es seinem Algorithmus ermöglichte, die meisten Funktionen etwas schneller als bei einer erschöpfenden Suche zu invertieren, ohne zu viel mehr Platz zu beanspruchen. Im Jahr 2000 dann die Kryptografen Amos Fiat und Moni Naor verlängert Hellmans Argumente für alle Funktionen.

Nach dem Durchbruch von Pass und Liu im Jahr 2020 waren diese alten Ergebnisse plötzlich neu relevant. Der Fiat-Naor-Algorithmus könnte beliebige Funktionen schneller invertieren als eine erschöpfende Suche. Könnte es auch bei Komprimierungsproblemen funktionieren?

Aus Uniform

Die ersten Forscher, die diese Frage stellten, waren Komplexitätstheoretiker Raul Santhanam der Universität Oxford und sein Doktorand Hanlin Ren. Sie taten dies in einem 2021 Papier Dies beweist, dass Komprimierungsprobleme und Funktionsinversion noch stärker miteinander verknüpft sind, als die Forscher angenommen hatten.

Pass und Liu hatten bewiesen, dass, wenn das zeitbeschränkte Kolmogorov-Komplexitätsproblem schwierig ist, auch die Funktionsinversion schwierig sein muss und umgekehrt. Aber Probleme können schwierig sein und dennoch Lösungen zulassen, die etwas besser sind als eine erschöpfende Suche. Santhanam und Ren zeigten, dass ein enger Zusammenhang zwischen der Notwendigkeit einer umfassenden Suche für ein Problem und der Notwendigkeit für ein anderes Problem besteht.

Ihr Ergebnis hatte unterschiedliche Auswirkungen auf zwei große Klassen von Algorithmen, die von Forschern häufig untersucht werden und als „einheitliche“ und „ungleichmäßige“ Algorithmen bezeichnet werden. Einheitliche Algorithmen folgen für jede Eingabe dem gleichen Verfahren – ein einheitliches Programm zum Sortieren von Zahlenlisten funktioniert beispielsweise unabhängig davon, ob die Liste 20 oder 20,000 Einträge enthält. Uneinheitliche Algorithmen verwenden stattdessen unterschiedliche Verfahren für Eingaben unterschiedlicher Länge.

Die vom Fiat-Naor-Algorithmus verwendeten Datenstrukturen sind immer auf eine bestimmte Funktion zugeschnitten. Um eine Funktion zu invertieren, die eine 10-Bit-Zeichenfolge verschlüsselt, benötigen Sie eine andere Datenstruktur als die, die Sie zum Invertieren einer Funktion benötigen, die eine 20-Bit-Zeichenfolge verschlüsselt, selbst wenn die Verschlüsselung auf ähnliche Weise erfolgt. Das macht Fiat-Naor zu einem uneinheitlichen Algorithmus.

Das Ergebnis von Santhanam und Ren deutete darauf hin, dass es möglich sein könnte, den Fiat-Naor-Algorithmus in einen Algorithmus zur Lösung von Komprimierungsproblemen umzuwandeln. Die Anpassung des Algorithmus von einem Problem an das andere war jedoch nicht einfach, und sie gingen der Frage nicht weiter nach.

Pass kam ein Jahr später auf die gleiche Idee, nachdem er gehört hatte, wie Fiat auf einem Workshop, bei dem Naors Beiträge zur Kryptographie gefeiert wurden, einen Vortrag über den klassischen Algorithmus hielt. „Diese Idee, die Funktionsinversion zu verwenden, hatte ich seitdem im Hinterkopf“, sagte er. Später begann er gemeinsam mit Forschern der Universität Tel Aviv ernsthaft an dem Problem zu arbeiten Noam Mazor.

In der Zwischenzeit wurde Ilango nach Gesprächen mit anderen Forschern, darunter Santhanam, bei einem Besuch am Simons Institute for the Theory of Computing in Berkeley, Kalifornien, dazu inspiriert, das Problem anzugehen. „Es entstand aus einem dieser sehr zufälligen Gespräche, bei denen man einfach mit Dingen herumwirft“, sagte Santhanam. Ilango schloss sich später mit Williams zusammen Shuichi Hirahara, ein Komplexitätstheoretiker am National Institute of Informatics in Tokio.

Der schwierige Teil bestand darin, herauszufinden, wie die Datenstruktur im Herzen des Fiat-Naor-Algorithmus in einen uneinheitlichen Algorithmus zur Lösung von Komprimierungsproblemen eingebettet werden kann. Es gibt ein Standardverfahren für diese Art der Einbettung, aber es würde den Algorithmus verlangsamen und seinen Vorteil gegenüber einer umfassenden Suche zunichtemachen. Die beiden Teams fanden cleverere Möglichkeiten, die Fiat-Naor-Datenstruktur zu integrieren, und erhielten Algorithmen für Komprimierungsprobleme, die bei allen Eingaben funktionierten und schneller blieben als eine umfassende Suche.

Die Details der beiden Algorithmen unterscheiden sich geringfügig. Die Methode von Ilango und seinen Co-Autoren ist schneller als eine erschöpfende Suche, selbst wenn man die Suche auf die einfachsten Möglichkeiten beschränkt, und sie gilt für alle Komprimierungsprobleme – zeitbegrenzte Kolmogorov-Komplexität, das Problem der minimalen Schaltkreisgröße und viele andere. Die Grundidee war jedoch bei beiden Algorithmen dieselbe. Die Techniken der Kryptographie hatten sich in diesem neuen Bereich bewährt.

Inversionskonvergenz

Der neue Beweis für uneinheitliche Algorithmen wirft eine natürliche Frage auf: Was ist mit einheitlichen Algorithmen? Gibt es eine Möglichkeit, Komprimierungsprobleme schneller zu lösen als eine umfassende Suche damit?

Die jüngsten Ergebnisse deuten darauf hin, dass ein solcher Algorithmus einem einheitlichen Algorithmus zur Invertierung beliebiger Funktionen entsprechen würde – etwas, nach dem Kryptographen seit Jahrzehnten erfolglos gesucht haben. Aus diesem Grund halten viele Forscher die Möglichkeit für unwahrscheinlich.

„Ich wäre sehr überrascht“, sagte Santhanam. „Es würde eine völlig neue Idee erfordern.“

Aber Allender sagte, Forscher sollten diese Möglichkeit nicht außer Acht lassen. „Eine gute Arbeitshypothese für mich war, dass, wenn es eine uneinheitliche Art und Weise gibt, etwas zu tun, es höchstwahrscheinlich auch eine einheitliche Art gibt“, sagte er.

In jedem Fall hat die Arbeit das Interesse der Komplexitätstheoretiker an alten Fragen der Kryptographie geweckt. Yuval Ishai, ein Kryptograf am Technion in Haifa, Israel, sagte, das sei das Spannendste daran.

„Ich freue mich wirklich über diese Konvergenz der Interessen verschiedener Gemeinschaften“, sagte er. „Ich denke, es ist großartig für die Wissenschaft.“