Jenseits von Zero-Knowledge: Wie geht es weiter in der programmierbaren Kryptographie?

Programmierbare Kryptographie

Während es Verschlüsselung schon seit Tausenden von Jahren gibt, handelt es sich bei der programmierbaren Kryptographie um eine moderne Technologie. Beschrieben als „Allzweckkryptographie … [oder] eine ausdrucksstarke Sprache für Ansprüche“ ist die Idee, dass ein kryptografisches Grundelement wie ein ZK-Beweis flexibel und anpassungsfähig genug gemacht werden könnte, dass ein Entwickler nahezu jede Funktion darauf programmieren könnte. Dass es eine ununterbrochene Logikkette geben kann, vom Klicken einer Schaltfläche auf einer Website bis zum mathematischen Beweis, der die Sicherheit einer kryptografischen Operation garantiert.

https://youtu.be/qAfprVCBhdQ?t=1024

Während die traditionelle Kryptografie auf festen Funktionssätzen beruhte, die einen erfahrenen Kryptografen erforderten, um für jeden neuen Mechanismus ein spezielles System zu erstellen, können Entwickler mit der programmierbaren Kryptografie kryptografische Eigenschaften und Funktionen in einer Sprache bereitstellen, die näher an dem liegt, was sie bereits verstehen. Es bietet Entwicklern, die keine Kryptographie-Experten sind, eine vertrautere Benutzeroberfläche.

ZK-Beweise wurden erstmals 1989 erdacht, blieben jedoch größtenteils theoretisch, bis 2012 eine Art ZK-Beweis namens zk-SNARK entdeckt wurde. Dieses neue Grundelement ermöglichte es ZK-Beweisen, nahezu jede Funktion oder beliebige Berechnung zu beweisen oder zu authentifizieren.

Seitdem zkSNARKS möglich wurde, sind Ressourcen und Talente in die Entwicklung von zCash, zkRollups, zkEVMs und einer Vielzahl anderer Anwendungen geflossen, die mit dem Buchstaben z beginnen. Es stellte sich heraus, dass dezentrale Systeme wie Ethereum und Blockchains im Allgemeinen die perfekte Motivation waren, Menschen für Kryptographie zu interessieren und ein einst unpraktisches Forschungsgebiet in ein aktives Ökosystem mit tatsächlichen Endbenutzeranwendungen zu verwandeln.

Es gibt keine Garantie dafür, dass Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE) und Indistinguishable Obfuscation (iO) denselben Weg wie ZK einschlagen und mit der Zeit praktischer, optimierter und universeller werden. Aber in diesem frühen Stadium ist es durchaus möglich.

Wenn Sie sich programmierbare Kryptographie als eine Art digitalen Computer vorstellen, der auf bestimmten Annahmen basiert, die bestimmte Eigenschaften und Garantien ermöglichen, dann befinden wir uns immer noch im Hardware-Stadium. Wir sind immer noch dabei, herauszufinden, wie wir die logischen Gatter oder Schaltkreise für diesen neuen Computer am besten konstruieren können.

Relativ intuitive Vergleiche

Um die allgemeine Landschaft der programmierbaren Kryptographie besser zu verstehen, beginnen wir mit einer groben Annäherung an die Position von MPC, FHE und IO im Verhältnis zu ZK und zueinander. In diesem Abschnitt und eigentlich in allen folgenden Abschnitten werden wir Nuancen, Präzision und Formalität zugunsten von Einfachheit und Zugänglichkeit abwägen.

Der einfachste Weg, über Kryptographie nachzudenken, besteht darin, welche Informationen verborgen oder geheim gehalten werden. Und was das System beweist oder offenbart.

Sie können sich jedes dieser Systeme auch als Ersatz für einen imaginären gemeinsamen Freund vorstellen. Wikipedia nennt diesen Freund „Tony“. Tony ist unfehlbar, unbestechlich und absolut vertrauenswürdig. Tonys Aufgabe ist es, Geheimnisse zu bewahren. Stellen Sie sich in der folgenden Tabelle die „privaten Elemente“ als die Geheimnisse vor, die Tony vertrauenswürdig bewahren kann, die „Anwendungsfälle“ als Aufgaben, die Tony einigermaßen gut ausführen könnte, und die „Praktikabilität“, als wie geschickt Tony diese Aufgaben heute ausführen könnte.

