Encryp­ted Computing – Ana­lyse & Verar­beitung Verschlüs­selter Daten (EC2)

Einführung zu Encrypted Computing/Privacy Enhancing Cryptography

Etablierte kryptographische Verfahren ermöglichen üblicherweise den Schutz vor ungewolltem Zugriff auf schützenswerte Daten während der Kommunikation mit anderen Parteien (data in transit) sowie während der Speicherung dieser Daten (data at rest). Mit diesen klassischen Verfahren ist es allerdings nicht möglich, Daten im verschlüsselten Zustand weiterzuverarbeiten. Dem stehen neuere kryptografische Konzepte wie Encrypted Computing (EC) und Privacy-Enhancing Cryptography (PEC) gegenüber: EC/PEC-Technologien wie Fully Homomorphic Encryption (FHE) und Multi Party Computation (MPC) erlauben es, Daten in verschlüsselter Form auch zu verarbeiten (data in use). Eine Entschlüsselung zum Klartext ist erst dann wieder nötig, wenn die Ergebnisse vom Auftraggeber/User eingesehen werden sollen; für die Berechnungen selbst ist dies aber nicht nötig. Sensible und sicherheitskritische Daten können so zwar analysiert, aber gleichzeitig auch vor unberechtigtem Zugriff geheim gehalten werden. EC/PEC-Verfahren decken somit alle drei Erscheinungsformen digitaler Daten ab und ermöglichen es, Datenschutz und Datennutzung flexibel miteinander zu vereinbaren.

Quanten- und Zukunftssicherheit

Neben der Einschränkung, dass viele gängige, klassische Verfahren (wie RSA) nur eingeschränkt Berechnungen in der verschlüsselten Domäne ermöglichen, drohen in naher Zukunft durch Quantencomputer die Gefahr, dass diese komplett gebrochen werden, weil die zugrundeliegenden mathematischen Probleme effizient gelöst werden können. Verfahren, die sich für homomorphe Verschlüsselung eignen, basieren auf anderen mathematischen Problemen, die nach derzeitigem Kenntnisstand, auch durch Quantencomputer nicht effizient lösbar sind. Sie gelten daher als quantensicher. Somit sind EC/PEC-Verfahren nach derzeitigem Stand der Forschung zukunftssicher.

Use-Case „Machine Learning as a Service“

Ein exemplarischer Use-Case für FHE im Bereich Machine Learning (ML) ist Machine Learning as a Service (MLaaS): In diesem Szenario bietet ein Serviceanbieter an, Daten über ein ML-Modell auszuwerten, möchte aber aus Geheimhaltungsgründen das Modell nicht offenlegen. Gleichzeitig möchten die Dateninhaber und Nutzer des Services ihrerseits gewisse Daten nicht im Klartext an den Serviceanbieter übermitteln. Normalerweise wäre eine Verarbeitung der Daten in diesem Setting nicht möglich, da keine Partei der anderen vertraut. Ein Lösungsansatz hierfür ist ein homomorphes Public-Key-Verfahren. Ein solches Verfahren ermöglicht es dem Dateninhaber, seine schützenswerten Daten homomorph zu verschlüsseln und dem Serviceanbieter, die Daten in verschlüsselter Form durch sein Modell in der verschlüsselten Domäne auszuwerten, ohne dabei die verschlüsselten Daten zu entschlüsseln. Der Serviceanbieter sendet dann das ebenfalls verschlüsselte Ergebnis zurück, das für den Dateninhaber mit seinem privaten Schlüssel in den Klartext umgewandelt werden kann. Der Schutz des Modells wird dadurch gewährleistet, dass dieses die ganze Zeit beim Serviceanbieter verbleibt, der Dateninhaber also keinen Zugriff auf dieses erhält.

Bisherige Einschränkungen

Auch wenn solche „verschlüsselten Berechnungen“ in der Theorie bereits möglich sind, sind die bekannten Verfahren in der Praxis noch oft zu langsam oder benötigen zu viel Arbeitsspeicher, um große Datenmengen zu verarbeiten. Ziel des Projektes ist es, neue Verfahren zu entwickeln oder bestehende Verfahren zu verbessern, sodass weitere Use-Cases auch in der Praxis abgedeckt werden können.

Vorstudie

Encrypted Computing Compass

1. Projektfragestellung:

