Jenseits öffentlicher Schlüssel: funktionale Verschlüsselung

Herkömmliche Verschlüsselung mit öffentlichen Schlüsseln folgt einem einfachen Modell: Mit einem öffentlichen Schlüssel verschlüsseln und mit dem entsprechenden privaten Schlüssel entschlüsseln. Die entschlüsselnde Partei erhält die gesamte Klartextnachricht. Dieses Alles-oder-nichts-Modell ist für viele Anwendungen zu grob: Eine medizinische Datenbank könnte einem Arzt beispielsweise nur mitteilen wollen, ob ein Patient an einer bestimmten Erkrankung leidet, nicht aber die gesamte Krankenakte offenlegen. Funktionale Verschlüsselung begegnet dieser Einschränkung.

Die identitätsbasierte Verschlüsselung (IBE), die Shamir 1984 vorgeschlagen und Boneh und Franklin 2001 konstruiert haben, ermöglicht die Verwendung einer Identitätszeichenkette (E-Mail-Adresse, Domänenname oder Mitarbeiter-ID) als öffentlichem Schlüssel. Eine vertrauenswürdige Schlüsselinstanz erzeugt private Schlüssel für bestimmte Identitäten. IBE macht Zertifikate für öffentliche Schlüssel überflüssig und ermöglicht eine einfache Schlüsselverteilung. IBE ist die einfachste Form der funktionalen Verschlüsselung.

Die funktionale Verschlüsselung (FE), die Boneh, Sahai und Waters 2011 formal definiert haben, verallgemeinert IBE. In einem FE-Schema kann eine Schlüsselinstanz für jede Funktion f einen Funktionsschlüssel sk_f erzeugen. Mit einer Verschlüsselung Enc(x) und einem Funktionsschlüssel sk_f kann eine entschlüsselnde Partei f(x) berechnen, erfährt über x jedoch nichts weiter als das, was f(x) offenlegt. Die Funktion f kann jede berechenbare Funktion innerhalb der vom Schema unterstützten Funktionsklasse sein.

Funktionale Verschlüsselung für Skalarprodukte ermöglicht es einer entschlüsselnden Partei mit sk_y, aus der Verschlüsselung des Vektors x das Skalarprodukt <x, y> zu berechnen. Dies ermöglicht datenschutzwahrende Inferenz beim maschinellen Lernen: Verschlüsseln Sie den Merkmalsvektor x eines Benutzers, überlassen Sie dem Modelleigentümer sk_y für dessen Gewichtsvektor y, und dieser erfährt nur das Skalarprodukt (den unverarbeiteten Vorhersagewert), nicht jedoch die Merkmale des Benutzers. Es gibt mehrere praxistaugliche Verfahren für FE von Skalarprodukten (ABDALLA et al. 2016).

FE für Gleichheitstests ermöglicht es einer Partei zu prüfen, ob ein verschlüsselter Wert mit einem bestimmten Wert v übereinstimmt, wobei sie nur erfährt, ob die Gleichheit vorliegt. Dies ermöglicht datenschutzwahrende Datenbankabfragen: Ein Server verwaltet verschlüsselte Datensätze, und ein Benutzer fragt Datensätze ab, die bestimmten Werten entsprechen, ohne dass der Server erfährt, wonach der Benutzer sucht oder mehr über die Ergebnisse erfährt als eine Ja-Nein-Übereinstimmung. Praxistaugliche Konstruktionen verwenden bilineare Paarungen.

Die leistungsfähigste Form der FE unterstützt beliebige boolesche oder arithmetische Schaltkreise als Funktionen. Eine entschlüsselnde Partei mit sk_f für jede Funktion f, die in Polynomialzeit berechenbar ist, kann f(x) aus Enc(x) berechnen. FE für allgemeine Schaltkreise wurde von Garg, Gentry, Halevi, Raykova, Sahai und Waters (2013) mithilfe multilinearer Abbildungen theoretisch konstruiert. Bestehende Konstruktionen für allgemeine FE sind jedoch aufgrund ihrer Abhängigkeit von nicht ausgereiften Annahmen über multilineare Abbildungen unpraktikabel.

