Der Kryptograf, der dafür sorgt, dass wir unseren Computern vertrauen können | Quanta-Magazin

Yael Tauman Kalai ist eine bahnbrechende theoretische Informatikerin, die beeindruckende Auszeichnungen gewonnen und die Art und Weise verändert hat, wie Menschen über das Internet denken. Aber als Kind war sie nicht gerade eine Musterschülerin.

„Ich war ein Unruhestifter“, sagte sie. „Im Grunde wurde ich – nicht ganz, aber im Grunde – von der High School geworfen.“

Kalai wurde in Tel Aviv, Israel, in einer Akademikerfamilie geboren und wuchs dort auf. Ihr Vater, Yair Tauman, ist Ökonom und Spieltheoretiker. Ihr Schulunterricht langweilte sie – ein Zeugnis dokumentierte etwa 150 Schulabwesenheiten, erinnert sie sich, da sie ihre Zeit lieber mit Wasserskifahren und geselligen Beisammenseins verbrachte. Aber ihre analytischen Fähigkeiten waren immer da.

„Wenn meine Eltern mich nicht ausgehen ließen, bestand die einzige Möglichkeit, meinen Vater zum Einverständnis zu bewegen, darin, ihm zu sagen: ‚Okay, gib mir ein Mathe-Rätsel.‘ So schwer du willst, aber wenn ich es löse, gehe ich.‘“ Normalerweise ging sie.

Ihre schlummernde Liebe zur Mathematik erwachte schließlich im College, als sie begann, deren Schönheit zu erkennen. Schließlich entdeckte sie, dass sie diese Mathematik auf Computer und insbesondere auf die Sicherung von Informationen anwenden konnte. Mittlerweile erstreckt sich ihre Arbeit über die Bereiche Mathematik und Informatik, und ihre Ideen waren grundlegend dafür, wie wir Berechnungen im digitalen Zeitalter schützen und verifizieren. In den letzten zwei Jahrzehnten hat sie daran gearbeitet, die Integrität unserer Smartphones, Cloud-Verbindungen und sogar Kryptowährungen sicherzustellen. Heute ist sie Forscherin bei Microsoft und außerordentliche Professorin am Massachusetts Institute of Technology. Kürzlich gewann sie den prestigeträchtigen ACM-Preis in Computing der Association for Computer Machinery für „Durchbrüche bei der nachweisbaren Delegation von Berechnungen und grundlegende Beiträge zur Kryptographie“. Ihre neueste Arbeit blickt auch in die Zukunft, indem sie darüber nachdenkt, wie sich Quantencomputer auf die Sicherheitslandschaft auswirken könnten.

Wie viel sprach mit Kalai über die Weitergabe von Geheimnissen, die Verifizierung der Cloud und die Unkonventionalität des Quantencomputings. Das Interview wurde aus Gründen der Klarheit gekürzt und bearbeitet.

Wie sind Sie vom High-School-Unruhestifter zum Akademiker geworden?

Ich wusste immer, dass ich Mathe liebe, aber die Mathematik in der High School war überhaupt nicht interessant. Dann habe ich im Grundstudium Mathematik studiert und war überwältigt. Es ist das erste Mal in meinem Leben, dass ich ununterbrochen saß und lernte, von morgens bis abends. Ich war in Euphorie. Und ich muss sagen, ich war ein bisschen verärgert, weil ich dachte: „Ich kann nicht glauben, dass ich das hätte genießen können, als ich noch viel jünger war!“

Was hat Sie an der Mathematik fasziniert?

Es ist sehr klar, elegant und abstrakt. Und einige Konzepte in der Mathematik sind kontraintuitiv; Ich erinnere mich, dass ich das Gefühl hatte, dass das Studium mich als Person veränderte. Du lernst, bescheiden zu sein, weil du immer wieder lernst, dass deine Intuitionen falsch sind.