Die obigen Tabellen sollen einen groben Überblick über verschiedene Bereiche der programmierbaren Kryptographie geben. Gehen wir nun etwas tiefer und schauen uns an, was MPC, FHE und iO tun, zusammen mit einigen interessanten Details zu den einzelnen Bereichen.

Mehrparteienberechnung (MPC)

Multi-Party Computation (MPC) ermöglicht es vielen Parteien, gemeinsam eine vereinbarte Funktion zu berechnen, ohne den anderen Teilnehmern Daten preiszugeben. Bei MPC wird die gleiche Berechnung auf alle Daten angewendet, die Eingaben jeder Partei werden jedoch geheim gehalten. Auch Zwischenwerte würden geheim bleiben. Am Ende wird nur die Ausgabe enthüllt.

Im Gegensatz zu ZK ist MPC kollaborativ. Es ermöglicht verschiedenen Parteien, an derselben Berechnung zusammenzuarbeiten, wobei jeder seine eigenen Daten beisteuert, um gemeinsam das gewünschte Ergebnis zu erzielen.

Wir können ZK und MPC im Kontext eines KI-Systems vergleichen, um mehr Kontext zu erhalten. ZK wäre gut darin, Daten zu authentifizieren oder zu verifizieren, die von einer realen Person oder vom Telefon einer Person stammen. MPC eignet sich besser zum Trainieren eines KI-Systems, da verschiedene Einzelpersonen, Gruppen oder Organisationen vertrauliche Daten mit dem KI-System teilen können, aber darauf vertrauen können, dass die Daten niemand anderem zugänglich gemacht wird.

Probleme mit Millionären

MPC wurde 1982 von Andrew Yao ins Leben gerufen, um ein Gedankenexperiment namens „Millionärsproblem“ zu lösen, bei dem zwei Millionäre wissen wollen, wer reicher ist, ohne sich gegenseitig zu sagen, wie viel Geld sie haben. Die Lösung bestand darin, verstümmelte Schaltkreise zu verwenden, was laut Vitalik Buterin, der häufig kryptografische Konzepte erklärt, auch eine der grundlegendsten Möglichkeiten ist, sich mit MPC vertraut zu machen.

[Bevor Sie etwas über eine verstümmelte Schaltung lernen, müssen Sie wissen, was eine arithmetische Schaltung im Allgemeinen ist. Wenn Sie mit der Idee von Schaltkreisen noch nicht vertraut sind, finden Sie hier eine einfache Erklärung.]

MPC ist ein mehrstufiger, interaktiver Prozess, bei dem Millionärin Nr. 1 (Alice the Garbler) zunächst den Schaltkreis erstellen, ihr Nettovermögen eingeben und es dann in eine verstümmelte oder verschlüsselte Form umwandeln muss, bevor sie es an Millionär Nr. 2 (Bob the Evaluator) weitergibt ). Wenn Bob die Rennstrecke in die Hände bekommt, besteht seine Aufgabe darin, sein eigenes Nettovermögen hinzuzufügen und dann die Rennstrecke zu bewerten oder laufen zu lassen, um sicherzustellen, dass sie korrekt ist. Schließlich entschlüsselt Bob die endgültige Ausgabe und erfährt beispielsweise, dass Alice reicher ist, erfährt jedoch nie, dass Alice tatsächlich viel reicher ist und er keine Annahmen hätte treffen sollen.

Das Millionärsproblem und verstümmelte Schaltkreise als Lösung waren entscheidend für die frühe Entwicklung von MPC. Aber seine Anwendung war begrenzt. Eine komplexere und differenziertere Version des Problems, das Problem der sozialistischen Millionäre, prüfte, ob die beiden Millionäre gleich reich waren, anstatt offenzulegen, wer mehr Geld hatte. Dieser subtile Unterschied erweiterte die MPC-Funktionalität erheblich, erforderte jedoch komplexere kryptografische Lösungen und Techniken, die über den Rahmen dieses Artikels hinausgehen.

Vollständig homomorphe Verschlüsselung (FHE)