Etablierte kryptographische Verfahren ermöglichen üblicherweise den Schutz vor ungewolltem Zugriff auf schützenswerte Daten während der Kommunikation mit anderen Parteien (data in transit) sowie während der Speicherung dieser Daten (data at rest). Die im Encrypted Computing Compass vorgestellten kryptografischen Techniken wie homomorphe Verschlüsselung und Multiparty Computation unterscheiden sich von den diesen klassischen Verfahren dadurch, dass sie auch eine Datenverarbeitung (data in use) in der verschlüsselten Domäne zulassen. Somit bleiben die Daten nicht nur während der Speicherung sondern auch während einer Berechnung verschlüsselt. Somit stellen diese Verfahren eine der höchsten Formen des Schutzes von Daten dar und sie erlauben es, weitere Use Cases abzudecken als die herkömmlichen Verfahren. So ist es beispielsweise mit homomorpher Verschlüsselung möglich, rechenintensive Aufgaben auf einen Cloudrechner auszulagern, selbst wenn man diesem keine Daten anvertrauen möchte.

Die Vorstudie „Encrypted Computing Compass“ stellt einen Überblick über den Stand der Technik im Bereich „Encrypted Computing“ dar und wird Ausgangspunkt für mindestens ein weiteres Projekt der Cyberagentur zum Bereich Encrypted Computing.

2. Projektpartner/Auftragnehmer:

3. Abstract der Veröffentlichung:

Daten bilden die Basis wichtiger ökonomischer oder gesellschaftlicher Entscheidungen und des wissenschaftlichen Fortschritts. Viele Daten, wie Firmengeheimnisse oder persönliche Daten, sollten aber geschützt sein. Daher wäre es wünschenswert, auf geheimen Daten rechnen zu können und Ergebnisse zu erhalten, ohne dass dafür Geheimnisse preisgegeben werden. Techniken der modernen Kryptographie erlauben ein Rechnen auf Geheimnissen und das vorliegende Dokument, der Encrypted Computing Compass, soll eine Einordnung dieser Techniken bieten und die Praxistauglichkeit der Lösungen beurteilen. Die moderne Kryptographie bietet, grob betrachtet, drei Ansätze um auf Geheimnissen zu rechnen:

1. Die vollhomomorphe Verschlüsselung (Fully Homomorphic Encryption, kurz FHE) ist ein Public Key Verschlüsselungsverfahren, mit dem Zahlen so verschlüsselt werden können, dass es möglich ist mit diesen verschlüsselten Zahlen zu rechnen, ohne die Zahlen selbst zu kennen. Die Ergebnisse der Berechnung bleiben verschlüsselte Zahlen und nur mit dem geheimen Schlüssel kann das Ergebnis entschlüsselt werden. FHE-Verfahren bilden den Schwerpunkt dieser Studie, da es gerade bei diese Verfahren in jüngster Zeit enorme Fortschritte gab und die Möglichkeiten und Grenzen dieser Verfahren nicht allgemein bekannt sind.
2. Sichere Mehrparteienberechnungen (Secure Multiparty Computations, kurz MPC), dies sind kryptographische Verfahren, bei denen mehrere Teilnehmer jeweils geheime Eingaben haben und gemeinsam auf diesen Eingaben rechnen wollen, ohne dass mehr bekannt wird als das Ergebnis der Berechnung. In der Theorie ist seit den 1980ern bekannt, dass es solche Verfahren für beliebige Berechnungen gibt, aber bei der Effizienz der Verfahren gab es inzwischen deutliche Fortschritte. Sichere Mehrparteienberechnungen werden in diesem Dokument als eine Alternative zu FHE-Verfahren betrachtet. Je nach Anwendung können sichere Mehrparteienberechnungen besser geeignet sein als FHE-Verfahren, insbesondere, wenn der Kommunikationsaufwand groß sein darf.
3. Sichere Enklaven beziehungsweise Trusted Execution Environments (TEEs), dies sind Hardwarebausteine, die eine sichere Berechnung so abkapseln, dass selbst der Betreiber der Hardware nicht an die geheimen Eingaben herankommt, oder die Ausgabe manipulieren kann. Enklaven und TEEs werden in diesem Dokument nur ganz am Rande betrachtet, weil sie, anders als FHE oder MPC, ein großes Vertrauen in den Hersteller der Enklave voraussetzen. Dennoch könnten Enklaven und TEEs, bei niedrigeren Anforderungen an die Sicherheit eine interessante Alternative sein, weil sie ohne Zusatzaufwand direkt auf den Geheimnissen rechen und somit eine durch andere Verfahren unerreichte Effizienz haben. Eine Kombination verschiedener Verfahren unterschiedlicher Effizienz und Sicherheit könnte ein vielversprechender Ansatz für die Zukunft sein.