Aber als ich nach einer guten Forschungsfrage suchte, kam mir alles schrittweise vor. Also fing ich an, mich der Informatik zuzuwenden. Und Kryptographie war genau das, was mir gefehlt hat, denn sie befasst sich mit realen Problemen. Kryptographie wird heute überall eingesetzt. Sie dienen dazu, sicherzustellen, dass die von uns versendeten Nachrichten vertraulich und authentisch sind. Woher weiß ich, dass die Nachricht, die ich erhalten habe, auch die gesendete Nachricht ist, wenn ich jemandem eine SMS schreibe? Woher weiß ich, dass die Person, die behauptet, die Nachricht gesendet zu haben, diejenige ist, die sie tatsächlich gesendet hat? Was bedeutet es, das zu wissen? Die Konzepte sind sehr philosophisch und die Art und Weise, wie wir sie mathematisch modellieren, ist wirklich schön. Für mich war es genau das Richtige, sowohl die Reinheit der Mathematik als auch die Anwendbarkeit.

An welchen kryptografischen Problemen haben Sie gearbeitet?

Meine Masterarbeit trug den Titel „How to Leak a Secret“. Hier liegt das Problem: Wir wissen, wie man digital signiert – um zu sagen: „Ich bin es, der diese Nachricht geschrieben hat.“ Aber sagen wir, ich möchte als MIT-Professor etwas unterschreiben, aber ich möchte nicht, dass die Leute wissen, dass ich es bin? Auf diese Weise ist das Geheimnis durchaus stichhaltig, weil Sie zwar wissen, dass ein MIT-Professor es unterschrieben hat, Sie aber nicht wissen, wer.

Wir haben dieses Problem mit etwas gelöst, das wir Ringsignaturen nannten und die von einer Idee in der Informatik inspiriert waren, die man Zeugenbeweise nennt. Nehmen wir an, es gibt eine Aussage und zwei verschiedene Möglichkeiten, sie zu beweisen. Wir sagen, dass es zwei „Zeugen“ dafür gibt, dass die Aussage richtig ist – jeder der Beweise. Ein Zeugenbeweis sieht immer gleich aus, egal welchen Sie verwenden: Er verbirgt, mit welchem ​​Zeugen Sie begonnen haben.

Ringsignaturen sind ähnlich. In der Gruppe der potenziellen Geheimnisverräter kann man sich vorstellen, dass jede Person einen geheimen Schlüssel besitzt. Und die Ringsignatur beweist im Wesentlichen, dass diese Nachricht von jemandem mit einem der geheimen Schlüssel signiert wurde, verrät aber nicht, welchen geheimen Schlüssel sie kennt. Es verbirgt, wessen geheimer Schlüssel verwendet wurde.

Würde eine Institution dieses System jemals tatsächlich nutzen?

Das ist das Schöne und Beängstigende daran – ich kann es schaffen, ohne dass jemand anderes involviert ist. Ich kann als Mitglied der Gruppe ohne die Erlaubnis der Gruppe unterschreiben. Es ist nicht klar, ob es sich hierbei um eine Funktion oder einen Fehler handelt, aber es ist klar, dass es sich um eine wissenschaftliche Entdeckung handelt. Es wurden Ringsignaturen verwendet – es gibt eine Kryptowährung namens Monero, die angeblich aus Gründen der Vertraulichkeit von Transaktionen verwendet wird. Aber ehrlich gesagt weiß ich nicht wirklich, wer unsere Arbeit nutzt. Die Wahrheit ist, ich bin zu beschäftigt, um dem zu folgen.

Wie hat sich Ihre Arbeit zur Analyse der Sicherheit unserer Geräte entwickelt?

Anfang der 2000er Jahre war ich am Ende meiner Doktorarbeit und arbeitete bei Shafi Goldwasser am MIT. Die Leute hatten gerade angefangen, über Cloud Computing zu sprechen, das wir mittlerweile jeden Tag nutzen. Früher hatte man einen riesigen Desktop, auf dem alles erledigt wurde. Mit der zunehmenden Erfassung großer Datenmengen wurden Berechnungen teurer und begannen, sie aus der Ferne durchzuführen. Die Idee dahinter ist, dass es eine leistungsstarke Cloud gibt, die Berechnungen für Sie durchführt. Möglicherweise vertrauen Sie der Cloud-Plattform jedoch nicht. Woher wissen Sie also, dass sie die Berechnung korrekt durchführt? Manchmal besteht möglicherweise ein Anreiz zum Betrügen, da die Berechnung sehr kostspielig sein kann. Und dann haben Sie in manchen Einstellungen möglicherweise Angst vor zufälligen Fehlern. Sie möchten also wirklich einen Beweis dafür, dass diese Berechnung korrekt ist.