Die vollständig homomorphe Verschlüsselung (FHE) ermöglicht Berechnungen anhand verschlüsselter Daten. Es kann eine Funktion mit verschlüsselten Daten ausführen, als ob diese unverschlüsselt geblieben wären. Die Ausgabe der Funktion wird nur von der Partei mit dem geheimen Schlüssel entschlüsselt. Wenn wir uns Verschlüsselung als eine Blackbox vorstellen, die Geheimnisse verbirgt, dann stellt FHE sicher, dass die Daten und die Berechnungen auf diesen Daten innerhalb dieser Blackbox bleiben.

Obwohl es für MPC keine berühmten Gedankenexperimente wie das Millionärsproblem gibt, behebt FHE eine grundlegende Sicherheitslücke: „die Notwendigkeit, Daten vor der Verarbeitung zu entschlüsseln.“

https://www.zama.ai/post/the-revolution-of-fhe

In einem KI-Kontext würde FHE alle Daten zwischen dem Benutzer (Inhaber des geheimen Schlüssels) und dem KI-System verschlüsselt halten. Der Benutzer interagiert wie gewohnt mit dem System, kann jedoch sicher sein, dass die KI nie etwas über die bereitgestellten Daten „gelernt“ hat. Die gesamte Interaktion würde verschlüsselt. Die KI erfährt nie, was Sie eingegeben oder gefragt haben, welche Bilder Sie gesendet haben oder wer sie gesendet hat, kann aber dennoch so reagieren, als ob sie die Informationen kennen würde.

Wenn es funktioniert, wird FHE eine der leistungsstärksten verfügbaren Technologien zum Schutz der Privatsphäre sein. Und wer weiß? In 10 Jahren werden wir vielleicht sogar FHE-EVMs haben.

Lärmmanagement

Im Vergleich zu MPC und ZK liegt FHE derzeit eher am theoretischen bzw. weniger praktischen Ende des Spektrums. Die Technologie galt erst 2009 als machbar, als Craig Gentry herausfand, wie man mit Lärm umgeht.

FHE-Vorgänge sind sehr rechenintensiv, da während des Verschlüsselungsprozesses „Rauschen“ hinzugefügt wird, um die Sicherheit zu erhöhen. Rauschen ist in FHE ein kleiner Zufallswert, der dem Klartext (unverschlüsselten Daten) hinzugefügt wird, bevor er in Chiffretext (verschlüsselte Daten) umgewandelt wird. Jeder Vorgang erhöht den Lärm. Während Additions- und Subtraktionsoperationen ein vernachlässigbares Rauschwachstum verursachen, ist die Multiplikation rechenintensiver, was zu einem erheblichen Rauschwachstum führt. Wenn also die Komplexität eines Programms zunimmt, häuft sich Rauschen an – der Platz, der zur Aufnahme von Rauschen benötigt wird, und die Rechenressourcen, die zur Verarbeitung von Rauschen benötigt werden.

Gentrys Durchbruch war eine Technik namens Bootstrapping, die das Rauschen reduzieren und mehr Berechnungen für verschlüsselte Daten in FHE-Systemen ermöglichen könnte. Bootstrapping nimmt den Chiffretext und entschlüsselt ihn homomorph, was bedeutet, dass der Rauschpegel eines verschlüsselten Datenelements reduziert wird, ohne tatsächlich preiszugeben, um was es sich handelt. Das Ergebnis ist ein Chiffretext mit viel geringerem vordefiniertem Rauschen, sodass wir den Chiffretext weiter berechnen können. Bootstrapping ermöglicht es uns im Allgemeinen, die Notwendigkeit zu umgehen, mit zunehmender Komplexität der Berechnung mehr Platz für das Rauschwachstum zu haben. Wir können den Speicherplatz auf wenige Operationen beschränken und wiederholt einen Bootstrap durchführen, um beliebig große Berechnungen durchzuführen, ohne die Originaldaten zu gefährden.

