Rechnen ohne zu entschlüsseln: Vollhomomorphe Verschlüsselung von Gentrys Bootstrapping bis zum ISO-Normentwurf

Der Aufhänger: Eine Frage, die 31 Jahre unbeantwortet blieb

1978 stellten drei Leute am MIT eine Frage, die so naiv klingt, dass man sie für trivial halten könnte. Ronald L. Rivest, Len Adleman und Michael L. Dertouzos schrieben einen Aufsatz mit dem Titel On Data Banks and Privacy Homomorphisms. Ihr Beispiel ist von bemerkenswerter Alltäglichkeit: Ein kleines Kreditunternehmen speichert seine Datensätze bei einem kommerziellen Time-Sharing-Dienst. Die Datensätze sind vertraulich. Man könnte sie verschlüsselt ablegen – aber dann kann der Dienst nichts damit rechnen. Entschlüsselt man sie zur Verarbeitung, sieht er alles.

Die Frage der drei lautete: Gibt es Verschlüsselungsfunktionen, bei denen man auf dem Chiffrat rechnen kann, ohne es zu entschlüsseln? Sie nannten solche Funktionen privacy homomorphisms – wörtlich: „These special encryption functions we call ‚privacy homomorphisms'; they form an interesting subset of arbitrary encryption schemes." Wenn der Dienstleister aus den Chiffraten von a und b das Chiffrat von a + b berechnen könnte, ohne je einen Klartext zu sehen, wäre das Dilemma aufgelöst.

