Abstract:
Moderne Kryptographie erlaubt nicht nur, personenbezogene Daten im Internet zu schützen oder sich für bestimmte Dienste zu authentifizieren, sondern ermöglicht auch das Auswerten einer Funktion auf geheimen Eingaben mehrerer Parteien, ohne dass dabei etwas über diese Eingaben gelernt werden kann (mit der Ausnahme von Informationen, die aus der Ausgabe und eigenen Eingaben effizient abgeleitet werden können). Kryptographische Protokolle dieser Art werden sichere Mehrparteienberechnung genannt und eignen sich für ein breites Anwendungsspektrum, wie z.B. geheime Abstimmungen und Auktionen.
... mehr
Um die Sicherheit solcher Protokolle zu beweisen, werden Annahmen benötigt, die oft komplexitätstheoretischer Natur sind, beispielsweise, dass es schwierig ist, hinreichend große Zahlen zu faktorisieren. Sicherheitsannahmen, die auf physikalischen Prinzipien basieren, bieten im Gegensatz zu komplexitätstheoretischen Annahmen jedoch einige Vorteile: die Protokolle sind meist konzeptionell einfacher, die Sicherheit ist unabhängig von den Berechnungskapazitäten des Angreifers, und die Funktionsweise und Sicherheit ist oft für den Menschen leichter nachvollziehbar. (Zum Beispiel forderte das Bundesverfassungsgericht: „Beim Einsatz elektronischer Wahlgeräte müssen die wesentlichen Schritte der Wahlhandlung und der Ergebnisermittlung vom Bürger zuverlässig und ohne besondere Sachkenntnis überprüft werden können.“ (BVerfG, Urteil des Zweiten Senats vom 03. März 2009)). Beispiele für solche Annahmen sind physikalisch getrennte oder unkorrumpierbare Hardware-Komponenten (vgl. Broadnax et al., 2018), Write-Only-Geräte für Logging, oder frei zu rubbelnde Felder, wie man sie von PIN-Briefen kennt. Auch die aus der Quantentheorie folgende Nicht-Duplizierbarkeit von Quantenzuständen ist eine physikalische Sicherheitsannahme, die z.B. verwendet wird, um nicht-klonbares „Quantengeld“ zu realisieren.
In der vorliegenden Dissertation geht es neben Protokollen, die die Sicherheit und Isolation bestimmter einfacher Hardware-Komponenten als Vertrauensanker verwenden, im Besonderen um kryptographischen Protokolle für die sichere Mehrparteienberechnung, die mit Hilfe physikalischer Spielkarten durchgeführt werden. Die Sicherheitsannahme besteht darin, dass die Karten ununterscheidbare Rückseiten haben und, dass bestimmte Mischoperationen sicher durchgeführt werden können. Eine Anwendung dieser Protokolle liegt also in der Veranschaulichung von Kryptographie und in der Ermöglichung sicherer Mehrparteienberechnungen, die gänzlich ohne Computer ausgeführt werden können.
Ein Ziel in diesem Bereich der Kryptographie ist es, Protokolle anzugeben, die möglichst wenige Karten benötigen – und sie als optimal in diesem Sinne zu beweisen. Abhängig von Anforderungen an das Laufzeitverhalten (endliche vs. lediglich im Erwartungswert endliche Laufzeit) und an die Praktikabilität der eingesetzten Mischoperationen, ergeben sich unterschiedliche untere Schranken für die mindestens benötigte Kartenanzahl. Im Rahmen der Arbeit wird für jede Kombination dieser Anforderungen ein UND-Protokoll – ein logisches UND zweier in Karten codierter Bits; dieses ist zusammen mit der Negation und dem Kopieren von Bits hinreichend für die Realisierung allgemeiner Schaltkreise – konstruiert oder in der Literatur identifiziert, das mit der minimalen Anzahl an Karten auskommt, und dies auch als Karten-minimal bewiesen. Insgesamt ist UND mit vier (für erwartet endliche Laufzeit (Koch, Walzer und Härtel, 2015; Koch, 2018)), fünf (für praktikable Mischoperationen oder endliche Laufzeit (Koch, Walzer und Härtel, 2015; Koch, 2018)) oder sechs Karten (für endliche Laufzeit und gleichzeitig praktikable Mischoperationen (Kastner et al., 2017)) möglich und optimal.
Für die notwendigen Struktureinsichten wurden so-genannte „Zustandsdiagramme“ mit zugehörigen Kalkülregeln entwickelt, die eine graphenbasierte Darstellung aller möglichen Protokolldurchläufe darstellen und an denen Korrektheit und Sicherheit der Protokolle direkt ablesbar sind (Koch, Walzer und Härtel, 2015; Kastner et al., 2017). Dieser Kalkül hat seitdem eine breite Verwendung in der bereichsrelevanten Literatur gefunden. (Beweise für untere Schranken bzgl. der Kartenanzahl werden durch den Kalkül zu Beweisen, die zeigen, dass bestimmte Protokollzustände in einer bestimmten kombinatorischen Graphenstruktur nicht erreichbar sind.) Mit Hilfe des Kalküls wurden Begriffe der Spielkartenkryptographie als C-Programm formalisiert und (unter bestimmten Einschränkungen) mit einem „Software Bounded Model Checking“-Ansatz die Längenminimalität eines kartenminimalen UND-Protokolls bewiesen (Koch, Schrempp und Kirsten, 2019).
Darüber hinaus werden konzeptionell einfache Protokolle für den Fall einer sicheren Mehrparteienberechnung angegeben, bei der sogar zusätzlich die zu berechnende Funktion geheim bleiben soll (Koch und Walzer, 2018), und zwar für jedes der folgenden Berechnungsmodelle: (universelle) Schaltkreise, binäre Entscheidungsdiagramme, Turingmaschinen und RAM-Maschinen. Es wird zudem untersucht, wie Karten-basierte Protokolle so ausgeführt werden können, dass die einzige Interaktion darin besteht, dass andere Parteien die korrekte Ausführung überwachen. Dies ermöglicht eine (schwach interaktive) Programm-Obfuszierung, bei der eine Partei ein durch Karten codiertes Programm auf eigenen Eingaben ausführen kann, ohne etwas über dessen interne Funktionsweise zu lernen, das über das Ein-/Ausgabeverhalten hinaus geht. Dies ist ohne derartige physikalische Annahmen i.A. nicht möglich. Zusätzlich wird eine Sicherheit gegen Angreifer, die auch vom Protokoll abweichen dürfen, formalisiert und es wird eine Methode angegeben um unter möglichst schwachen Sicherheitsannahmen ein passiv sicheres Protokoll mechanisch in ein aktiv sicheres zu transformieren (Koch und Walzer, 2017).
Eine weitere, in der Dissertation untersuchte physikalische Sicherheitsannahme, ist die Annahme primitiver, unkorrumpierbarer Hardware-Bausteine, wie z.B. einen TAN-Generator. Dies ermöglicht z.B. eine sichere Authentifikation des menschlichen Nutzers über ein korrumpiertes Terminal, ohne dass der Nutzer selbst kryptographische Berechnungen durchführen muss (z.B. große Primzahlen zu multiplizieren). Dies wird am Beispiel des Geldabhebens an einem korrumpierten Geldautomaten mit Hilfe eines als sicher angenommenen zweiten Geräts (Achenbach et al., 2019) und mit möglichst schwachen Anforderungen an die vorhandenen Kommunikationskanäle gelöst. Da das angegebene Protokoll auch sicher ist, wenn es beliebig mit anderen gleichzeitig laufenden Protokollen ausgeführt wird (also sogenannte Universelle Komponierbarkeit aufweist), es modular entworfen wurde, und die Sicherheitsannahme glaubwürdig ist, ist die Funktionsweise für den Menschen transparent und nachvollziehbar.
Insgesamt bildet die Arbeit durch die verschiedenen Karten-basierten Protokolle, Kalküle und systematisierten Beweise für untere Schranken bzgl. der Kartenanzahl, sowie durch Ergebnisse zur sicheren Verwendung eines nicht-vertrauenswürdigen Terminals, und einer Einordnung dieser in eine systematische Darstellung der verschiedenen, in der Kryptographie verwendeten physikalischen Annahmen, einen wesentlichen Beitrag zur physikalisch-basierten Kryptographie.
Abstract (englisch):
Modern cryptography does not only enable to protect your personal data on the Internet, or to authenticate for certain services, but also evaluate a function on private inputs of multiple parties, without anyone being able to learn something about these inputs (with the exception of knowledge that can be deduced from the output and own inputs efficiently). Cryptographic protocols of this type are called secure multiparty computation and are suitable for a broad spectrum of applications, such as for voting or auctions, where the vote or bid should remain private.
To prove security of such protocols, one needs assumptions that are often complexity-theoretic in nature – for example that it is difficult to factorize sufficiently large numbers. ... mehrSecurity assumptions that are based on physical principles exhibit quite some advantages when compared to complexity-theoretic assumptions: the protocols are often conceptually simpler, the security is independent of the computational power of an attacker, and the functioning and security is often more transparent to humans. (For example, the German Constitutional Court demanded: “When electronic voting machines are deployed, it must be possible for the citizen to check the essential steps in the election act and in the ascertainment of the results reliably and without special expert knowledge.” (BVerfG, Judgment of the Second Senate of 03 March 2009).) Examples of such assumptions are physically isolated or incorruptible hardware components (cf. Broadnax et al., 2018), write-only devices for logging, or scratch-off cards as common in letters for personal PINs. Also, the non-cloneability of quantum states that follows from the principles of quantum theory, is a physical security assumption that is, e.g., used to realize non-cloneable “quantum money”.
This dissertation covers, besides protocols that use the security of certain simple hardware components as a trust anchor, particularly cryptographic protocols for secure multiparty computation that is executed with the help of a deck of physical playing cards. The security assumption is that the cards have indistinguishable backs and that certain shuffling actions can be performed securely. One application of these protocols is a didactic method to illustrate cryptography and to allow for secure multiparty computation that can be performed completely without any computer/hardware involved.
In this area of cryptography, researchers aim to construct protocols using a minimal number of cards – and to prove them optimal in this sense. Depending on the requirements posed to running time (finite vs. finite only in expectation) and to the practicability of the used shuffles, one can derive different lower bounds for the necessary number of cards. This thesis derives a lower bound for all combinations of these requirements in the case of AND – a logical AND of two bits encoded in cards; together with negation and duplication of bits, this is sufficient for computing arbitrary circuits – and constructs or identifies protocols in the literature that use this minimal number of cards. In total, AND is possible and optimal with four (in the case of expectedly finite running time (Koch, Walzer, and Härtel, 2015; Koch, 2018)), five (in the case of requiring practicable shuffling or a finite running time (Koch, Walzer, and Härtel, 2015; Koch, 2018)) or six cards (for finite running time and simultaneously using only practicable shuffling (Kastner et al., 2017)).
For the necessary structural insights we developed “state diagrams”, a graph-based representation of all possible protocol runs, which allow for direct reading of correctness and security from the diagram (Koch, Walzer, and Härtel, 2015; Kastner et al., 2017). This method has since found broad usage in the area-relevant literature. (With this method, proofs of lower bounds with respect to the number of cards become proofs that certain protocol states are not reachable in the associated combinatorial graph structure.) Using this, we were able to formalize the respective notions of card-based cryptography as a C program and prove the run-minimality (given certain restrictions) of a card-minimal AND protocol using a Software Bounded Model Checking approach (Koch, Schrempp, and Kirsten, 2019).
Moreover, we give conceptionally simple protocols in the case of secure multiparty computation that additionally protects the function to be computed (Koch and Walzer, 2018) for each of the following computational models: (universal) circuits, branching programs, Turing machines and RAM machines. Furthermore, we give an analysis of how card-based protocols can be executed such that the only interaction is in the other parties watching for the correct execution of the protocol. This allows for (weakly interactive in the aforementioned sense) program obfuscation, where one party can execute a program encoded in cards on his own inputs, without learning anything about its internal workings, except what can be deduced from input- and output-behavior. This is in general impossible without such physical assumptions. Additionally, we formalize a security notion against active attackers and specify a method that – using very weak security assumptions – compiles a passively secure protocol fulfilling certain conditions into an actively secure version (Koch and Walzer, 2017).
A second physical security assumption analyzed in this thesis is to assume primitive, incorruptible hardware, such as a TAN generator. This allows for example a secure authentication of a human user via a corrupted/untrusted terminal, without requiring that the user conducts cryptographic computation by herself (such as multiplying large primes). A construction is given in the case of money withdrawal at a corrupted ATM with the help of a very simple trusted second device and with very weak security assumptions to the available communication channels (Achenbach et al., 2019). The given protocol remains secure when being run concurrently with other protocols (exhibits so-called Universal Composability security), was designed in a modular way, and uses a plausible security assumption. Hence, its functioning is transparent to humans.
Overall, by giving several card-based protocols, systematized proof methods for showing lower bounds and respective proofs, as well as our results for the secure utilization of a non-trusted terminal, together with a categorization of these into a systematic presentation of the different physical assumptions used in cryptography, this thesis presents a significant contribution to cryptography based on physical assumptions.