Abhängig vom FHE-Schema kann das Bootstrapping entweder mehrere Minuten oder Millisekunden dauern. Wenn das Bootstrapping langsamer ist, kann der Rechenaufwand durch die gleichzeitige Anwendung auf mehrere Chiffretexte verteilt werden. Wenn das Bootstrapping schneller ist, geht das normalerweise mit dem Nachteil einher, dass jeweils nur mit kleinen Klartextstücken (normalerweise 8 Bit) gearbeitet werden muss, um effizient zu bleiben.

Ununterscheidbarkeitsverschleierung (iO)

Wenn FHE alle Elemente der Berechnung in eine Blackbox umwandelt, verwandelt iO die Berechnung selbst in eine Blackbox.

Ununterscheidbarkeitsverschleierung (iO) gilt als das leistungsfähigste kryptografische System im Bereich der theoretischen Möglichkeiten. In einem Artikel wird iO als „Master-Tool, aus dem fast jedes andere kryptografische Protokoll erstellt werden könnte“ beschrieben und von Kryptografie-Experten als „Kronjuwel“ und „ein kryptografisches Primitiv, das sie alle beherrscht“ bezeichnet.

Laut Amit Sahai, dem Professor, der dafür bekannt ist, Kindern ZK-Beweise zu erklären, und einem der Forscher, die einen Weg entwickelt haben, iO auf fundierten Annahmen aufzubauen, arbeitet iO nach einem grundlegend anderen Paradigma als frühere kryptografische Systeme. IO geht davon aus, dass der Gegner bereits Ihre Gedanken lesen kann (eine Metapher für Ihren Computer). Ihre Geheimnisse sind bereits bekannt und können daher nicht verborgen bleiben. Das Einzige, was Sie tun können, ist, das zu verschleiern, was der Gegner bereits sehen kann.

https://youtu.be/v2RR_c5hn1E

Der Sinn von iO besteht darin, zwei Funktionen oder Berechnungen gleichermaßen unverständlich zu machen. Wenn Sie zwei Berechnungen in eine Form bringen, die nicht voneinander zu unterscheiden ist, können Sie die Funktionsweise des Programms verbergen. Wenn Sie den Unterschied zwischen zwei Programmen nicht erkennen können, wissen Sie nicht, welches der beiden Programme ausgeführt wird, und von keinem der beiden Programme können Informationen abgeleitet werden, außer dass beide die gleiche Funktion ausführen. Beide Programme nehmen die gleichen Eingaben entgegen und erzeugen die gleichen Ausgaben, aber iO macht es so, dass niemand herausfinden kann, wie.

Mit iO können Sie die Struktur jeder Art von Funktion verbergen, einschließlich fast aller Funktionen, die die Kryptographie ausmachen. Mit anderen Worten: Indem Sie fast alles verschleiern, erreichen Sie die universellste programmierbare Kryptographie, auf der andere Grundelemente programmiert werden können.

Technisch gesehen gibt es eine Blackbox, die größer ist als iO. Es wird im wahrsten Sinne des Wortes Black-Box-Verschleierung genannt. Aber das ist immer noch unmöglich.

Fundierte Annahmen

Niemand wusste, wie man iO baut, bis 2013 multilineare Karten von Garg, Gentry, Halevi, Raykova, Sahai und Waters vorgeschlagen wurden. Ein Computerprogramm könnte wie Puzzleteile zerlegt und dann mithilfe multilinearer Karten verdeckt werden. Die verdeckten Teile könnten wieder zusammengesetzt werden, um die gleiche Funktionalität wie das ursprüngliche Programm zu erreichen, ohne sein Innenleben preiszugeben.

Multilineare Karten sind eine Verallgemeinerung der bilinearen Karten oder Paarungen, die in der Elliptic Curves Cryptography (ECC) verwendet werden. Während bilineare Karten die Grundlage für bestehende kryptografische Schemata wie BLS-Signaturen bilden, sind sie für iO nicht komplex oder aussagekräftig genug. Und obwohl multilineare Karten mit iO umgehen konnten, war diese neu entwickelte algebraische Struktur leicht angreifbar und nicht sicher, sodass die Verwendung multilinearer Karten für Kryptographen im Allgemeinen unbefriedigend war. Das Feld blieb wieder hängen.

