Rechnen mit sieben Siegeln

Bisher werden Daten zwar beim Transport und zur Speicherung verschlüsselt, sie können aber nur im Klartext verarbeitet werden. Genau das will homomorphe Kryptografie ändern. Es geht dabei im Kern um das Rechnen mit verschlüsselten Daten, sodass diese im durchgehend verschlüsselten Zustand verarbeitet werden. Das wichtigste Einsatzgebiet dafür sind Cloud-Dienste und Cloud-Computing.

Durch eine effiziente Anwendung von homomorpher Kryptografie ließen sich sogar neue Geschäftsfelder erschließen. Klassisches Beispiel ist die Cloud-gestützte Verarbeitung von vertraulichen Medizindaten. Dies ist auch eines der Themen des aktuellen Forschungsrahmenprogramms Horizon 2020 der Europäischen Kommission.

Das Prinzip ist einfach: Weil die homomorphe Verschlüsselung die Struktur erhält, kann man die Daten verschlüsseln und mit dem Resultat weiterhin rechnen. Algebraisch homomorphe Systeme unterstützen die Addition und die Multiplikation. Als Resultat erhält man ein Ergebnis, das nur der Eigentümer der Daten mit seinem Schlüssel wieder dechiffrieren kann. Kompliziert wird es erst, wenn man die Details betrachtet.

Die Herausforderung

Die größte Herausforderung ist dabei aktuell die Tatsache, dass die Anzahl von hintereinander durchführbaren Rechenschritten auf verschlüsselten Daten begrenzt ist. Der mathematische Hintergrund ist die etwas ungenaue Verschlüsselung einer Klartextzahl. Werden zwei verschlüsselte Zahlen addiert, vergrößert sich die Ungenauigkeit, auch Rauschen genannt. Nach der Entschlüsselung verschwindet das Rauschen wieder, das Ergebnis ist korrekt.

Die Multiplikation jedoch ist die alles entscheidende Operation. Bei vielen homomorphen Systemen vergrößert sie das Rauschen exponentiell mit der Anzahl der Operationen. Nach einer Multiplikation ist das Rauschen verdoppelt, nach der zweiten vervierfacht, dann verachtfacht und so fort. Ein zu stark verrauschter Chiffretext lässt sich aber nicht mehr vernünftig entschlüsseln und führt zu falschen Ergebnissen.

Will man ein unbeschränkt lauffähiges System (fully homomorphic), muss man die Daten zwischendurch entrauschen. Das ist etwa mit dem sogenannten Bootstrapping durchaus möglich, es verschlingt aber im Vergleich zu den Nutzoperationen einen großen Teil der Rechenleistung. Mit einem nur teilweise homomorphen System lässt sich hingegen – bis zu einer bestimmten Komplexität – sehr effizient verschlüsselt rechnen.

Aktive Forschung

Homomorphe Verschlüsselung ist ein Bereich aktiver Forschung; die Szene ist sehr dynamisch. Beinahe wöchentlich werden neue Ansätze vorgestellt, alte Ansätze verbessert und alle Ansätze anscheinend irgendwie miteinander verknüpft. Neben der Verbesserung der theoretischen Grundlagen wird auch mit hohem Aufwand an konkreten Umsetzungen gearbeitet.

Die entstandenen Implementierungen sind aber noch meilenweit von einer effizienten Einsatzfähigkeit oder gar Standards entfernt. Über die Benutzbarkeit der Implementierungen für nicht gerade Krypto-affine Entwickler hüllen wir lieber den Mantel des Schweigens. Als eine Art Referenz-Implementierung gilt derzeit die Bibliothek HELib von Shai Halevi und Victor Shoup, die allerdings immer noch reichlich komplex und schwierig zu benutzen ist.

Anfang Dezember hat nun Microsoft Research ihre Simple Encrypted Arithmetic Library – kurz SEAL – veröffentlicht. Dabei kommt ein Kryptosystem namens YASHE zum Einsatz, mit dem sich bisher nur eine begrenzte Anzahl von verschlüsselten, arithmetischen Operationen hintereinander ausführen lassen. Diese Tatsache qualifiziert das Verfahren unter Experten als „somewhat homomorphic“, halbwegs homomorph.

SEAL könnte tatsächlich das sein, was Amerikaner als Game Changer bezeichnen: eine bahnbrechende Veränderung. Denn schon die Projektbeschreibung formuliert einen klaren Anspruch: „Eine einfach zu benutzende Bibliothek für homomorphe Verschlüsselung“. Auch der Entwickler Kim Laine betont, dass es hauptsächlich darum geht, selbst interessierten Laien den Zugang zu der Technologie zu ermöglichen.

Benutzbare Bibliothek

Der Einstieg in die homomorphe Verschlüsselung gestaltet sich mit SEAL tatsächlich denkbar einfach. Neben etwas Boilerplate-Code unter anderem zur Konfiguration der Schlüsselgeneratoren sind die ersten verschlüsselten, arithmetischen Operationen schnell umgesetzt.

  1 const int value1 = 5;
  2 const int value2 = -7;
  3 BigPoly encoded1 = encoder.encode(value1);
  4 BigPoly encoded2 = encoder.encode(value2);
  5 BigPoly encrypted1 = encryptor.encrypt(encoded1);
  6 BigPoly encrypted2 = encryptor.encrypt(encoded2);
  7 
  8 BigPoly encnegated1 = evaluator.negate(encrypted1);
  9 BigPoly encsum = evaluator.add(encrypted1, encrypted2);
 10 BigPoly encdiff = evaluator.sub(encrypted1, encrypted2);
 11 BigPoly encproduct = evaluator.multiply(encrypted1, encrypted2);
 12 
 13 BigPoly decryptedsum = decryptor.decrypt(encsum);
 14 int decodedsum = encoder.decode_int32(decryptedsum);
 