Aber in der Regel sind Beweise sehr lang und schwache Geräte können lange Beweise nicht überprüfen. Selbst für Geräte, die das können, ist es sehr kostspielig. Gibt es also eine Möglichkeit, die Beweise zu verkleinern? Informationstheoretisch nein. Aber es stellt sich heraus, dass wir mithilfe kryptografischer Tools stattdessen prägnante Zertifikate generieren können, die sehr, sehr schwer zu fälschen sind. Diese werden als prägnante nicht interaktive Argumente oder SNARGs bezeichnet. Es ist eigentlich kein Beweis. Aber solange man ein Problem nicht lösen kann, von dem wir Kryptographen glauben, dass es sehr schwierig ist, etwa die Faktorisierung großer Zahlen, kann man die prägnanten Beweise nicht fälschen.

Wie kam es zu diesen Beweisen?

Es begann 1985 mit Shafi Goldwasser, Silvio Micali und Charles Rackoff, die gemeinsam die Idee interaktiver Beweise einführten. Wenn man früher über Beweise nachdachte, dachte man darüber nach, Datenzeilen zu schreiben, und man kann sie lesen und überprüfen, ob sie korrekt sind oder nicht. Goldwasser, Micali und Rackoff führten eine völlig andere Art ein, etwas zu beweisen: die Interaktion. Es gibt einen Prüfer und einen Prüfer, und sie tauschen Nachrichten hin und her. Dann entscheidet der Prüfer, ob er überzeugt ist oder nicht.

Lassen Sie mich Ihnen ein Beispiel für etwas geben, das als interaktiver Beweis einfacher zu machen ist als ein klassischer Beweis. Angenommen, wir spielen Schach. Angenommen, ich möchte Ihnen beweisen, dass ich eine Erfolgsstrategie habe. Egal welche Schritte Sie unternehmen, ich werde trotzdem gewinnen. Wie kann ich Ihnen das beweisen?

Im klassischen Sinne ist es ein großer Beweis, denn ich muss beweisen, dass meine Strategie bei allen möglichen Zugkombinationen funktioniert. Aber es stellt sich heraus, dass ich es durch Interaktion sehr prägnant machen kann. Wenn Sie nicht glauben, dass ich eine Erfolgsstrategie habe, spielen wir einfach. Ich werde dir zeigen, dass ich gewinnen werde. Das allein ist natürlich nicht überzeugend – nur weil ich einmal gegen dich gewinnen kann, heißt das nicht, dass ich gegen jeden gewinnen kann. Also gib mir einen Großmeister. Ich werde gegen einen Großmeister gewinnen. Das zeigt die Kraft der Interaktion.

Der Nachteil eines interaktiven Beweises besteht jedoch darin, dass er nicht übertragbar ist. Nehmen wir an, Sie geben mir einen Hundert-Dollar-Schein und beweisen durch Interaktion, dass er tatsächlich 100 Dollar wert ist. Ich möchte es weitergeben können. Ich möchte es jemand anderem geben, der es jemand anderem gibt. Aber wenn ich nur einen interaktiven Beweis hätte, würde das nichts bedeuten; Ich kann es niemand anderem geben. Das Schöne an SNARGs ist also, dass man sie jemand anderem geben kann.

Wie ein Echtheitszertifikat?

Exakt. Blockchains sind heute der wichtigste Ort, an dem sie zur Verifizierung von Transaktionen eingesetzt werden. Als die Blockchain entstand, sagte ich meinen Schülern, wir sollten dem Bitcoin-Entwickler Satoshi Nakamoto Blumen und Pralinen schicken, weil er unsere Arbeit wirklich so relevant gemacht hat.

Wie lässt sich also die Interaktion zur Erstellung dieser übertragbaren Zertifikate beseitigen?