Ununterscheidbarkeits-Obfuskation (iO) ist das stärkste bekannte kryptografische Primitive und eng mit funktionaler Verschlüsselung verwandt. Ein iO-Schema nimmt eine Schaltung C und erzeugt eine obfuskierte Version O(C), die dieselbe Funktion berechnet, aber nichts über C preisgibt, was über dessen Ein-/Ausgabeverhalten hinausgeht. Aus iO lassen sich die meisten bekannten kryptografischen Primitive ableiten, einschließlich allgemeiner FE. Es existieren Kandidatenkonstruktionen auf Grundlage von Gitterproblemen, sie sind jedoch noch weit von einer praktischen Nutzung entfernt.

Attributbasierte Verschlüsselung (ABE) ist eine praktisch realisierbare Form der funktionalen Verschlüsselung, bei der die Funktion f auf eine Richtlinienauswertung beschränkt ist: f(x) = 1, wenn die Attributmenge x eine Richtlinie erfüllt, andernfalls 0. ABE ermöglicht eine fein abgestufte Zugriffskontrolle, bei der die Entschlüsselungsrechte von den Attributen eines Benutzers abhängen. ABE ist die am weitesten praktisch eingesetzte Form der funktionalen Verschlüsselung und wird unter anderem in Cloud-Speichern, im Gesundheitswesen und im IoT verwendet.

Die Geschichte der FE-Konstruktionen entwickelt sich von einfachen zu leistungsfähigen Verfahren: IBE (Boneh-Franklin 2001) → FE für Gleichheit (verschiedene Verfahren von 2005–2010) → FE für innere Produkte (ABDALLA 2016) → FE für Schaltungen begrenzter Tiefe (auf Grundlage multilinearer Abbildungen, 2013) → allgemeine FE (aus iO vermutet). Jeder Schritt ist leistungsfähiger, aber auch komplexer und weniger effizient. In der Praxis wird die einfachste Form eingesetzt, die die gewünschte Funktionalität ermöglicht.

Die Sicherheit von FE wird durch die Ununterscheidbarkeit der Verschlüsselungen zweier Nachrichten x0 und x1 definiert, selbst wenn Funktionsschlüssel für beliebige Funktionen f vorliegen, solange für alle abgefragten Funktionen f(x0) = f(x1) gilt. Dadurch wird sichergestellt, dass die entschlüsselnde Instanz genau f(x) und nichts darüber hinaus erfährt. Es gibt zwei Sicherheitsstufen: selektive Sicherheit (der Angreifer legt die Herausforderungsnachrichten fest, bevor er den öffentlichen Schlüssel sieht) und adaptive Sicherheit (vollständige simulationsbasierte Sicherheit).

Allgemeine FE ist weiterhin nicht praktisch einsetzbar, FE für innere Produkte und ABE können jedoch bereits heute eingesetzt werden. Zu den Herausforderungen gehören die erforderliche vertrauenswürdige Schlüsselautorität (ein einzelner Ausfallpunkt), die Komplexität des Schlüsselwiderrufs, der Leistungsaufwand durch Pairing-Operationen und die begrenzte Standardisierung. Zu den Forschungsrichtungen gehören FE mit mehreren Autoritäten (ohne eine einzelne vertrauenswürdige Autorität), die dezentrale Schlüsselerzeugung und FE für größere Funktionsklassen ohne multilineare Abbildungen.

Was unterscheidet die funktionale Verschlüsselung von der herkömmlichen Verschlüsselung mit öffentlichen Schlüsseln?

Die funktionale Verschlüsselung (Boneh-Sahai-Waters 2011) verallgemeinert IBE, indem sie Funktionsschlüssel sk_f ermöglicht, mit denen sich aus Enc(x) f(x) berechnen lässt, ohne x vollständig zu erfahren. Für FE für innere Produkte (private ML-Inferenz) und Gleichheitstests existieren praktische Konstruktionen. ABE ist ein praktisch eingesetzter Sonderfall zur Auswertung von Zugriffsrichtlinien. FE für allgemeine Schaltungen erfordert multilineare Abbildungen (unpraktikabel). iO ist das stärkste verwandte Primitive. Die zentrale Herausforderung besteht darin, von der Theorie zu einer effizienten Praxis zu gelangen.