Der Aufsatz gab Beispielkonstruktionen an – im Text ist von vier die Rede („We give here four sample privacy homomorphisms."), durchnummeriert sind Beispiele 1 bis 5. Die Inkonsistenz steht seit 1978 im Papier. Entscheidender als die Zählung ist die Ehrlichkeit der Autoren über ihr eigenes Material. Wörtlich: „Some of them are rather weak cryptographically; a ‚chosen plain-text attack' may break them." Beispiel 4 wird ausdrücklich bezeichnet als „not really secure against a ‚chosen plaintext attack', although it has many good properties otherwise".

Und sie notierten eine Grenze ihrer eigenen Konstruktionen, die dem heutigen Modell vorgreift: Es sei „not possible to simultaneously preserve security and give the system the operation of performing comparisons … against known constants". Die Begründung steht im Papier selbst – wer Vergleiche gegen Konstanten im Klartext ablesen kann, führt eine binäre Suche und liest damit jeden Wert aus. Wichtig ist, was das nicht heißt: Homomorph rechnen lassen sich Vergleiche sehr wohl, heutige Verfahren tun das über Nachschlagetabellen. Nur bleibt ihr Ergebnis verschlüsselt. Genau daraus folgt das Schaltkreismodell, das in Teil 5 die Kosten erklärt.

Damit stand die Frage im Raum – und blieb stehen. Einzelne Verfahren mit einer homomorphen Operation gab es: RSA ist multiplikativ homomorph, Paillier additiv. Aber ein Verfahren, das beide Operationen beliebig oft erlaubt und damit jede berechenbare Funktion auf verschlüsselten Daten auswerten kann, fehlte 31 Jahre lang. Craig Gentry schrieb 2009 im Abstract seiner Stanford-Dissertation den Satz, auf den die Kryptographie einunddreißig Jahre gewartet hatte: „We propose the first fully homomorphic encryption scheme, solving a central open problem in cryptography." Und ordnete ihn direkt zu: „This problem was posed by Rivest et al. in 1978."

Dieser Artikel nimmt das auseinander: warum es so lange dauerte, worin Gentrys Trick besteht – und welche unbewiesene Annahme er mitbringt –, wie die heutigen Verfahrensfamilien sich unterscheiden und wie die ISO-Normreihe sie schneidet, was das Ganze an Rechenzeit kostet, wo 2021 und noch einmal 2024 eine unangenehme Überraschung lauerte, und was vollhomomorphe Verschlüsselung ausdrücklich nicht leistet. Letzteres ist der wichtigste Teil.

Teil 1: Warum es 31 Jahre dauerte – das Rauschproblem

Die moderne Antwort auf die Frage von 1978 kommt aus der Gittertheorie, und sie bringt einen Preis mit, der die gesamte Baukunst des Feldes bestimmt.

Lernen mit Fehlern

Oded Regev veröffentlichte seine Ergebnisse 2005; die hier verwendete Fassung vom 2. Mai 2009 trägt den Titel On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. Das zentrale Problem – Learning With Errors, kurz LWE – ist in einem Satz zu beschreiben: Gegeben sind Paare (a_i, b_i), wobei a_i unabhängig und gleichverteilt aus Z_p^n gezogen wird und b_i = ⟨s, a_i⟩ + e_i gilt. Jeder Fehlerterm e_i ∈ Z_p stammt unabhängig aus einer Fehlerverteilung χ. Gesucht ist der geheime Vektor s.

Ohne die Fehlerterme wäre das lineare Algebra und in Sekunden gelöst. Mit ihnen gilt es als hart. Regev beschreibt es im Papier als „a natural extension of the ‚learning from parity with error' problem to higher moduli" und ebenso: „It can also be viewed as the problem of decoding from a random linear code."

Sein Hauptsatz (Theorem 1.1, informelle Fassung) lautet: Für n, p und α ∈ (0,1) mit αp > 2√n gilt – wer LWE effizient löst, liefert damit „an efficient quantum algorithm that approximates the decision version of the shortest vector problem (GAPSVP) and the shortest independent vectors problem (SIVP) to within Õ(n/α) in the worst case".

Das Wort quantum ist dabei nicht Marketing, sondern eine Einschränkung des Beweises. Regev schreibt ausdrücklich: „Our reduction, however, is quantum." Und im Abstract: „A main open question is whether this reduction can be made classical (i.e., non-quantum)." Im Abschnitt zu offenen Fragen heißt es entsprechend, die zentrale offene Frage dieser Arbeit sei, ob Theorem 1.1 „dequantisiert" werden kann.

Das Rauschen ist Schutz und Problem zugleich

Für die Kryptographie ist das Rauschen der eigentliche Schutzmechanismus: Es macht das Chiffrat von einer Zufallsfolge ununterscheidbar. Für das Rechnen auf Chiffraten ist es der Fluch. Addiert man zwei Chiffrate, addieren sich die Fehlerterme. Multipliziert man sie, multiplizieren sie sich – das Rauschen wächst deutlich schneller. Irgendwann überschreitet es eine Schwelle, ab der die Entschlüsselung nicht mehr den richtigen Klartext liefert, sondern Müll.

Damit ist klar, warum Teilerfolge möglich waren, ein Gesamterfolg aber nicht: Man konnte Verfahren bauen, die eine begrenzte Zahl von Operationen aushalten – „somewhat homomorphic". Die Multiplikationstiefe, die ein solches Verfahren verkraftet, ist das sogenannte Rauschbudget. Ist es erschöpft, ist das Chiffrat verloren. Eine beliebige Funktion lässt sich so nicht auswerten, weil man die Tiefe des Schaltkreises nicht vorab beschränken will.

Dieses Rauschen wird uns durch den ganzen Artikel verfolgen. Es verschwindet in keinem der heutigen Verfahren – es wird nur unterschiedlich verbucht. Und in Teil 6 wird es vom technischen Detail zum Angriffsvektor.

Teil 2: Gentrys Trick – Entschlüsseln, ohne zu entschlüsseln

Gentrys Lösung ist eines der elegantesten Argumente der neueren Kryptographie, und sie besteht aus einer Umkehrung des Problems.

Bootstrapping

Der Gedanke: Wenn das Rauschen das Problem ist, dann brauche ich eine Operation, die es zurücksetzt – eine Art Auffrischen des Chiffrats. Entschlüsseln und neu verschlüsseln würde das tun, aber der Server hat den geheimen Schlüssel nicht; hätte er ihn, wäre das ganze Verfahren sinnlos.

Gentrys Ausweg: Man führt die Entschlüsselungsfunktion selbst homomorph aus. Der Server bekommt eine Verschlüsselung des geheimen Schlüssels und wertet damit den Entschlüsselungsschaltkreis auf dem verrauschten Chiffrat aus. Das Ergebnis ist ein Chiffrat desselben Klartexts – mit dem Rauschen, das die homomorphe Auswertung des Entschlüsselungsschaltkreises erzeugt, statt dem angesammelten Rauschen der bisherigen Rechnung. In Gentrys Worten aus der Dissertation: „This is the idea behind bootstrapping: we do decrypt the ciphertext, but homomorphically!"

Daraus folgt sein allgemeines Resultat, und es ist ein reines Selbstbezugsargument. Es genügt, ein Verfahren zu bauen, das seinen eigenen – leicht erweiterten – Entschlüsselungsschaltkreis auswerten kann; ein solches Verfahren nennt Gentry bootstrappable.

Hier gehört allerdings ein Vorbehalt hin, der in populären Darstellungen fast immer fehlt. Aus Bootstrappability folgt zunächst nur leveled FHE – über eine Kette von L Schlüsselpaaren, bei der jede Auffrischung zum nächsten Schlüssel übergeht. Unbegrenzte Tiefe mit einem einzigen Schlüsselpaar folgt erst unter einer zusätzlichen Annahme: der Zirkularitätssicherheit, also der Annahme, dass die Verschlüsselung des geheimen Schlüssels unter dem eigenen öffentlichen Schlüssel sicher ist. Diese Annahme ist aus keinem Standardproblem bewiesen. Wie grundlegend sie ist, zeigt eine Arbeit von Canetti, Lin, Tessaro und Vaikuntanathan aus dem Jahr 2014, die ihr eigenes Ergebnis als „the first construction of full-fledged FHE that does not rely on encryption with circular security" beschreibt – im Umkehrschluss beruhten alle bootstrapping-basierten Voll-FHE-Konstruktionen davor genau darauf. Jedes praktisch eingesetzte FHE-Verfahren mit unbegrenzter Tiefe steht also auf einer Annahme, für die es keinen Härtebeweis gibt.

Squashing: der Verschlüsseler fängt mit dem Entschlüsseln an

Der Haken: Gentrys erstes Verfahren auf Basis idealer Gitter war nicht bootstrappable, und die Begründung ist feiner, als sie oft wiedergegeben wird. Die Tiefe, die das Verfahren korrekt auswerten kann, hängt doppelt logarithmisch von den Rausch-Radien ab (in der Dissertation: log log r_Dec − log log(γ_Mult(R) · r_Enc)). Die Tiefe seines eigenen Entschlüsselungsschaltkreises enthält dagegen zusätzlich einen Term, der logarithmisch in der Gitterdimension n ist (O(log n + log log r_Dec)). Genau dieser Term log n sorgt dafür, dass das Verfahren knapp nicht an sich selbst heranreicht – Gentry formuliert es als Beobachtung, nicht als Beweis: „for this initial scheme, it seems that no matter how the parameters are set, the decryption circuit is always slightly too complex for the scheme to evaluate."

Der letzte Schritt der Konstruktion ist Squashing: Der Entschlüsselungsschaltkreis wird flacher gemacht. Gentry formuliert das Ziel als Reduktion der Entschlüsselungskomplexität „without affecting the ‚evaluative capacity' of the scheme at all" – räumt für einen Zwischenschritt aber eine ganz geringe Einbuße ein. Technisch legt man einen „hint" über den geheimen Schlüssel in den öffentlichen Schlüssel. Dieser Hinweis genügt nicht, um ein Chiffrat zu entschlüsseln, aber er erlaubt, das Chiffrat so vorzuverarbeiten, dass ein sehr flacher Schaltkreis es entschlüsseln kann. Im Abstract seines Konferenzvortrags beschreibt Gentry das Prinzip bildhaft: Man versetzt den Verschlüsseler in die Lage, mit dem Entschlüsseln anzufangen, und lässt dem Entschlüsseler weniger Arbeit – ähnlich wie bei einem server-aided Kryptosystem. Dafür ist eine zweite Härteannahme nötig: „we require a second computational hardness assumption."

Die Konferenzfassung erschien 2009 unter dem Titel Fully Homomorphic Encryption Using Ideal Lattices beim Annual ACM SIGACT Symposium on Theory of Computing (STOC 2009); die ausführliche Darstellung ist die Stanford-Dissertation A Fully Homomorphic Encryption Scheme vom September 2009.

Was Bootstrapping nicht ist: ein Effizienzgewinn

Bootstrapping ist der Hebel für unbegrenzte Tiefe, nicht für Geschwindigkeit. Es ist die teuerste Einzeloperation des Feldes, und ein großer Teil der Forschung seit 2009 besteht darin, sie entweder zu vermeiden oder billiger zu machen. Beide Wege wurden gegangen.

Teil 3: Vermeiden oder beschleunigen – die beiden Entwicklungslinien

Der Vermeidungspfad: leveled FHE

2011 zeigten Zvika Brakerski, Craig Gentry und Vinod Vaikuntanathan in Fully Homomorphic Encryption without Bootstrapping (das Verfahren heißt heute BGV), dass man Bootstrapping für viele Zwecke nicht braucht. Ihr Verfahren wertet Schaltkreise mit L Ebenen aus, bei einem Rechenaufwand pro Gatter von „Õ(λ · L³) per-gate computation" – also quasi-linear im Sicherheitsparameter λ. Die Sicherheit beruht dabei „on RLWE for an approximation factor exponential in L".

Der Preis steht im Wort leveled: Die Schaltkreistiefe L muss vorab festgelegt werden, weil die Parameter von ihr abhängen. Das ist keine Nebenbedingung, sondern die Grenze des Ansatzes. BGV behandelt Bootstrapping konsequent als Optimierung, nicht als Fundament: Mit Bootstrapping fällt der Aufwand pro Gatter auf Õ(λ²), unabhängig von L – wobei die Sicherheit dann auf RLWE für quasi-polynomielle Faktoren beruht, also auf einer verschärften Annahme. Für Schaltkreise großer Breite – im Abstract: „for circuits of large width — e.g., where a constant fraction of levels have width at least λ" – lässt sich das durch Batching des Bootstrappings auf Õ(λ) senken. Diese letzte Schranke gilt ausdrücklich nur für breite Schaltkreise und ist nicht die allgemeine Kennzahl des Verfahrens.

Für unbegrenzte Tiefe ist Bootstrapping das einzige aus Gitterannahmen bekannte Mittel. Eine Unmöglichkeit anderer Wege ist dagegen nicht bewiesen: Aus sub-exponentiell hartem Indistinguishability Obfuscation lässt sich, wie die oben genannte Arbeit von 2014 zeigt, nicht-leveled FHE auch ohne Zirkularitätsannahme konstruieren – allerdings aus einer Annahme, die praktisch nicht einsetzbar ist. „Unverzichtbar" ist Bootstrapping also in der Praxis, nicht im Satz der Theorie.

Der Beschleunigungspfad: TFHE

Die andere Linie hat Bootstrapping so weit optimiert, dass es zur Standardoperation wurde. Ilaria Chillotti, Nicolas Gama, Mariya Georgieva und Malika Izabachène legten mit TFHE: Fast Fully Homomorphic Encryption over the Torus die Vollfassung ihrer Asiacrypt-2016- und Asiacrypt-2017-Arbeiten vor (Journal of Cryptology, 2019). Die Zahlen aus dem Abstract sind der Grund für die Verbreitung des Verfahrens: Die Bootstrapping-Laufzeit des Vorgängerverfahrens FHEW sinkt „from 690ms to 13ms single core", bei gleichem Sicherheitsparameter – und mit einem Bootstrapping-Schlüssel von 16 MB statt 1 GB. Hinzu kommt ein neues circuit bootstrapping, das LWE-Chiffrate in rauscharme RingGSW-Chiffrate umwandelt, „in just 137ms".

Der Modus, in dem TFHE üblicherweise betrieben wird, heißt gate bootstrapping: Jedes binäre Gatter wird einzeln mit einem Bootstrapping abgeschlossen, sodass das Rauschen nie anwächst. Das ist rechnerisch verschwenderisch – aber es macht die Tiefe des Schaltkreises irrelevant, und das ist in der Praxis oft mehr wert als ein kleinerer konstanter Faktor.

Teil 4: Drei Rechenmodelle, vier Verfahren – und eine Normreihe, die ihnen folgt

Wer heute FHE einsetzt, wählt kein „FHE", sondern eine von wenigen Familien mit unterschiedlichen Rechenmodellen. Ich bin der Meinung, dass diese Unterscheidung in der Diskussion zu oft übersprungen wird – belegen lässt sich das nicht, aber sie entscheidet darüber, ob ein Vorhaben technisch überhaupt aufgeht.

Exakte Arithmetik auf modularen Zahlen: BGV und BFV

BGV und BFV rechnen exakt mit ganzen Zahlen modulo einem Klartextmodul. Sie unterstützen Batching: Ein Klartextpolynom kodiert einen Vektor von Werten, und eine homomorphe Operation wirkt auf alle Slots gleichzeitig (SIMD). Für Statistik, Datenbankabfragen und alles, bei dem ein Rundungsfehler nicht akzeptabel ist, sind sie die Wahl. BFV beruht nach Angabe der Apple-Implementierung „on the ring learning with errors (RLWE) hardness problem, which is quantum resistant".

Approximative Arithmetik: CKKS

2017 veröffentlichten Jung Hee Cheon, Andrey Kim, Miran Kim und Yongsoo Song auf ASIACRYPT das Verfahren CKKS (Homomorphic Encryption for Arithmetic of Approximate Numbers). Die Idee ist eine bewusste Umdeutung: Statt das Rauschen als Fehler zu bekämpfen, wird es als Teil des Rundungsfehlers behandelt, der bei approximativer Arithmetik ohnehin entsteht. Das Papier beschreibt eine neue Rescaling-Prozedur, die „truncates a ciphertext into a smaller modulus, which leads to rounding of plaintext"; das Rauschen wird dabei zusammen mit dem Klartext mitverkleinert. Die Entschlüsselung „outputs an approximate value of plaintext with the predetermined precision".

Der bemerkenswerte Satz des Abstracts ist dieser: Der Genauigkeitsverlust während der Auswertung ist durch die Tiefe des Schaltkreises beschränkt, und „it is at most one more bit compared with unencrypted approximate arithmetic such as floating-point operations". Dafür wächst die Bitlänge des Chiffratmoduls linear mit der Schaltkreistiefe, eben wegen des Rescaling. Als Anwendungen nennt das Papier das multiplikative Inverse, Exponential- und Logistikfunktion sowie die diskrete Fourier-Transformation.

Wichtig für das Verständnis des späteren Angriffs: Das Rauschen verschwindet in CKKS nicht, es wird nur anders verbucht. Es kostet Genauigkeit statt Korrektheit, und es begrenzt die Tiefe weiterhin – der linear mit der Tiefe wachsende Chiffratmodul ist genau diese Grenze. Genau dieses verbuchte Restrauschen wird 2021 zum Angriffsvektor.

Damit ist CKKS das naheliegende Verfahren für den arithmetischen Teil des maschinellen Lernens auf verschlüsselten Daten – Skalarprodukte, Polynomapproximationen. Für Vergleiche, Maximumbildung und nicht-polynomielle Aktivierungsfunktionen ist es die falsche Wahl.

Auswertung über Nachschlagetabellen: TFHE/FHEW

Die dritte Familie rechnet nicht arithmetisch, sondern wertet Funktionen über Lookup-Tabellen aus. TFHE optimiert laut Abstract ausdrücklich „the evaluation of look-up tables and arbitrary functions in RingGSW based homomorphic schemes". Das ist der Zugang für alles, was arithmetisch unangenehm ist – Vergleiche, Maximum, Aktivierungsfunktionen, Bit-Operationen.

Die ISO-Reihe gliedert nach Rechenmodellen, nicht nach Verfahren

Beim ISO/IEC JTC 1/SC 27 (Information security, cybersecurity and privacy protection) entsteht die Normreihe ISO/IEC 28033 Information security — Fully homomorphic encryption. Ihre Mechanismenteile sind nicht nach Verfahren, sondern nach Rechenmodellen geschnitten:

Drei Einordnungen dazu. Erstens: Die Zuordnung der Spalte „Naheliegende Zuordnung" ist eine Lesart, keine Festlegung der Norm – die Normtitel nennen keine Verfahrensnamen. Vier Verfahren verteilen sich dabei auf drei Mechanismenteile, weil BGV und BFV in einen Teil fallen.

Zweitens, und das ist für die Praxis das Wichtigste: Keiner der Teile ist zum Abrufzeitpunkt ein veröffentlichter Internationaler Standard. Alle vier Mechanismenteile tragen den Status „Under development"; die Teile 1 und 2 stehen als Draft International Standard beim Abschluss der Abstimmung, die Teile 3 und 4 als Final Draft im Genehmigungsverfahren. Wer heute „nach ISO 28033" fordert oder zusichert, bezieht sich auf einen Normentwurf.

Drittens: Dass ein eigener Teil 5 für Scheme Switching existiert, zeigt, dass die Normung reale Pipelines im Blick hat – praktische Anwendungen wechseln zwischen exakter Arithmetik, approximativer Arithmetik und Tabellenauswertung. Neu ist der Gedanke nicht: Die CHIMERA-Arbeit von Boura, Gama, Georgieva und Jetchev aus dem Jahr 2018 nennt „the recent standardization initiatives of homomorphic schemes and common APIs" ausdrücklich als Motiv und begründet den Verfahrenswechsel damit, dass „operations of different nature and not achievable within a single FHE scheme have to be performed". Festzuhalten bleibt, dass dieser Wechsel selbst ein kryptographisches Verfahren mit eigenen Kosten ist.

Teil 5: Was es kostet – und warum der Faktor nur die halbe Antwort ist

Die Größenordnung

Die DARPA hat mit dem Programm DPRIVE (Data Protection in Virtual Environments) genau an diesem Punkt angesetzt. Auf der Programmseite – inzwischen mit „This program is now complete" markiert – steht die Diagnose: FHE „requires enormous computation time to perform even simple operations", und „running FHE in software on standard processing hardware remains untenable for practical data security applications due to the massive processing overhead". Das Programmziel ist mit einer Zahl formuliert: FHE-Berechnungen „within a factor of ten of unencrypted computations", an anderer Stelle „within one order of magnitude of current performance on unencrypted data". Der Beschleuniger sollte den Laufzeit-Overhead gegenüber softwarebasierter FHE auf konventionellen CPUs „by many orders of magnitude" senken – diese Formel bezeichnet also die geforderte Reduktion, nicht den Ist-Zustand.

Den Ist-Zustand nennt die Programmseite nicht. Eine gemessene, zitierbare Einordnung gibt es dennoch. Samardzic, Feldmann, Krastev, Devadas, Dreslinski, Peikert und Sanchez beziffern in ihrer MICRO-2021-Arbeit zum FHE-Beschleuniger F1 den Abstand sorgfältig optimierter Software-FHE zur Klartextrechnung mit „10,000× to 100,000× slower than unencrypted computation when executed in carefully optimized software", im Abstract als „4 to 5 orders of magnitude". Zum Vergleich nennt dieselbe Arbeit für die ersten Verfahren von 2009 „about 10^9 times slower". Das ist eine Einordnung des Feldes, keine Einzelmessung – gemessen wird in der Arbeit der Beschleuniger F1 gegen Software-FHE auf einem Vierkern-Xeon, mit Faktoren von 1.195× (CKKS-Bootstrapping) bis 17.412× (LoLa-MNIST), geometrisches Mittel 5.432×. Bemerkenswert ist der dort berichtete Methodenhinweis: Mikrobenchmarks ergeben weit höhere Beschleunigungen (bis 48.640×) als Vollbenchmarks, weil sie „pure compute" sind und „miss FHE's data-movement bottlenecks".

Auf der Softwareseite ist OpenFHE die Implementierung mit der breitesten Schemaabdeckung; das zugehörige Papier (WAHC 2022, 23 Autoren, darunter Halevi, Micciancio, Polyakov, Rohloff und Vaikuntanathan) nennt für die FHEW/TFHE-artigen Schemata DM, CGGI und LMKCDEY, in denen nichtlineare Operationen über funktionales Bootstrapping laufen, „a form of fast functional bootstrapping (under 100 ms)" – die Angabe steht im Haupttext, nicht im Abstract. Die dort genannten Vergleichszahlen sind relative Kosten zwischen FHE-Konfigurationen, typischerweise Faktoren von 1,2 bis 1,5 zwischen verschiedenen Modi, nicht Vergleiche gegen Klartextrechnung.

Die Gestalt der Rechnung

Die praktisch wichtigere Konsequenz ist nicht der Faktor, sondern die Form, in die eine Berechnung gebracht werden muss. Weil der Auswerter keinen Klartext sieht, kann er nicht auf Klartextwerte verzweigen: Eine Bedingung über verschlüsselten Daten hat kein Ergebnis, das er lesen könnte. Deshalb formulieren die Schema-Arbeiten – Gentry, BGV, TFHE, CKKS – das Modell als Auswertung von Schaltkreisen.

Daraus folgt konkret: Ein if wird zu beiden Zweigen plus arithmetischer Auswahl; eine Schleife muss im Schaltkreismodell auf ihre maximale Rundenzahl ausgerollt werden; ein Datenbankzugriff über einen verschlüsselten Index wird in allen heute eingesetzten Systemen zu einem Durchlauf über alle Einträge.

Dass das nicht zwingend so ist, gehört zur Redlichkeit dazu – und es ist überraschender, als die Praxis vermuten lässt. Goldwasser, Kalai, Popa und Vaikuntanathan benennen in How to Run Turing Machines on Encrypted Data (CRYPTO 2013) genau diesen Nachteil als behebbar: Der Mangel des Schaltkreismodells sei, dass „evaluating an algorithm over encrypted data is as slow as the worst-case running time of that algorithm"; ihre Variante läuft „in time that is dependent on the running time of M on input x". Der Preis ist, dass die tatsächliche Laufzeit als Nebeninformation nach außen gelangt. Und Lin, Mook und Wichs zeigen in Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE (CRYPTO 2023), dass ein Server nach einer Vorverarbeitung von O(N^(1+ε)) jede Anfrage „in time that is sub-linear in the database size" beantworten kann, mit polylogarithmischer Laufzeit und Kommunikation – und konstruieren RAM-FHE „under the RingLWE assumption with circular security", dessen Kosten an der RAM-Laufzeit hängen statt an der Schaltkreisgröße. Beides ist asymptotisch und ohne praktische Implementierung; der Satz „FHE muss immer alles anfassen" ist also eine Aussage über den Stand der Technik, nicht über die Theorie.

Der Overhead von FHE ist deshalb nicht nur Kryptographie: hinzu kommt der Verlust der Abkürzungen, die normale Programme nehmen. Wie groß dieser Anteil ist, wird in der Literatur nicht beziffert; gemessen dominieren Datenbewegung und Bootstrapping – eine Arbeit zum Beschleuniger-Entwurf veranschlagt für Bootstrapping „more than 50% of the total compute and memory budget".

Teil 6: Der Fall CKKS – als die Sicherheitsdefinition selbst zur Lücke wurde

Dies ist der lehrreichste Vorfall in der Geschichte des Feldes, den ich kenne, und er handelt nicht von einem Implementierungsfehler, sondern von einer Definition.

CKKS wurde als IND-CPA-sicher nach der klassischen Definition entworfen und als solches jahrelang eingesetzt. 2021 präsentierten Baiyu Li und Daniele Micciancio auf der EUROCRYPT das Papier On the Security of Homomorphic Encryption on Approximate Numbers – und darin passive Angriffe auf CKKS, die zur vollständigen Schlüsselwiederherstellung führen: „leading to complete key recovery with high probability and very modest running times", in erwarteter Polynomialzeit. Die Autoren haben den Angriff implementiert und gegen die großen Open-Source-Bibliotheken getestet, unter anderem HEAAN, SEAL, HElib und PALISADE. Die ausgewerteten Funktionen waren keine Laborkonstrukte, sondern genau das, was man mit CKKS tut: „mean and variance computations, and approximation of logistic and exponential functions using their Maclaurin series".

Wie der Angriff wirklich funktioniert

Die naheliegende Erklärung – „das Restrauschen hängt vom Schlüssel ab, also verrät es ihn" – ist falsch. Der Mechanismus ist genau umgekehrt, und das macht ihn so verblüffend. Die Kenntnis des Entschlüsselungsergebnisses eliminiert das Rauschen:

1. Ein Chiffrat ist ein Paar (a, b) mit b = ⟨s, a⟩ + m + e.
2. Die Entschlüsselung liefert m + e – bei einem approximativen Verfahren eben nicht nur m. Dafür genügt die Identitätsfunktion; es muss gar nichts ausgewertet werden.
3. Der Angreifer rechnet c = b − (m + e). Der unbekannte Fehler e kürzt sich heraus. Übrig bleibt c = ⟨s, a⟩ mod q – eine fehlerfreie lineare Gleichung in den Unbekannten des Schlüssels.
4. Damit ist das harte RLWE-Problem auf lineare Algebra reduziert. Bei den in CKKS üblichen Moduli ist das Ringelement a mit hoher Wahrscheinlichkeit invertierbar, sodass s = a⁻¹·c folgt: ein einziges Chiffrat samt seinem Entschlüsselungsergebnis reicht. Nur bei Moduli, die Zweierpotenzen sind, braucht man mehrere.

Die Nebenbedingung: Der Angreifer muss die Kodierung des Klartexts exakt rekonstruieren können, was eine Schranke an die Fehlernorm verlangt; bei großen Klartexten greift stattdessen ein Gitterangriff, der polynomiell, aber in der Arbeit nicht implementiert ist.

Was das Papier behauptet – und was nicht

Hier wird in Zusammenfassungen oft verzerrt. Das Papier behauptet nicht, CKKS sei nicht IND-CPA-sicher. Es sagt, dass die traditionelle Formulierung von IND-CPA „does not adequately capture security against passive adversaries when applied to approximate encryption schemes", und dass eine andere, stärkere Definition nötig ist. Die Autoren schlagen diese Definition vor; in der Revision heißt sie IND-CPA^D, wobei das D ausdrücklich kennzeichnet, dass dem Angreifer Entschlüsselungsergebnisse offengelegt werden.

Und eine Einordnung des Bedrohungsmodells gehört dazu, sonst klingt der Befund dramatischer als er für viele Architekturen ist: Der Angriff setzt voraus, dass der Angreifer zu einem ihm bekannten Chiffrat auch das Entschlüsselungsergebnis sieht. Im einfachen Auslagerungsmodell – der Dateneigner verschlüsselt, der Server rechnet, nur der Dateneigner entschlüsselt und gibt das Ergebnis nicht weiter – ist das nicht der Fall. Scharf wird es dort, wo Entschlüsselungsergebnisse geteilt werden: in Threshold-Verfahren, Mehrparteien-Auswertungen und überall, wo Ergebnisse veröffentlicht werden.

Die Reparatur – und warum die Trennlinie nicht bei „exakt" liegt

Die Behebung kam ein Jahr später, von Baiyu Li, Daniele Micciancio, Mark Schultz und Jessica Sorrell: Securing Approximate Homomorphic Encryption Using Differential Privacy (CRYPTO 2022). Das Ergebnis: Es genügt, „adding Gaussian noise to the output of CKKS decryption", um IND-CPA^D-Sicherheit zu erreichen, mit „nearly matching upper and lower bounds" für die nötige Rauschmenge. Das Papier nennt zugleich einen Fallstrick: Mechanismen, deren Rauschparameter am tatsächlichen Fehler des einzelnen Chiffrats ausgerichtet sind statt am Worst-Case-Fehler, bleiben „vulnerable to IND-CPA^D attacks".

Und hier kommt die Pointe, die die naheliegende Lehre des Vorfalls korrigiert. Man möchte schließen: approximativ ist gefährlich, exakt ist sicher. Das stimmt nicht. Bei exakter Verschlüsselung verrät ein korrektes Entschlüsselungsergebnis dem Angreifer unmittelbar nichts Neues – aber nur, solange die Entschlüsselung wirklich immer korrekt ist. 2024 zeigten Checri, Sirdey, Boudguiga und Bultel in On the practical CPA^D security of „exact" and threshold FHE schemes and libraries (CRYPTO 2024), dass auch die „exakten" Verfahren nur mit hoher, nicht mit voller Wahrscheinlichkeit korrekt entschlüsseln: Sie konstruieren „a CPA^D key recovery attack on the linearly homomorphic Regev cryptosystem", die sich nach ihrer Angabe „easily generalizes to other xHE schemes such as BFV, BGV and TFHE", und halten fest, dass „existing threshold variants of BFV, BGV and CKKS are particularily exposed to CPA^D attackers". Der Angriff ist implementiert, läuft gegen gängige Bibliotheken und benötigt nach Angabe der Arbeit unter einer Stunde auf einem durchschnittlichen Laptop.

Die Trennlinie liegt also nicht bei exakt gegen approximativ, sondern bei perfekter gegen nicht-perfekter Korrektheit. Der CKKS-Vorfall war nicht ein Spezialfall der Approximation, sondern der erste sichtbare Fall einer allgemeineren Lücke.

Die Lehre daraus ist allgemeiner als CKKS und allgemeiner als FHE: Eine Sicherheitsdefinition ist ein Modell der Angreiferfähigkeiten. Wenn ein Verfahren Informationen nach außen gibt, die das Modell nicht vorgesehen hat – ein Restrauschen, eine seltene Fehlentschlüsselung –, dann ist nicht der Code falsch und nicht die Mathematik, sondern die Annahme, die Definition sei vom Rechenmodell unabhängig.

Teil 7: Was vollhomomorphe Verschlüsselung nicht leistet

Der 2018 von einer Gruppe aus Industrie, Forschung und Behörden veröffentlichte Homomorphic Encryption Standard (HomomorphicEncryption.org, 21. November 2018; Autorenliste u. a. Albrecht, Chase, Goldwasser, Halevi, Laine, Lauter, Micciancio, Moody, Sahai, Vaikuntanathan) ist in diesem Punkt bemerkenswert offen. Er legt als Sicherheitsziel „Semantic Security or IND-CPA Security" fest – und benennt dann, was damit nicht abgedeckt ist.

Kein Schutz gegen einen aktiven Server. Das Dokument führt genau den Fall vor: Der Client lässt F(M) berechnen, die Cloud liefert aber ein Chiffrat von G(M) für eine andere Funktion G. Wörtlich: „This is an example of an active attack which is not ruled out by semantic security." Und weiter: „Such attacks are not addressed by the semantic security guarantee, countering them requires additional measures beyond the use of homomorphic encryption." FHE garantiert Vertraulichkeit der Eingaben, nicht Korrektheit des Ergebnisses. Wer Letztere braucht, braucht ein zusätzliches Verfahren.

Keine CCA2-Sicherheit – solange jeder rechnen darf. Die Malleabilität des Chiffrats ist bei FHE kein Defekt, sondern die gewünschte Eigenschaft: Wer das Chiffrat gezielt verändern kann, kann darauf rechnen. Loftus, May, Smart und Vercauteren formulieren in On CCA-Secure Fully Homomorphic Encryption (ePrint 2010/560) die gängige Lesart: „any encryption scheme which supports any form of homomorphic operation cannot be secure against adaptive chosen ciphertext attacks". Wichtig ist, wie dieser Satz dort steht: als Vorbemerkung, eingeleitet mit „It is well known that", ohne Beweis und ohne Quellenangabe. Die Theoreme der Arbeit betreffen etwas anderes – sie zeigen, dass „the basic Gentry scheme is not IND-CCA1", und dass eine geringfügige Modifikation einer Variante des Smart-Vercauteren-Verfahrens IND-CCA1 erreicht, „indeed PA-1".

Ein förmliches Unmöglichkeitsresultat gibt es nicht, und es wäre auch zu stark. Das Argument – Chiffrat verändern, Entschlüsselungsorakel befragen – setzt voraus, dass die homomorphe Operation öffentlich und unbeschränkt ausführbar ist. Nimmt man eine der beiden Voraussetzungen weg, lässt sich CCA-artige Sicherheit erreichen: Prabhakaran und Rosulek (ICALP 2008) definieren CCA-Sicherheit relativ zu einer erlaubten Transformationsmenge; Boneh, Segev und Waters beschränken mit Targeted Malleability (ITCS 2012) die Malleabilität auf „a specific set of ‚allowable' functions"; und Emura und Koautoren (PKC 2013) binden die homomorphe Operation an einen eigenen geheimen Auswertungsschlüssel – „By introducing a secret key for homomorphic operations, we can control who is allowed to perform the homomorphic operation." Für das Cloud-Szenario, in dem genau jeder rechnen können soll, bleibt die Aussage praktisch richtig – aber sie ist eine Folge der Architektur, nicht ein Satz der Kryptographie.

Keine Geheimhaltung der Berechnung, jedenfalls nicht von selbst. Dass das Chiffrat verbirgt, welche Operationen zu ihm geführt haben, nennt der Standard „a desirable additional security property beyond semantic security" – also eine wünschenswerte zusätzliche, nicht eine vorhandene Eigenschaft. Für BGV heißt es, die Auswertungsalgorithmen könnten erweitert werden, um Evaluation Privacy „with respect to semi-honest adversaries" zu bieten; für BFV wird eine entsprechende Erweiterung genannt, dort ohne diese ausdrückliche Angreiferqualifikation. Das ist eine Option, kein Defaultverhalten.

Die Nachbartechnologien, fair verglichen

Confidential Computing löst dasselbe Grundproblem (data in use), indem es das Vertrauen auf den Chiphersteller und eine Attestierung verschiebt. FHE löst es über eine Härteannahme und braucht dafür keinen vertrauenswürdigen Hardwarehersteller – zahlt aber mit vier bis fünf Größenordnungen Rechenzeit, mit dem Schaltkreismodell und damit, dass Confidential Computing die Integrität der Berechnung mitattestiert, während FHE sie laut dem oben zitierten Standard gerade nicht garantiert.

Zero-Knowledge-Beweise adressieren die andere Hälfte, aber anders, als die Kurzformel nahelegt. Sie leisten zwei Dinge: Soundness, also dass ein falscher Satz den Prüfer nicht überzeugt, und Zero-Knowledge, also dass der Prüfer über den privaten Zeugen nichts erfährt, was er nicht schon wusste – die ZKProof Community Reference formuliert es als Eigenschaft, nichts über den Zeugen zu verraten „beyond what the attacker may already know about the witness from other sources". Zero-Knowledge ist also eine Vertraulichkeitseigenschaft der Eingaben. Was ZK nicht leistet, ist Auslagerung: Beim ZK-Beweis rechnet der Dateneigner selbst, weil er den Zeugen kennt. FHE erlaubt umgekehrt einem Dritten das Rechnen auf Daten, die er nie sieht, garantiert dafür aber nicht, dass er das Richtige gerechnet hat. Die beiden Verfahren sind komplementär, nicht konkurrierend.

Differential Privacy schützt eine andere Sache – nicht die Daten auf dem Weg zur Berechnung, sondern den Einzelnen im veröffentlichten Ergebnis. Dass die CKKS-Reparatur mit einem DP-Mechanismus arbeitet, ist weniger ein Zufall als die saubere Analyse einer alten Technik: Rauschüberdeckung ist in der Gitterkryptographie seit Langem üblich; die Differential-Privacy-Rechnung liefert erstmals nahezu scharfe obere und untere Schranken für die nötige Menge.

Teil 8: Wo es heute tatsächlich läuft

Der häufigste Einwand gegen FHE lautet, es sei Forschung. Das ist seit 2024 nicht mehr richtig – allerdings in einer sehr spezifischen Form.

Apple hat am 30. Juli 2024 (Beitrag von Fabian Boemer, Karl Tarbe und Rehan Rishi) die Bibliothek swift-homomorphic-encryption als Open Source veröffentlicht. Sie implementiert das Brakerski-Fan-Vercauteren-Verfahren (BFV). Die genannte Produktanwendung ist Live Caller ID Lookup in iOS 18: Der Dienst „uses homomorphic encryption to send an encrypted query to a server that can provide information about a phone number without the server knowing the specific phone number in the request". Technisch ist es ein Private-Information-Retrieval-Verfahren: ein Schlüssel-Wert-Lookup, bei dem der Server das abgefragte Schlüsselwort nicht erfährt. Der Beitrag hält ausdrücklich fest: „the server itself never decrypts the original data or even has access to the decryption key."

Zwei Einschränkungen gehören dazu. Erstens stellt der Beitrag keine Chiffratgrößen oder Latenzen in den Vordergrund; die im Beispielcode benannte Parametermenge ist ausdrücklich markiert („These encryption parameters are insecure, suitable for testing only."), und für die Produktanwendung heißt es nur, sie verlange „BFV parameters with post-quantum 128-bit security", ohne konkrete Werte. Welches PIR-Protokoll verwendet wird, ist aus den veröffentlichten Dokumenten nicht ersichtlich.

Zweitens, und das ist die wichtigere Einordnung: Live Caller ID Lookup ist ein Lookup, keine beliebige Berechnung. PIR gehört zu den FHE-Anwendungen mit dem günstigsten Verhältnis von Nutzen zu Kosten, weil die Schaltkreisform fest und ihre Tiefe vorab bekannt und anfrageunabhängig ist – es wird kein Bootstrapping gebraucht, das Verfahren bleibt leveled. Flach ist der Schaltkreis dagegen nicht: Die gängigen Single-Server-Konstruktionen setzen gerade auf homomorphe Multiplikation. MulPIR nutzt „multiplicative homomorphism to implement the recursion steps in PIR", ausdrücklich „at the cost of an increased computational cost for the server"; Spiral verwendet eine Folge externer Produkte zwischen Regev- und GSW-Chiffraten mit Rauschverwaltung und Modulus Switching und argumentiert dabei über das Rauschwachstum nach k sequentiellen Multiplikationen. Dass FHE hier produktiv läuft, ist ein echter Befund – aber er trägt nicht ohne weiteres auf beliebige Auslagerung von Geschäftslogik.

Faktenprüfung

Für diesen Artikel wurden 89 prüfbare Aussagen extrahiert und gegen die Primärquellen geprüft: 69 Aussagen der Klassen (a) harte Fakten, (b) wörtliche Zitate und (c) Quellenzuschreibungen – davon 47 mit Fakten-, 17 mit Zitat- und 14 mit Zuschreibungsanteil, wobei einzelne Aussagen in mehrere Klassen fallen – sowie 20 Synthese-Aussagen der Klasse (d). Die Prüfung erfolgte durch zwei getrennte Gutachter-Instanzen, die den Entwurf und die Quellenliste erhielten und den Auftrag hatten, Fehler zu finden; für die Synthese-Aussagen wurde zusätzlich aktiv nach Gegenevidenz und einschränkenden Folgearbeiten gesucht. Ergebnis: 60 BESTÄTIGT, 9 FALSCH, 17 ABZUSCHWÄCHEN, 3 NICHT PRÜFBAR. 29 Aussagen wurden korrigiert, abgeschwächt oder gestrichen.

Die wichtigsten Korrekturen:

1. Der Erklärmechanismus des CKKS-Angriffs war im Entwurf frei erfunden. Der Entwurf behauptete, das Restrauschen hänge vom geheimen Schlüssel ab und verrate ihn deshalb nach genügend Beobachtungen. Der tatsächliche Mechanismus ist das Gegenteil: Wer das approximative Entschlüsselungsergebnis m + e kennt und von der Chiffratkomponente abzieht, kürzt den Fehler heraus und erhält eine fehlerfreie lineare Gleichung – ein einziges Chiffrat genügt bei den üblichen Moduli. Teil 6 wurde entsprechend neu geschrieben.
2. Die Kernlehre von Teil 6 („exakt ist sicher, approximativ nicht") war falsch. Checri, Sirdey, Boudguiga und Bultel zeigen auf der CRYPTO 2024 denselben Angriffstyp gegen BFV, BGV und TFHE, weil auch die „exakten" Verfahren nicht perfekt korrekt entschlüsseln. Die Trennlinie wurde von „exakt gegen approximativ" auf „perfekte gegen nicht-perfekte Korrektheit" umgestellt – das verändert auch die Erkenntnis zum Mitnehmen.
3. Gentrys Bootstrapping-Theorem war ohne seine Zirkularitätsannahme wiedergegeben. Aus Bootstrappability folgt zunächst nur leveled FHE; unbegrenzte Tiefe mit einem Schlüsselpaar setzt voraus, dass die Verschlüsselung des geheimen Schlüssels unter dem eigenen öffentlichen Schlüssel sicher ist – eine aus keinem Standardproblem bewiesene Annahme. Der Abschnitt wurde ergänzt.

Weitere wesentliche Korrekturen: Der Entwurf verwechselte in der Squashing-Begründung die logarithmischen Abhängigkeiten – die auswertbare Tiefe hängt doppelt logarithmisch von den Rausch-Radien ab, die Gitterdimension steckt im Entschlüsselungsschaltkreis; die Behauptung, Bootstrapping sei für unbegrenzte Tiefe „unverzichtbar", wurde auf „das einzige aus Gitterannahmen bekannte Mittel" zurückgenommen, weil es eine Konstruktion aus Indistinguishability Obfuscation gibt; die Aussage, ein verschlüsselter Datenbankzugriff werde zwingend zum Volldurchlauf, wurde durch den Gegenbefund des doppelt effizienten PIR aus Ring-LWE relativiert, ebenso das Ausrollen von Schleifen durch die Turing-Maschinen-Konstruktion von Goldwasser et al.; die Zurückhaltung bei den Kostenzahlen war zu stark – die gemessene Einordnung von 10.000× bis 100.000× aus der MICRO-2021-Arbeit zu F1 wurde ergänzt, und „many orders of magnitude" wurde von der DARPA-Seite richtig als geforderte Reduktion statt als Ist-Zustand zugeordnet; die Darstellung von Zero-Knowledge-Beweisen als Verfahren, die „nicht die Vertraulichkeit der Eingaben" betreffen, war falsch und wurde ersetzt, der wirkliche Unterschied liegt in der Auslagerbarkeit; die CCA2-Aussage wurde von „grundsätzlich ausgeschlossen" auf „ausgeschlossen, solange die homomorphe Operation öffentlich und unbeschränkt ausführbar ist" zurückgenommen, mit den drei Gegenbeispielen Prabhakaran/Rosulek, Boneh/Segev/Waters und Emura et al.; „flach" wurde in der PIR-Begründung gestrichen, weil MulPIR und Spiral gerade auf homomorphe Multiplikation setzen; die Behauptung, die ISO-Reihe folge „genau" der Einteilung in Schemafamilien, wurde auf drei Mechanismenteile gegen vier Verfahren präzisiert und die Zuordnung als Lesart gekennzeichnet, da die Normtitel keine Verfahrensnamen nennen; Teil 5 der Normreihe ist kein „Eingeständnis", sondern die Normung eines bereits 2018 in der CHIMERA-Arbeit so motivierten Gedankens; „CKKS ist das Verfahren für maschinelles Lernen" wurde auf den arithmetischen Teil beschränkt, weil der Artikel selbst Aktivierungsfunktionen der Tabellenauswertung zuordnet; die Aussage über RAD78 und Vergleiche gegen Konstanten wurde auf das Ablesen des Vergleichsergebnisses eingegrenzt, weil sie sonst dem TFHE-Abschnitt widersprach; die OpenFHE-Zahl „under 100 ms" wurde den FHEW/TFHE-artigen Schemata zugeordnet statt nichtlinearen Operationen allgemein; Evaluation Privacy mit semi-honest-Qualifikation gilt laut Quelle für BGV, nicht für BFV; die Zuschreibung des Gentry-Zitats wurde vom Einleitungskapitel in den Abstract korrigiert; das Kreditinstitut von 1978 war ein kleines Kreditunternehmen bei einem Time-Sharing-Dienst; und „ein Vierteljahrhundert" widersprach der dreifach belegten Zahl von 31 Jahren. Drei nicht belegbare Aussagen über den Diskurs („wird im Vertriebsgespräch überdehnt", „wird regelmäßig übersprungen", „der lehrreichste Vorfall") wurden gestrichen oder als eigene Einschätzung gekennzeichnet, ebenso die negative Existenzaussage über fehlende Latenzangaben im Apple-Beitrag.

Hinweis: Automatisierte KI-Prüfung gegen Primärquellen; keine menschliche Fachprüfung. Offen bleibt in diesem Lauf, ob die ISO-Normtexte selbst BGV, BFV, CKKS und TFHE namentlich nennen – die abgerufenen Katalogseiten tun es nicht, die Normtexte waren nicht zugänglich. Die Stufen- und Datumsangaben der Tabelle stammen von den ISO-Komiteeseiten zum Abrufzeitpunkt und können inzwischen fortgeschritten sein.

Erkenntnis zum Mitnehmen

Vollhomomorphe Verschlüsselung wirkt auf den ersten Blick wie das Ende eines Dilemmas: Daten auslagern, ohne sie preiszugeben. Nach der Durchsicht der Primärliteratur bleiben drei Einsichten, die alle drei unbequem sind.

Die erste: FHE garantiert Vertraulichkeit der Eingaben, nicht Korrektheit des Ergebnisses. Das steht nicht im Kleingedruckten, sondern im Standard des Feldes selbst, mit einem ausgearbeiteten Beispiel: Der Server kann statt F(M) einfach G(M) rechnen, und semantische Sicherheit schließt das ausdrücklich nicht aus. Jede Architektur, in der aus dem Ergebnis einer ausgelagerten Berechnung eine Entscheidung folgt, braucht daher ein zweites Verfahren für die Integrität. Wer FHE einsetzt und über Integrität nicht gesprochen hat, hat nur die Hälfte des Problems gelöst – und möglicherweise die leichtere.

Die zweite: Das Kostenproblem ist nur zur Hälfte Kryptographie. Vier bis fünf Größenordnungen gegenüber Klartextrechnung sind die eine Hälfte. Die andere ist, dass die Berechnung in einen Schaltkreis gebracht werden muss, dessen Gestalt nicht von den Daten abhängen darf. Jedes if wird zu beiden Zweigen, jede Schleife zu ihrem Worst Case, jeder indizierte Zugriff zum Volldurchlauf. Es gibt theoretische Auswege, aber keine praktisch eingesetzten. Das heißt: Die Machbarkeitsfrage ist kein Benchmark, sondern eine Frage über die Form des eigenen Algorithmus.

Die dritte, und sie ist die allgemeinste: Die Sicherheitsdefinition ist Teil des Systems, nicht Teil der Theorie. CKKS war korrekt implementiert, die Mathematik stimmte, und das Verfahren erfüllte die Definition, auf die es gebaut war. Die vollständige Schlüsselwiederherstellung aus einem einzigen Chiffrat wurde möglich, weil das Verfahren eine Information herausgab – Klartext plus Restrauschen –, die das Angreifermodell nicht vorgesehen hatte. Und 2024 stellte sich heraus, dass dieselbe Lücke bei den „exakten" Verfahren besteht, weil deren Korrektheit nur mit hoher Wahrscheinlichkeit gilt. Die Trennlinie verläuft nicht zwischen exakt und approximativ, sondern zwischen perfekter und nicht-perfekter Korrektheit.

Der praktische Handlungsanstoß daraus ist eine einzige Frage, die sich an jedem geplanten FHE-Einsatz in einer Stunde klären lässt – und die darüber entscheidet, ob man im IND-CPA- oder im IND-CPA^D-Bedrohungsmodell steht: Verlassen Entschlüsselungsergebnisse jemals die Vertrauensgrenze des Schlüsselinhabers? Entschlüsselt nur der Dateneigner und behält das Ergebnis, ist die klassische Definition tragfähig. Sobald Ergebnisse geteilt, veröffentlicht oder in einem Threshold-Verfahren gemeinsam entschlüsselt werden, ist IND-CPA die falsche Messlatte, und man braucht die Rauschüberdeckung nach der Differential-Privacy-Rechnung – am Worst-Case-Fehler kalibriert, nicht am tatsächlichen.

Der konkrete erste Schritt, der sich in einer Woche tun lässt, wenn ein FHE-Vorhaben zur Debatte steht: Nimm die Berechnung, die ausgelagert werden soll, und schreibe sie als Schaltkreis auf – mit angegebener Multiplikationstiefe und mit jedem if explizit zu beiden Zweigen aufgelöst. Wenn das nicht in einer Seite gelingt, weil die Tiefe von den Daten abhängt, ist die Antwort auf die Machbarkeitsfrage schon gegeben, und zwar unabhängig von jedem Benchmark und jeder Hardwaregeneration.

Reflexionsfrage

Confidential Computing verlagert Vertrauen auf einen Chiphersteller und eine Attestierungskette – auf etwas, das man benennen, prüfen und vertraglich adressieren kann, das aber kompromittierbar ist. Vollhomomorphe Verschlüsselung verlagert es auf eine mathematische Härteannahme – und, bei unbegrenzter Tiefe, zusätzlich auf eine Zirkularitätsannahme, für die es keinen Härtebeweis gibt und die man niemandem gegenüber durchsetzen kann, weil sie keinen Adressaten hat.

Welches der beiden Vertrauen würdest du für ein konkretes Vorhaben lieber eingehen – und, wichtiger: an welcher Eigenschaft würdest du den Unterschied festmachen? Daran, dass das eine im Fall des Versagens bemerkbar wäre und das andere nicht? Daran, dass das eine einen Haftenden hat? Oder daran, dass mathematische Annahmen leise altern, Hardware aber laut bricht?

Und ändert sich deine Antwort, wenn du nicht der Auslagernde bist, sondern die Person, über deren Daten gerechnet wird?

Querverweise im Vault

• Rechnen im versiegelten Raum: Confidential Computing und die Grenzen des Nichtvertrauens – die direkte Alternative zum selben Problem data in use, mit umgekehrtem Vertrauensmodell: Silizium und Attestierung statt Härteannahme. Der entscheidende Unterschied, der in beiden Artikeln zusammenläuft: Confidential Computing attestiert die Integrität der Berechnung mit, FHE garantiert sie nicht.
• Beweisen ohne zu verraten: Zero-Knowledge-Beweise von Ali Babas Höhle bis zu zk-SNARKs – die komplementäre Hälfte: Korrektheit beweisen, ohne den Zeugen zu verraten. Genau das, was FHE fehlt – weshalb die beiden Verfahren in der Praxis kombiniert und nicht gegeneinander abgewogen werden.
• Der Zufall, der die Privatsphäre schützt: Differential Privacy und die Kunst, nichts über den Einzelnen zu verraten – der überraschende Berührungspunkt: Die Reparatur der CKKS-Sicherheitslücke ist ein Differential-Privacy-Mechanismus, der auf das Entschlüsselungsergebnis angewandt wird, mit nahezu scharfen Schranken für die nötige Rauschmenge.
• Ernte jetzt, entschlüssle später: Post-Quanten-Kryptographie und das Rennen gegen den Quantencomputer – dieselbe Gitterwelt von der anderen Seite. Learning With Errors und Ring-LWE tragen sowohl die Post-Quanten-Standards als auch jedes heutige FHE-Verfahren; wer einen davon bewertet, bewertet die Annahme beider.
• Der Mann, der drei Abkommen kippte: Max Schrems, der transatlantische Datentransfer und das Rätsel der Angemessenheit – die rechtliche Motivation hinter dem technischen Aufwand: FHE ist einer der wenigen Kandidaten für eine zusätzliche Maßnahme, bei der der Empfänger die Daten technisch nicht lesen kann. Was das Verfahren nicht leistet – Integrität, Verbergen der Berechnung – ist für diese Bewertung genauso relevant wie das, was es leistet.

Quellen und zum Weiterlesen

1. Ronald L. Rivest, Len Adleman, Michael L. Dertouzos: On Data Banks and Privacy Homomorphisms, in: Foundations of Secure Computation (Hrsg. DeMillo, Dobkin, Jones, Lipton), Academic Press 1978, S. 165–179. Geprüft wurden die Definition der privacy homomorphisms, die Beispielzählung, die Selbsteinschätzung zur Chosen-Plaintext-Anfälligkeit und die Grenze bei Vergleichen gegen Konstanten. PDF bei MIT CSAIL · BibTeX
2. Oded Regev: On Lattices, Learning with Errors, Random Linear Codes, and Cryptography; Ergebnisse ursprünglich 2005 veröffentlicht, geprüfte Fassung vom 2. Mai 2009. Geprüft wurden die LWE-Definition, Theorem 1.1 (Õ(n/α), αp > 2√n, GAPSVP/SIVP) und die Aussagen zur Quantennatur der Reduktion. PDF
3. Craig Gentry: A Fully Homomorphic Encryption Scheme, Dissertation, Stanford University, September 2009 – Bootstrapping, Squashing, die Tiefenabschätzungen und die zweite Härteannahme. PDF · Konferenzfassung: Fully Homomorphic Encryption Using Ideal Lattices, STOC 2009, DOI 10.1145/1536414.1536440 (Abstract · Publikationsnachweis)
4. Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan: Fully Homomorphic Encryption without Bootstrapping (BGV), 2011 – leveled FHE, Õ(λ·L³) pro Gatter, Õ(λ²) mit Bootstrapping, Õ(λ) mit Batching für breite Schaltkreise. ePrint 2011/277
5. Ran Canetti, Huijia Lin, Stefano Tessaro, Vinod Vaikuntanathan: Konstruktion von nicht-leveled FHE ohne Zirkularitätssicherheit, aus sub-exponentiell hartem Indistinguishability Obfuscation – Belegstelle für die Rolle der Zirkularitätsannahme in allen bootstrapping-basierten Konstruktionen. ePrint 2014/882
6. Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, Malika Izabachène: TFHE: Fast Fully Homomorphic Encryption over the Torus, Journal of Cryptology 2019 (Vollfassung von Asiacrypt 2016 und 2017) – 690 ms → 13 ms single core, 1 GB → 16 MB Bootstrapping-Schlüssel, 137 ms circuit bootstrapping, Lookup-Tabellen. ePrint 2018/421
7. Jung Hee Cheon, Andrey Kim, Miran Kim, Yongsoo Song: Homomorphic Encryption for Arithmetic of Approximate Numbers (CKKS), ASIACRYPT 2017 – Rescaling, Genauigkeitsschranke von höchstens einem zusätzlichen Bit, lineares Wachstum des Chiffratmoduls mit der Tiefe. ePrint 2016/421
8. Baiyu Li, Daniele Micciancio: On the Security of Homomorphic Encryption on Approximate Numbers, EUROCRYPT 2021 – passive Angriffe auf CKKS mit vollständiger Schlüsselwiederherstellung, getestet gegen HEAAN, SEAL, HElib und PALISADE; Einführung des Begriffs IND-CPA^D. ePrint 2020/1533
9. Baiyu Li, Daniele Micciancio, Mark Schultz, Jessica Sorrell: Securing Approximate Homomorphic Encryption Using Differential Privacy, CRYPTO 2022 – Gauß'sches Rauschen auf das Entschlüsselungsergebnis genügt für IND-CPA^D; am tatsächlichen statt am Worst-Case-Fehler kalibrierte Mechanismen bleiben angreifbar. ePrint 2022/816
10. Marina Checri, Renaud Sirdey, Aymen Boudguiga, Jean-Paul Bultel: On the practical CPA^D security of „exact" and threshold FHE schemes and libraries, CRYPTO 2024 – Verallgemeinerung des Angriffstyps auf BFV, BGV und TFHE über die nicht perfekte Entschlüsselungskorrektheit; besondere Exposition der Threshold-Varianten. ePrint 2024/116
11. Albrecht, Chase, Chen, Ding, Goldwasser, Gorbunov, Halevi, Hoffstein, Laine, Lauter, Lokam, Micciancio, Moody, Morrison, Sahai, Vaikuntanathan: Homomorphic Encryption Standard, HomomorphicEncryption.org, 21. November 2018 (v1.1) – IND-CPA als Sicherheitsziel, aktive Angriffe ausdrücklich nicht abgedeckt, Evaluation Privacy als wünschenswerte Zusatzeigenschaft. Standardseite
12. J. Loftus, A. May, N. P. Smart, F. Vercauteren: On CCA-Secure Fully Homomorphic Encryption – die gängige Lesart zur CCA2-Unmöglichkeit (dort als Vorbemerkung ohne Beweis), der CCA1-Angriff auf das Gentry-Basisverfahren und die PA-1-Konstruktion. ePrint 2010/560
13. Dan Boneh, Gil Segev, Brent Waters: Targeted Malleability: Homomorphic Encryption for Restricted Computations, ITCS 2012 – Beschränkung der Malleabilität auf eine zulässige Funktionsmenge als Weg zu CCA-artiger Sicherheit. ePrint 2011/311; ergänzend Prabhakaran/Rosulek, Homomorphic Encryption with CCA Security, ICALP 2008 (ePrint 2008/079) und Emura et al., PKC 2013, zum geheimen Auswertungsschlüssel (ePrint 2013/390)
14. Nikola Samardzic, Axel Feldmann, Aleksandar Krastev, Srinivas Devadas, Ronald Dreslinski, Christopher Peikert, Daniel Sanchez: F1: A Fast and Programmable Accelerator for Fully Homomorphic Encryption, MICRO 2021 – die gemessene Einordnung „10,000× to 100,000× slower than unencrypted computation" für optimierte Software-FHE sowie der Hinweis auf Datenbewegung als Flaschenhals. arXiv-PDF
15. DARPA: Data Protection in Virtual Environments (DPRIVE) – Programmseite, als abgeschlossen markiert; Ziel „within a factor of ten of unencrypted computations", Reduktionsvorgabe „by many orders of magnitude". darpa.mil
16. Al Badawi, Alexandru, Bates, Bergamaschi, Cousins, Erabelli, Genise, Halevi, Hunt, Kim, Lee, Liu, Micciancio, Pascoe, Polyakov, Quah, Saraswathy, Rohloff, Saylor, Suponitsky, Triplett, Vaikuntanathan, Zucca: OpenFHE: Open-Source Fully Homomorphic Encryption Library, WAHC 2022 – Schemaabdeckung, „fast functional bootstrapping (under 100 ms)" für die FHEW/TFHE-artigen Schemata, relative Modus-Kosten von 1,2× bis 1,5×. ePrint 2022/915
17. Shafi Goldwasser, Yael Tauman Kalai, Raluca Ada Popa, Vinod Vaikuntanathan: How to Run Turing Machines on Encrypted Data, CRYPTO 2013 – der Nachteil des Schaltkreismodells und eine Konstruktion, deren Kosten an der tatsächlichen Laufzeit hängen. ePrint 2013/229; sowie Wei-Kai Lin, Ethan Mook, Daniel Wichs: Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE, CRYPTO 2023 – sublineare Serverlaufzeit nach Vorverarbeitung. ePrint 2022/1703
18. ISO/IEC JTC 1/SC 27: Normreihe ISO/IEC 28033 Information security — Fully homomorphic encryption, Teile 1 bis 5 – Titel, Stufencodes und Stufendaten zum Abrufzeitpunkt. Teil 1 · Teil 2 · Teil 3 · Teil 4 · Teil 5
19. Fabian Boemer, Karl Tarbe, Rehan Rishi: Announcing Swift Homomorphic Encryption, swift.org, 30. Juli 2024 – BFV-Implementierung, Live Caller ID Lookup in iOS 18 als PIR-Anwendung, Aussagen zum Schlüsselzugriff des Servers. swift.org
20. Christina Boura, Nicolas Gama, Mariya Georgieva, Dimitar Jetchev: CHIMERA: Combining Ring-LWE-based Fully Homomorphic Encryption Schemes, 2018 – Verfahrenswechsel als Antwort auf Standardisierungsinitiativen und gemeinsame APIs. ePrint 2018/758; ergänzend zu PIR-Konstruktionen mit homomorpher Multiplikation: Ali et al., Communication-Computation Trade-offs in PIR (MulPIR), USENIX Security 2021 (ePrint 2019/1483)

Hinweis: Dieser Artikel ist eine fachliche Darstellung des Forschungs- und Normungsstands und keine Sicherheitsberatung für ein konkretes Vorhaben. Die Angaben zum Normungsstand der ISO/IEC-28033-Reihe beruhen auf den Komiteeseiten zum Abrufzeitpunkt und sollten vor einer Entscheidung erneut geprüft werden.

← All articles