- Vollhomomorphe Verschlüsselung (FHE) ist eine Technologie, mit der Berechnungen auf Chiffretexten ausgeführt werden können, ohne die Daten zu entschlüsseln
- Derzeit hat FHE weiterhin Einschränkungen wie geringe Praxistauglichkeit, eine 1.000- bis 10.000-fache Verlangsamung der Rechengeschwindigkeit und einen 40- bis 1.000-fachen Anstieg des Speicherbedarfs
- Doch in letzter Zeit werden FHE-Algorithmen jedes Jahr 8-mal schneller, sodass sie bald in Bereichen wie Cloud Computing, LLM-Inferenz und Blockchain-Smart-Contracts praktisch einsetzbar sein könnten
- Wenn FHE allgemein verbreitet wird, dürfte dies einen industriellen Wandel fördern, bei dem Datenschutz in der gesamten Computing-Umgebung zum Standard wird
- Behandelt werden außerdem gitterbasierte Kryptografie, LWE, Bootstrapping und weitere Schlüsselkonzepte, die Entwicklungsgeschichte von FHE-Algorithmen, reale Implementierungsbeispiele und Trends bei Leistungsverbesserungen
Einleitung: Was ist vollhomomorphe Verschlüsselung?
- Vollhomomorphe Verschlüsselung (Fully Homomorphic Encryption, FHE) ermöglicht beliebige Berechnungen direkt auf Chiffretexten, ohne sie zu entschlüsseln, sodass tatsächlich direkt auf verschlüsselten Daten gerechnet werden kann
- Das heißt, ein Server kann Anfragen und Ergebnisse berechnen und zurückgeben, ohne den Klartext zu kennen
- Diese Technologie wird bereits heute in verschiedenen realen Systemen eingeführt
Potenzial und Grenzen von FHE: „Mooresches Gesetz für FHE“
- FHE kann Daten im Netzwerk dauerhaft verschlüsselt halten und so vollständige Privatsphäre ermöglichen, indem das Risiko von Datenlecks an der Wurzel beseitigt wird
- Dennoch ist die praktische Nutzung derzeit stark eingeschränkt, weil Berechnungen auf Chiffretexten im Vergleich zu Berechnungen auf Klartext 1.000- bis 10.000-mal langsamer sind und der Speicherbedarf um etwa das 40- bis 1.000-Fache steigt – also mit massiven Performance-Einbußen einhergeht
- Das ähnelt dem frühen Internet der 1990er Jahre
- Doch FHE wird zuletzt jedes Jahr 8-mal schneller und dürfte bald in mehrere praktische Anwendungsbereiche vordringen
Der Kipppunkt: Die bald bevorstehende Praxistauglichkeit von FHE
- Wenn sich dieses sprunghafte Tempo der Verbesserungen fortsetzt, könnte FHE künftig in folgenden Bereichen praktisch einsetzbar werden
- verschlüsseltes Cloud Computing
- verschlüsselte LLM-Inferenz
- Blockchain-Smart-Contracts mit Geheimhaltung
- Solche Veränderungen könnten das auf dem Sammeln von Nutzerdaten basierende Geschäftsmodell des Internets grundlegend erschüttern
- Durch FHE wird ein grundlegender Wandel von einem Internet, in dem „Überwachung der Standard“ ist, zu einem Internet erwartet, in dem „Privatsphäre der Standard“ ist
Die Achillesferse der Datensicherheit und die Lösung durch FHE
- Daten befinden sich in drei Zuständen (gespeichert, übertragen, in Benutzung), und gerade im Zustand „in Benutzung“ werden sie entschlüsselt und damit oft zur Sicherheitslücke
- Cloud, Insider, Hacker oder verwundbare CPUs – sie alle können auf Klartextdaten im Speicher zugreifen
- Auch große Datenlecks entstehen überwiegend während der „Nutzung“ oder „Speicherung“
- FHE hält Daten über ihren gesamten Lebenszyklus hinweg verschlüsselt und beseitigt diese Schwachstelle damit grundlegend
Definition von vollständig privatem Computing
- In einer idealen Umgebung bleiben Daten beim Speichern, Übertragen und Benutzen (Berechnen) durchgehend verschlüsselt
- Ein Server sieht zum Beispiel niemals eine Klartextanfrage, sondern erhält eine verschlüsselte Anfrage und gibt nur ein verschlüsseltes Ergebnis zurück
- Nur der Nutzer selbst kann dieses Ergebnis entschlüsseln
Wie FHE funktioniert: mathematische Struktur und Konzepte
- „Homomorph“ beruht auf einer mathematischen Transformation, die dieselbe Struktur erhält (ähnlich etwa der Fourier-Transformation)
- FHE transformiert zwischen Klartextraum und Chiffretextraum in beide Richtungen, sodass das Entschlüsseln des Ergebnisses einer Chiffretext-Operation genau dem Ergebnis derselben Klartext-Operation entspricht
- Für diese Transformation werden vor allem gitterbasierte Kryptografie und LWE (Learning With Errors) verwendet
- Gitterbasierte Kryptografie ist ein Vektorproblem in sehr hoher Dimension und gilt als selbst für Quantencomputer schwer lösbar (quantenresistent)
- LWE ist das Problem, ein lineares System mit Rauschen zurückzurechnen, was in der Praxis nicht entschlüsselbar ist
Rauschmanagement und Bootstrapping
- In FHE nimmt das Rauschen (Noise) im Chiffretext mit jeder weiteren Operation zu
- Bei Addition wächst es linear, bei Multiplikation exponentiell, sodass die Entschlüsselung schließlich unmöglich werden kann
- Die Schlüsseltechnik zur Lösung ist Bootstrapping: Dabei wird ein Chiffretext mit einem „neuen öffentlichen Schlüssel“ erneut verschlüsselt und das Rauschen auf ein bestimmtes Niveau zurückgesetzt
- Dieser Prozess ist der Performance-Flaschenhals von FHE-Systemen, wird aber jedes Jahr schnell verbessert
Weitere zentrale Bausteine von FHE
- Relinearization: Ein Verfahren, das das Problem löst, dass sich der Schlüsseldrang nach einer Multiplikation auf Grad 2 erhöht, und ihn wieder auf Grad 1 zurückführt
- Modulus Switching: Eine Technik zur Verringerung des Modulus eines Chiffretexts für das Rauschmanagement
Daneben werden mit der Weiterentwicklung der Algorithmen fortlaufend verschiedene weitere Techniken vorgestellt
Klassifikation homomorpher Verschlüsselungssysteme (HE) und Python-Beispiel
- Partiell homomorphe Verschlüsselung (Partial HE): Unterstützt nur eine Operation (z. B. unterstützt die Paillier-Verschlüsselung nur Addition)
- Eingeschränkt homomorphe Verschlüsselung (Somewhat HE): Unterstützt sowohl Addition als auch Multiplikation, aber nur mit begrenzter Anzahl wiederholter Multiplikationen
- Vollhomomorphe Verschlüsselung (FHE): Unterstützt Addition und Multiplikation unbegrenzt. Turing-Vollständigkeit garantiert
An einem in Python implementierten Beispiel der Paillier-Verschlüsselung lässt sich partielle Homomorphie intuitiv nachvollziehen
Geschichte der FHE-Entwicklung und das „Mooresche Gesetz für FHE“
- 1978: Erstmals taucht das Konzept des „privacy homomorphism“ auf
- 2009: Erste Realisierung von FHE durch Craig Gentry (Dissertation)
- 2011: Erste Implementierung, 30 Minuten pro Bit (extrem langsam)
- Seit 2013: Bootstrapping auf wenige ms verkürzt
- 2017: Unterstützung approximativer Gleitkommazahlen wie CKKS, ernsthafter Einsatz in ML/AI
FHE-Algorithmen haben sich seit 2011 jedes Jahr um den Faktor 8 verbessert und sind von einem anfänglichen Overhead von 10¹⁰ auf zuletzt etwa 10³ bis 10⁴ gesunken
Neueste Papers haben den FHE-Multiplikationsdurchsatz um das 1.000-Fache erhöht und die Latenz um das 10-Fache gesenkt; in Kombination mit Hardware-Beschleunigung besteht Potenzial für eine zusätzliche Geschwindigkeitssteigerung um mehr als das 1.000-Fache
Eine Zukunft, in der Verschlüsselung der Standard ist
- Große Datenlecks sind eine unvermeidliche Realität
- Wenn mit FHE Server auch ohne Entschlüsselungsschlüssel nur Berechnungen auf verschlüsselten Daten ausführen können, könnte das zu einem neuen Standard für den Schutz der Privatsphäre werden
- Noch ist FHE nicht in allen Bereichen vollständig praxistauglich, verbessert sich aber jedes Jahr in erstaunlichem Tempo
- Zusammen mit den steigenden Anforderungen an Privatsphäre und strengeren Regulierungen wird erwartet, dass FHE letztlich für den Großteil des Cloud Computing zum Standard wird
- Das Internet-Computing der Zukunft wird sich zu einem Zustand entwickeln, in dem es jederzeit verschlüsselt ist
2010er Jahre: HTTPS als Standard
In Zukunft: FHE als Standard
Literatur und weiterführende Materialien
- FHE Reference Library: Umfassende Zusammenstellung wissenschaftlicher Materialien
- Craig Gentrys Dissertation von 2009: Ausgangspunkt von FHE
- Vitalik Buterin: FHE im Detail analysiert
- Community: FHE.org (entwicklerzentrierter Hub)
- GitHub: awesome-he: Sammlung von Projekten rund um homomorphe Verschlüsselung
1 Kommentare
Hacker-News-Kommentare
Ich sage das als jemand, der FHE und Cryptography wirklich sehr mag. FHE wird zwar immer schneller, aber solange es auf Bootstrapping angewiesen ist, wird es die Rechengeschwindigkeit von Klartext nicht einholen können. Der durch Bootstrapping verursachte Overhead von etwa dem 1000-Fachen oder mehr ist grundsätzlich unvermeidbar, und als klar wurde, dass man es nicht einfach weiter beschleunigen kann, begann die Diskussion über Hardware-Beschleunigung. Aber in einer Zeit, in der praktisch alle Rechenressourcen in LLMs fließen, ist das nicht einfach. Wenn man bedenkt, um wie viel die Kosten pro Token bei FHE-Computing steigen würden, ist es realistisch kaum denkbar, solange es nicht deutlich weniger als das 1000-Fache ist. Wenn es um Datenschutz geht, ist Confidential Computing derzeit die einzige praktikable Alternative. Mir gefällt nicht, dass man dafür der Hardware vertrauen muss, aber das ist das Beste, was wir haben
Es gibt einen noch grundlegenderen Grund, warum sich FHE schwer für beliebige Berechnungen einsetzen lässt. Bestimmte Arten von Operationen werden auf Chiffretexten nämlich unnatürlich viel komplexer als auf Klartext. Bei einer Datenbanksuche ist es im Klartext O(log n), bei einer Suche mit verschlüsseltem Schlüssel aber O(n). Deshalb ist eine vollständig homomorphe Google-Suche im Grunde nicht umsetzbar. Bei vollständig homomorpher DNN-Inferenz könnte die Lage aber anders sein
Auch ohne Bootstrapping kann FHE nie so schnell sein wie Klartextberechnung. Chiffretexte sind etwa 1000-mal größer als Klartexte. Das heißt, man braucht viel mehr Speicherbandbreite und viel mehr Rechenleistung. Diese Lücke lässt sich nicht schließen
Ich frage mich, ob es nicht doch eine bestimmte Nachfragegruppe gibt, die wirklich überprüfbare Privatsphäre will, selbst wenn die Rechenkosten um das 1000-Fache steigen. Vielleicht nicht in der Größenordnung von Dropbox, aber ich kann mir schon einen gewissen Markt vorstellen
Ich denke zurück an die Zeit, als alles PCIe-Erweiterungskarten waren. Bei GPUs war das so, und auch spezielle Beschleuniger wie mathematische Coprozessoren gab es separat. Heute ist das in Allzweckhardware integriert und dadurch billiger und bequemer, aber es kann nie so gut sein wie Silizium, das für eine bestimmte Funktion optimiert ist. Deshalb plädiere ich dafür, dedizierte AI/ML-Karten getrennt von GPU-basierten Lösungen einzusetzen. Die Architekturen überschneiden sich teilweise, aber AI-Karten auf GPU-Basis nehmen in vieler Hinsicht Nachteile in Kauf. Wirkliche AI-Beschleuniger sind meiner Meinung nach spezialisierte Hardware im neuesten SXM-Sockel. Aber SXM-Sockel gibt es nur in Servern, und billig sind sie auch nicht
Ich erkenne den LLM-Hype an, frage mich aber, ob es wirklich keine anderen sinnvollen Einsatzgebiete für FHE gibt. Man könnte zum Beispiel überlegen, Trading-Algorithmen, die keine hohe Geschwindigkeit brauchen, per FHE auf einem Server zu hosten, um Sicherheit zu garantieren
FHE ist deshalb wichtig, weil Unternehmen derzeit unter Druck von Regierungen in bestimmten Fällen gezwungen werden können, die Verschlüsselung bestimmter Ziele zu brechen. FHE ermöglicht es Unternehmen, offen zu sagen: "Wir können den Klartext überhaupt nicht sehen." In der Rolle eines Netzwerk-Carriers ist das mit E2E encryption und Ähnlichem teilweise möglich, aber bei der Verarbeitung von Daten im Klartext bislang nicht. Ich halte Privatsphäre für ein grundlegendes Menschenrecht. Staatliche Macht sollte nur sehr eingeschränkt gegenüber demokratischer Aktivität wirken, etwa beim Wählen, bei Kunst, Presse und Meinungsäußerung
Selbst wenn FHE beliebige Berechnungen zulässt, werden die meisten Dienste genutzt, weil sie bestimmte Daten bereitstellen. Wenn Google meine Anfrage sicher verarbeiten soll, müsste der gesamte Suchindex verschlüsselt werden, was in der Praxis unmöglich ist. Auch geschäftlich sehe ich kaum einen Anreiz, FHE-basierte Dienste außerhalb sehr kleiner Hochvertrauens- und Hochrisikobereiche einzuführen
Soweit ich weiß, müssen nur sensible Daten verschlüsselt werden, zum Beispiel meine Banktransaktionsdaten. Die zu berechnende Funktion selbst muss nicht verschlüsselt werden, sondern kann mit öffentlichen Daten kombiniert werden
Letztlich fehlt großen Unternehmen der Anreiz, FHE routinemäßig einzusetzen, weil es ihr Geschäftsmodell ist, die Daten oder Anfragen der Nutzer direkt einzusehen. Im Finanzsektor wie bei Banken könnte das cool sein, aber darüber hinaus ist völlig offen, wann es übernommen wird
Die Anreizfrage stimmt. Aber der erste Teil stimmt nicht. Private Lookups in Klartext-Datenbanken sind bereits seit einigen Jahren möglich. Man muss die Klartext-DB allerdings vorher ziemlich aufwendig vorverarbeiten oder im schlimmsten Fall die gesamte DB linear durchsuchen
Als Beispiel für eine FHE-Implementierung einer vollständig privaten Suchmaschine wird spiralwiki.com genannt. Der Server weiß dabei überhaupt nicht, welchen Wikipedia-Artikel der Nutzer liest spiralwiki.com
Aus "Client-Sicht" wird es sicher Menschen geben, die für einen Dienst bezahlen würden, der ihre Daten so vollständig schützt wie FHE, aber in der Praxis wäre er extrem teuer und hätte nur sehr wenige Abonnenten. Wenn man annimmt, dass die Rechenkosten gegenüber heute um ein Vielfaches steigen, wäre es selbst bei einem datenschutzorientierten Google-Ersatz für 100 Dollar im Jahr schwer, viele Nutzer zu gewinnen. Je höher die Kosten, desto weniger Abonnenten. Es gibt Alternativen wie Tor, die kostenlos ziemlich viel Schutz bieten, auch wenn er nicht perfekt ist. HE ist also nicht nutzlos, sondern nur etwas, dessen Kosten am Ende nur sehr wenige tragen würden
Es wird die Idee erwähnt, dass sich das Internet von "Überwachung als Standard" zu "Privatsphäre als Standard" wandeln könnte. Auch ich verbreite seit langer Zeit Privacy-Technologien, etwa durch digitale Signaturen. Aber man muss die Realität sehen, in der Hacker News oder Facebook die Identität aller in der Hand haben. Das ist einfach zu leicht und zu profitabel. FHE ist ebenfalls so eine Technik, die Menschen zwar wollen, die sich aber praktisch nicht schnell und breit durchsetzt. Wegen des betrieblichen Overheads und der Komplexität hält man in den meisten Fällen bestehende Ansätze für ausreichend gut
Wenn ich an das Ende einer E-Mail so etwas wie eine digitale Signatur angehängt habe, bekam ich nur Reaktionen wie: "Was soll das sein?" Ich frage mich, ob jemand jemals erfolgreich normale Nutzer zur Client-seitigen Verschlüsselung bewegt hat
Es gibt die Meinung, dass die Kombination aus FHE und AI zu einer echten Killer-Kombination werden könnte, weil AI einen Teil der Komplexitätslast übernimmt und dadurch vielleicht breite Nutzung möglich wird
In der Praxis wird es für Unternehmen keinen Grund geben, eine Lösung wie einen FHE-Dienst einzuführen, die eine Million Mal mehr Rechenleistung braucht, schwerer zu debuggen ist und keine Analyse der Nutzungsmuster erlaubt
Mit dem Google-Beispiel einzusteigen, kann irreführend sein. Die meisten denken bei "Google" an "Websuche", aber das im Dokument beschriebene FHE passt womöglich nicht zu Suchdiensten, weil die gesamten Eingabedaten unter einem einzelnen Schlüssel verschlüsselt sein müssen. Googles Suchindex umfasst mehrere TB, und alles unter einem bestimmten Schlüssel zu verschlüsseln, ist praktisch unmöglich. Das heißt: FHE ist nur nützlich, wenn der Nutzer die gesamte Eingabe kontrolliert. Der Google-Verweis stiftet Verwirrung
Bei Fällen wie Apple CallerID scheint es nicht unbedingt nötig zu sein, die gesamte Datenbank pro Nutzer zu verschlüsseln Apples Forschung zu homomorpher Verschlüsselung / Apples private Suche
Ein homomorpher Verschlüsselungsdienst muss den Verschlüsselungsschlüssel von vornherein gar nicht kennen. Genau das ist der Kernpunkt. Es wird ein sehr einfaches Verschlüsselungsbeispiel vorgestellt, bei dem man im Zustand eines unbestimmten Schlüssels das Ergebnis einer Addition von Chiffretexten bilden kann. Wenn man stärkere Verschlüsselung und komplexere Operationen unterstützt, kann man sehr vielfältige Funktionen umsetzen
Wenn man Google hört, denkt man nicht nur an Suche, sondern auch an Gmail, Google Docs und viele andere datenschutzrelevante Dienste. Wer nur an Suche denkt, hat den betreffenden Artikel wahrscheinlich gar nicht gelesen
Ich glaube nicht, dass FHE so bald in General-Purpose-Computing oder Internet-Diensten ankommen wird. Wahrscheinlich braucht es noch viele weitere Generationen von Moore’s law. Aber Bereiche, in denen FHE schon zu glänzen beginnt, könnten Smart Contracts, Finanzen und Medizin sein, wo die Komplexität niedriger ist, aber Sicherheit und Vertrauen extrem wichtig sind. Durch aktuelle Fortschritte bei Moore's law und Software-Optimierung beginnt sich die Kurve meiner Meinung nach in Richtung praktischer Nutzbarkeit zu biegen. Als Beispiel wird Zamas Hardware-/Devtools-Arbeit genannt
E2EE-git wurde bereits entwickelt. Ich fragte die Person, die es gebaut hat, ob sich damit Anforderungen wie protected branches oder das Verhindern von force pushes serverseitig umsetzen lassen, aber wenn der Client bösartig ist, gab es keine wirkliche Antwort. Ich frage mich, ob sich daraus irgendwann ein E2EE-GitHub entwickeln könnte relevanter Hacker-News-Link
Wenn ich den Diskurs höre, dass FHE immer schneller wird, muss ich an ein altes mathematisches Problem zur Durchschnittsgeschwindigkeit denken. Zum Beispiel: Wenn man eine Meile bergauf mit 15 mph fährt, wie schnell muss man dann eine Meile bergab fahren, damit der Durchschnitt über die gesamten 2 Meilen bei 30 mph liegt? Das Tempo vergangener Verbesserungen garantiert nicht die Möglichkeiten der Zukunft. Das ist keine physikalische Grenze, sondern eine algorithmische
Was wäre, wenn die Abfahrt ein Steilhang wäre? Wenn man die Terminalgeschwindigkeit eines Autos mit 200–300 mph annimmt, könnte man rechnerisch vielleicht auf 15 Sekunden für eine Meile im freien Fall kommen. Für einen Durchschnitt von 30 mph über 2 Meilen bräuchte man insgesamt 4 Minuten, also müsste man die Bergauf-Geschwindigkeit an die verbleibende Zeit anpassen, aber in der Praxis wäre das wegen vieler Variablen nicht umsetzbar
Streng gerechnet reichen auf der Abfahrt 41 mph aus, um insgesamt auf 30 mph Durchschnitt zu kommen. Das setzt voraus, dass in der Fragestellung Rundungs- oder Messfehler stecken