Homomorphic Encryption

Der "Heilige Gral" der Kryptografie. Normalerweise: Um Daten zu bearbeiten (z. B. "Suche in E-Mails"), musst du sie entschlüsseln. In dem Moment sind sie sichtbar für den Server (Cloud). Homomorphe Verschlüsselung erlaubt Rechnen auf verschlüsselten Daten. Du schickst verschlüsselte Zahlen an die Cloud: Enc(5) und Enc(3). Die Cloud rechnet Enc(5) + Enc(3). Sie weiß nicht, was drin steht. Ergebnis ist Enc(8). Nur du (mit dem Schlüssel) kannst Enc(8) öffnen und "8" lesen. Die Cloud rechnet blind.

Merksatz: Ein Verschlüsselungsverfahren, das es ermöglicht, Berechnungen auf verschlüsselten Daten (Chiffrat) durchzuführen, sodass das entschlüsselte Ergebnis dem entspricht, als hätte man die Berechnungen auf den Klartextdaten ausgeführt.

Noch sehr wenig. Es ist extrem langsam (Faktor 1.000 bis 1.000.000 langsamer als Klartext). Aber es kommt:

Microsoft SEAL / Google Transpiler: Bibliotheken für FHE (Fully Homomorphic Encryption).
Private AI: Medizinische Datenanalyse in der Cloud, ohne dass die Cloud Patientendaten sieht.

1. Noise Growth

Die Verschlüsselung basiert auf Lattice Cryptography (Gitter). Man addiert Rauschen zur Sicherheit. Bei jeder Rechenoperation (Plus, Mal) wächst das Rauschen. Wenn zu viel Rauschen da ist, kann man nicht mehr entschlüsseln. Gentrys Trick (Bootstrapping): Man führt die Entschlüsselung homomorph im Chiffrat aus, um das Rauschen zu resetten. Das ist extrem rechenaufwendig.

2. Typen

PHE (Partially): Kann nur Plus ODER Mal (z. B. RSA, Paillier). Schnell.
SHE (Somewhat): Kann Plus und ein bisschen Mal (begrenzte Tiefe).
FHE (Fully): Kann alles beliebig oft. (Der Gral, seit 2009 möglich, aber langsam).

1. Gentry's Bootstrapping (The Breakthrough)

Bis 2009 dachte man, FHE sei unmöglich, da das Rauschen (Noise) bei Mal-Operationen exponentiell wächst. Craig Gentry löste dies durch Bootstrapping: Man nimmt ein Chiffrat $C$ (mit viel Rauschen) und den verschlüsselten geheimen Schlüssel $SK_{enc}$. Man lässt den Computer die Entschlüsselungs-Funktion homomorph ausführen. Das Ergebnis ist ein neues Chiffrat des gleichen Inhalts, aber mit dem "frischen" Rauschen der Entschlüsselungs-Operation. Es ist, als würde man ein schmutziges Paket in ein sauberes Paket umverpacken, ohne das Paket jemals zu öffnen. Dies ist der rechenintensivste Schritt in der modernen Kryptographie.

2. Modulus Switching & Leveled HE

Da Bootstrapping so teuer ist, nutzt man in der Produktion oft Leveled Homomorphic Encryption. Anstatt das Rauschen zu resetten, nutzt man Modulus Switching: Man verkleinert den Modul des Zahlensystems schrittweise nach jeder Operation. Das reduziert das Rauschen proportional mit, verringert aber auch die Präzision. Für Anwendungen wie "Durchschnittsberechnung über 1000 Patientendaten" reicht das oft aus, ohne dass man das extrem teure Bootstrapping benötigt.

3. RLWE (Ring Learning With Errors)

Moderne FHE-Verfahren (wie BFV, BGV oder CKKS) basieren nicht auf einfachen Gittern, sondern auf Ringen von Polynomen. Dies erlaubt es, viele Datenpunkte gleichzeitig in ein einziges Chiffrat zu packen (SIMD - Single Instruction, Multiple Data). Ein einziges "verschlüsseltes Paket" kann z. B. 8192 Zahlen enthalten. Wenn man dieses Paket mit einem anderen Paket addiert, werden alle 8192 Zahlenpaare gleichzeitig addiert. Diese Vektorisierung ist der einzige Grund, warum FHE heute für bestimmte Big-Data-Anwendungen überhaupt in Reichweite der kommerziellen Nutzung ist.