Ziel dieses Dokuments ist das kompakte und verständliche Darlegen der wissenschaftlichen Grundlagen, auf denen FHE- und MPC-Verfahren beruhen, sowie eine Vorstudie der praktischen Machbarkeit für relevante Use-Cases. Das Dokument ist in folgende Abschnitte gegliedert:

Ontologie (Kapitel 12), dieser Abschnitt klärt die notwendigen Begriffe und erlaubt einen direkten Einstieg in relevante Literatur.

Gitterbasierte Kryptographie (Kapitel 2), in diesem Kapitel werden die mathematischen Grundlagen der gitterbasierten Verschlüsselungs-Verfahren motiviert und eingeführt, insbesondere werden die zugrundeliegenden Sicherheitsannahmen betrachtet, etwa, dass gitterbasierte Verfahren als sicher sogar gegen Quantencomputer eingeschätzt werden.

Gitterbasierte Verschlüsselungs-Verfahren (Kapitel 3), hier werden zwei konkrete Verschlüsselungsverfahren angegeben. Es sind Public-Key Verfahren, also Verfahren, bei denen jeder verschlüsseln, aber nur der Besitzer eines geheimen Schlüssels entschlüsseln kann. Diese gitterbasierten Verfahren erlauben schon eine Addition von verschlüsselten Geheimnissen und bilden die Grundlage der vollhomomorphen Verfahren.

Somewhat Homomorphic Encryption (Kapitel 4), dieses Kapitel erklärt die Grundlagen der vollhomomorphen Verschlüsselungs-Verfahren von den ersten Ansätzen bis zu den zur Zeit aktuellsten Verfahren der sogenannten vierten Generation.

Fully-Homomorphic Encryption (Kapitel 5), hier werden die verschiedenen vollhomomorphen Verfahren kurz vorgestellt, sowie die relevanten Forschungsgruppen und verfügbaren Bibliotheken. Dieses Kapitel spiegelt also den aktuellen Stand der Forschung und gibt die entscheidenden Referenzen für zukünftige Studien zur vollhomomorphen Verschlüsselung.

Fortgeschrittene Verfahren (Kapitel 6), hier werden Varianten von FHE-Verfahren vorgestellt, die zusätzliche Eigenschaften haben oder Vorteile bieten. Insbesondere Verfahren für numerische, d.h. näherungsweise Berechnungen, Verfahren, die mehr Teilnehmer erlauben, Verfahren, die Quantenberechnungen unterstützen oder das Obfuszieren von Schaltkreisen.

Sichere Mehrparteienberechnungen (MPC) (Kapitel 7), in diesem Kapitel werden Alternativen zu FHEVerfahren vorgestellt, die für einige Anwendungen eine effizientere Berechnung auf geheimen Daten erlauben, die aber einen signifikant höheren Kommunikationsaufwand haben.

Sichere Hardware (Kapitel 8) haben wir in diesem Dokument nur kurz betrachtet, weil großes Vertrauen in die Hardware und den Hersteller nötig sind, solange man die sichere Hardware nicht mit anderen Ansätzen kombiniert. Betrachtet werden Trusted Platform Modules (TPMs), die sicherstellen, dass nur bestimmte, zertifizierte Programme auf dem Computer laufen und sichere Enklaven, die Berechnungen wegkapseln können.

Anwendungen und Use-Cases (Kapitel 9), dieses Kapitel ist ein Herzstück der Vorstudie, da konkrete relevante Anwendungsbeispiele betrachtet werden sowie ihre Machbarkeit auf verschlüsselten Daten. Als Zusammenfassung der Use-Case Studie ergibt sich, dass bei Anwendungen, bei denen es weder auf die Kommunikationskomplexität noch auf die Lastbalancierung ankommt, die FHE-basierte Ansätze derzeit nicht mit alternativen Ansätzen konkurrenzfähig sind.

Benchmarks (Kapitel 10), in diesem Abschnitt wird ein FHE-Estimator vorgestellt, der als wesentlicher Teil dieser Vorstudie entwickelt und implementiert wurde. Dieser FHE-Estimator ist über eine Webseite erreichbar und kann basierend auf einem gegebenen Programm, den Aufwand abschätzen, der nötig wäre, um dieses Programm als Schaltkreis mit einem FHE-Verfahren durchzurechnen.

Entscheidungshilfen (Kapitel 11), dieser Abschnitt bietet, aufbauend auf den vorangegangenen Kapiteln, eine systematische Einordnung der verschiedenen verfügbaren Ansätze für das Rechnen auf Geheimnissen. Anhand von Fragen über eine geplante Anwendung wird Schritt für Schritt entschieden welcher Ansatz für die Anwendung am besten geeignet ist.