Mit Kryptographie. Lassen Sie mich versuchen, Ihnen eine Vorstellung davon zu geben, wie das funktioniert. In unseren interaktiven Beweisen sendet der Prüfer normalerweise nur Zufallsdaten an den Prüfer – man könnte sich das so vorstellen, dass der Prüfer den Beweis stichprobenartig überprüft. Dann hatten Amos Fiat und Adi Shamir eine Idee: Warum braucht man diesen Verifizierer, wenn er nur Zufälligkeiten sendet? Vielleicht können wir diesen Verifizierer durch eine Funktion ersetzen, etwa durch eine sogenannte Hash-Funktion – es ist eine Funktion, die zufällig aussieht und ein sehr wichtiger Baustein in der Kryptographie ist.

Und es stellt sich heraus: Ja, das können wir. Heute wird das ständig gemacht. Wenn Sie ein iPhone oder ein Android-Gerät besitzen, verwenden Sie das Fiat-Shamir-Paradigma, wenn Ihr Telefon eine Verbindung zu Remote-Servern herstellt, was im Laufe des Tages häufig vorkommen kann. Und es ist dieses Paradigma, das wir verwenden, um die prägnanten Beweise zu konstruieren, die bestätigen, dass Fernberechnungen korrekt sind.

Sie haben davon gesprochen, dass Maschinen „postquantensicher“ sein müssen. Was bedeutet das?

Quantencomputer werden, wenn sie tatsächlich in großem Maßstab existieren, viel leistungsfähiger sein als klassische Computer. Klassische Computer arbeiten mit Bits, die entweder 0 oder 1 sind. In Quantencomputern gibt es Quantenbits, die zwischen 0 und 1 überlagert sind. Und diese Qubits sind verschränkt, was bedeutet, dass sie sich gegenseitig beeinflussen. Das ist es, was Quantencomputern ihre eigentliche Leistungsfähigkeit verleiht.

In Zukunft wird es möglicherweise nicht mehr so ​​sein, dass jeder einen Quanten-Desktop hat. Möglicherweise gibt es einige teure Quantengeräte, die Fernberechnungen für Sie durchführen. Angenommen, Sie möchten eine teure Berechnung an eines dieser Quantengeräte delegieren und benötigen ein Zertifikat, das die Richtigkeit der Ausgabe bestätigt – wie zertifiziert man die Korrektheit von Quantencomputern? Da wir nun Quantenbits und keine klassischen Bits verwenden wollen, ändert sich alles, insbesondere wenn ich möchte, dass der Verifizierer ein klassischer Computer ist.

Im Jahr 2018 erfolgte der Spatenstich Folge von einer Berkeley-Studentin, Urmila Mahadev. Sie war die erste, die einen klassischen, rechnerisch sicheren Beweis zur Verifizierung von Quantenberechnungen vorlegte.

Man kann also einen klassischen Computer nutzen, um Quantenberechnungen zu verifizieren? Das klingt unmöglich!

Ist das nicht erstaunlich? Ich war im Programmkomitee, als Urmila ihren Aufsatz veröffentlichte, und habe die ganze Nacht damit verbracht, mir das anzusehen – die Menge an Koffein, die ich getrunken habe! Ich war überwältigt. Zu diesem Zeitpunkt war ich ein kompletter Quanten-Dummkopf. Ich habe den Krypto-Teil verstanden, aber es hat eine Weile gedauert, bis ich verstanden habe, wie das mit dem Quanten-Teil zusammenpasst. Und es war wunderschön.

Der Übergang vom klassischen zum Quantencomputing klingt nach einer steilen Lernkurve.

Ich weiss. Eigentlich weiß ich nichts über Physik, und da ist eine Menge quantenphysikalischer Intuition im Spiel. Ich verstehe die grundlegendsten Konzepte wie Energie und Temperatur nicht. Manchmal arbeite ich mit Studenten und sobald wir über Quantencomputing sprechen, werde ich zum Studenten. Ich fange an, etwas mehr Intuition zu entwickeln. Und ich muss sagen, es macht mir so viel Spaß, mit einem Lehrbuch über Quanteninformation da zu sitzen. Es gibt nichts Schöneres, als Student zu sein.