Das Code-Beispiel zeigt das grundsätzliche Vorgehen: Zunächst werden die Klartextzahlen als Polynom kodiert (encode), um sie dann per Verschlüsselung in den homomorphen Bildraum zu transferieren (encrypt). Dort können dann die verschlüsselten Operationen ausgeführt werden. Nach der Entschlüsselung des Ergebnisses muss dieses noch von der Polynomdarstellung in eine ganze Zahl zurückgewandelt werden.

Durch die homomorphe Verschlüsselung kann man alle Operationen der Evaluator-Klasse auch an ein externes System delegieren, ohne dass der Ausführende die Klartextzahlen zu Gesicht bekommt. Für die Verarbeitung der verschlüsselten Zahlen wird zur Laufzeit nur der Public-Key benötigt. Den geheimen Schlüssel braucht der Auftraggeber am Ende zur Entschlüsselung des Ergebnisses.

Da YASHE-Operationen das erwähnte Rauschen produzieren, muss man sich in SEAL als Entwickler mit zwei Funktionen behelfen, die in der Entwicklungsphase eines Programms mit verschlüsselten Zahlen Aufschluss über das Rauschen eines Operanden geben. So liefert inherent_noise() das tatsächliche gegenwärtige Rauschen eines Operanden und inherent_noise_max() das maximale Rauschen, bei dem unter der gewählten Parameter-Konfiguration noch eine Entschlüsselung möglich ist.

YASHE wählt den scheinbar umständlichen Umweg über die Polynome, weil dies ein recht effizienter Ansatz ist, Zahlen in eine so verschlüsselbare Form zu bringen, dass man damit dann noch vernünftig rechnen kann. Daneben existieren aber auch etliche andere Ansätze, wie die Darstellung als Gitter-Vektor in Form einer Matrix oder als zusammengesetzte Zahlen.

Die SEAL-Bibliothek bietet die Grundrechenarten auf ganzen (einschließlich negativen) und rationalen Zahlen, die auch in ausführlichem Beispiel-Code dokumentiert sind. Die hohe Kunst der homomorphen Kryptografie erfordert aber eigentlich nur die Addition und die Multiplikation natürlicher Zahlen. So lassen sich boolesche Ausdrücke aus AND- und XOR-Operationen und damit beliebige Schaltkreissimulationen und Programme herstellen.

Wer jetzt gleich loslegen möchte, kann sich die SEAL-Bibliothek etwa per Git aus dem Codeplex-Repository klonen und per GNU-C++ übersetzen. Zusätzlich liefert Microsoft nicht überraschend .NET-Wrapper mit. Anders als andere Implementierungen, die auf arithmetische Funktions-Kolosse wie GMP oder NTL aufsetzen, hat die Bibliothek keine externen Abhängigkeiten. Das erleichtert die Portierung auf Plattformen mit begrenzten Ressourcen.

Die Zukunft

Zum Kasten: Ein einfaches homomorphes Kryptoschema

Die Bibliothek wird in Kooperation mit der Forschungsgruppe Distributed Computing & Security (DCSec) der Leibniz Universität Hannover weiterentwickelt. Das Ziel ist dabei eine verschlüsselt rechnende Maschinen-Simulation. Dazu werden die booleschen Schaltkreise eines Prozessors so in arithmetische Formeln abgebildet, dass sie sich mit einem homomorphen Schema verschlüsselt berechnen lassen. Wichtigstes Schaltelement ist dabei der Multiplexer, der eine Auswahl aus mehreren Argumenten anhand eines Index gestattet. Das kann eine Speicheradresse oder auch eine elementare Befehlsfunktion (ein Opcode) sein.

Ein wichtiger Schritt in diese Richtung wird die Umsetzung eines sogenannten Bootstrapping-Mechanismus sein. Erst dieser erlaubt die unbegrenzte Anzahl von verschlüsselten Operationen, wie sie beispielsweise für die Implementierung eines Prozessors erforderlich ist.

Um das Versprechen einer sicheren Umgebung halten zu können, muss der verschlüsselte Prozessor bestimmten Konstruktionsregeln gehorchen: Damit ein Angreifer nicht etwa über einen Seitenkanal – also etwa die Laufzeit bestimmter Funktionen – nützliche Informationen ermitteln kann, müssen alle Operationen eine konstante Laufzeit aufweisen. Das Ziel ist, dass sich je zwei Maschinenzyklen nicht voneinander unterscheiden lassen. Das gelingt bisher im Prototyp, bis aber verschlüsselte Prozessoren mit vernünftiger Performance auf den Markt kommen, dürften noch ein paar Jahre vergehen. SEAL ist immerhin ein Beitrag, diesen Weg möglicherweise zu verkürzen.

Im derzeitigen Zustand lässt sich die Bibliothek durchaus schon für konkrete Anwendungen einsetzen. Laine hat darüber hinaus angekündigt, die Themen Bootstrapping, Performance und Vorschläge für Standards anzugehen, ohne jedoch schon einen konkreten Zeitplan vorzulegen. Angesichts der Klarheit und des Funktionsumfangs des verfügbaren Prototyps lohnt es sich aber zweifellos, am Ball zu bleiben. (ju@ct.de)

Links zu den Projektseiten: ct.de/yeyu