Dann, im Jahr 2020, schlugen Jain, Lin und Sahai eine Lösung vor, die zwar ungewöhnlich und neu, aber für Kryptographen einfach genug war, um darüber nachzudenken, und anstatt sich auf neu entwickelte Annahmen wie multilineare Karten zu verlassen, könnte diese Version von iO auf mehr aufbauen Standardannahmen und fundierte Annahmen, die seit Jahrzehnten untersucht werden, wie z. B. Lernen mit Fehlern (LWE). Mit diesem jüngsten Durchbruch wurde iO wieder machbar. Der heilige Gral war immer noch in Reichweite.

Ungezähmte Wildnis

Jedes kryptografische System basiert auf unterschiedlichen mathematischen Annahmen und kryptografischen Techniken. Kein einziger Durchbruch löst alle Probleme eines Systems. Stattdessen folgen Entdeckungen einer unvorhersehbaren Reihe kleiner Schritte und großer Sprünge, die bestehende Annahmen und Techniken verändern, was wiederum zu weiteren Durchbrüchen und Entdeckungen führt. Und auf jede Entdeckung, die funktionierte, taten viele weitere nicht.

In einer Präsentation auf iO beschrieb Sahai das Gebiet als „ungezähmte Wildnis“, wo nicht einmal klar sei, was nicht verstanden wurde und welche Probleme es zu lösen gäbe.

Teams wie PSE arbeiten hauptsächlich auf der praktischen oder angewandten Seite der programmierbaren Kryptographie und konzentrieren sich auf Primitive wie ZK und MPC mit fundierten Annahmen, die kampferprobt, relativ optimiert und als sicher und effektiv gelten. Obwohl es noch viele Optimierungen gibt, befindet sich ZK mittlerweile fest im Bereich der Praktikabilität. Aber es gab auch eine Zeit, in der ZK auf die ungezähmte Wildnis beschränkt war.

Um die Anzahl der datenschutz-, sicherheitsgarantierenden, anspruchsverifizierenden und kryptografiefähigen Tools zu maximieren, auf die die Welt Zugriff hat, sollten wir zumindest ein Auge auf den Horizont dessen richten, was kommen wird, denn niemand kann vorhersagen, was passieren wird wird in 10 Jahren praxistauglich sein.

Sahais Präsentation enthält ein Zitat aus einem Nature-Artikel von Steven Weinberg aus dem Jahr 2003 mit dem Titel „Four Golden Lessons“, der einen weiteren Grund hervorhebt, an dem derzeit Unpraktischen zu arbeiten.

„Als ich Ende der 1960er Jahre am Massachusetts Institute of Technology lehrte, sagte mir ein Student, dass er sich lieber mit der Allgemeinen Relativitätstheorie befassen wollte als mit dem Bereich, an dem ich arbeitete, der Elementarteilchenphysik, weil die Prinzipien der ersteren wohlbekannt seien , während letzteres für ihn ein Chaos zu sein schien. Mir fiel auf, dass er gerade einen vollkommen guten Grund dafür angegeben hatte, das Gegenteil zu tun … Mein Rat ist, sich auf die Sauerei einzulassen – da kommt es darauf an.“

Programmierbare Kryptographie wird von verschiedenen Teams erforscht, darunter PSE und 0xPARC, Mitorganisatoren einer zweitägigen Veranstaltung namens Programmable Cryptography Conference, die am 16. und 17. November 2023 in Istanbul, Türkei, stattfindet.

Kommen Sie und sagen Sie Hallo!

Oder finden Sie PSE online auf Discord.

Haftungsausschluss:

1. Dieser Artikel ist ein Nachdruck aus [Privacy and Scaling Explorations]. Alle Urheberrechte liegen beim ursprünglichen Autor [kichong]. Wenn Sie Einwände gegen diesen Nachdruck haben, wenden Sie sich bitte an das Gate Learn- Team, das sich umgehend darum kümmern wird.
2. Haftungsausschluss: Die in diesem Artikel geäußerten Ansichten und Meinungen sind ausschließlich die des Autors und stellen keine Anlageberatung dar.
3. Übersetzungen des Artikels in andere Sprachen werden vom Gate Learn-Team durchgeführt. Sofern nicht anders angegeben, ist das Kopieren, Verbreiten oder Plagiieren der übersetzten Artikel verboten.