Was ist homomorphe Verschlüsselung?

Homomorphic Encryption (HE) ermöglicht Berechnungen direkt auf verschlüsselten Daten. Das verschlüsselte Ergebnis entspricht nach der Entschlüsselung dem Ergebnis derselben Operationen auf den Klartextdaten. „Auf dem Chiffrat rechnen, ohne zu entschlüsseln.“

Stellen Sie sich vor, Sie legen Zahlen in eine verschlossene Box mit speziellen Handschuhen, die seitlich eingebaut sind. Sie können die Zahlen durch die Handschuhe hindurch verändern (addieren, multiplizieren), ohne die Box jemals zu öffnen. Nur die Person mit dem Schlüssel kann das Ergebnis sehen, wenn sie die Box aufschließt.

Partially Homomorphic Encryption unterstützt einen Operationstyp unbegrenzt: RSA (in der Lehrbuchvariante) ist multiplikativ homomorph: Enc(m1)*Enc(m2) = Enc(m1*m2). Paillier ist additiv homomorph: Enc(m1)*Enc(m2) = Enc(m1+m2). Eingesetzt bei elektronischen Wahlen und Private Information Retrieval.

Somewhat Homomorphic Encryption unterstützt sowohl Addition als auch Multiplikation, jedoch nur für eine begrenzte Anzahl von Multiplikationen (die Schaltungstiefe). Das Rauschen nimmt mit jeder Multiplikation zu; nach einem bestimmten Schwellenwert schlägt die Entschlüsselung fehl. Die erste Konstruktion stammt von Gentry (2009).

Fully Homomorphic Encryption unterstützt beliebige Berechnungen (jede boolesche oder arithmetische Schaltung) auf verschlüsselten Daten. Gentry (2009) zeigte, dass FHE durch „Bootstrapping“ möglich ist: Dabei wird die Entschlüsselungsschaltung homomorph ausgewertet, um das Chiffrat zu aktualisieren und das Rauschen zurückzusetzen.

Die meisten HE-Schemata basieren auf Gittern (BGV, BFV, CKKS). Bei der Verschlüsselung wird dem Chiffrat Rauschen hinzugefügt. Addition: Das Rauschen wächst additiv. Multiplikation: Das Rauschen wächst multiplikativ. Bootstrapping: Das Chiffrat wird homomorph entschlüsselt, wodurch das Rauschen auf sein ursprüngliches Niveau zurückgesetzt wird. Bootstrapping ist aufwendig.

FHE ist noch immer 10^6-mal langsamer als Berechnungen im Klartext. Die Verschlüsselung einer 32-Bit-Ganzzahl erfordert mehrere Kilobyte Chiffratdaten. Bootstrapping benötigt pro Gatter mehrere Sekunden. In der Praxis wird FHE für bestimmte Workloads eingesetzt: Inferenz mit maschinellem Lernen, Datenbankabfragen und Genomanalyse.

Die meisten HE-Schemata basieren auf dem schwierigen Problem Learning With Errors (LWE) oder Ring-LWE (RLWE), das als quantenresistent gilt. Ein Bruch von HE erfordert die Lösung von RLWE – es ist kein Quantenalgorithmus bekannt, der dabei eine wesentliche Beschleunigung bietet.

SEAL (Microsoft, unterstützt BFV/CKKS), HEAAN (Seoul National University, CKKS), OpenFHE (Open Source, BGV/BFV/CKKS/FHEW/TFHE), HElib (IBM, BGV). Alle sind für Forschungszwecke ausgelegt; Produktiveinsätze sind selten und domänenspezifisch.

Medizinische Genomik: Abfragen einer Gendatenbank, ohne Ihr Genom offenzulegen. Verschlüsselte ML-Inferenz: Die Cloud führt ein neuronales Netz mit Ihren Daten aus, ohne sie einsehen zu können. Private Analysen: Aggregieren von Statistiken über verschlüsselte Nutzerdaten. Berechnung finanzieller Risiken auf vertraulichen Portfolios.

HE: Eine Partei führt Berechnungen auf Daten aus, die von einer anderen Partei verschlüsselt wurden. MPC: Mehrere Parteien führen gemeinsam Berechnungen durch, ohne ihre Eingaben einander offenzulegen. Hybrid: HE für die Offline-Vorverarbeitung und MPC für interaktive Protokolle. Zielkonflikte: HE = hohe Latenz; MPC = Kommunikationsaufwand.

Was ist die wichtigste Einschränkung von Somewhat Homomorphic Encryption (SHE)?

Homomorphic Encryption ermöglicht Berechnungen auf Chiffraten. PHE unterstützt eine Operation; SHE unterstützt eine begrenzte Tiefe; FHE unterstützt mithilfe von Bootstrapping beliebige Schaltkreise. Die Verfahren basieren auf den schwierigen Problemen LWE/RLWE. Als Nächstes folgt die mathematische Grundlage von LWE.