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:

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.
8. 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.
9. 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.
10. 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.
11. Ontologie (Kapitel 12), dieser Abschnitt klärt die notwendigen Begriffe und erlaubt einen direkten Einstieg in relevante Literatur.

Kontakt für Nachfragen: ec2@cyberagentur.de