In cryptography, we do not know which computational assumptions are the most secure to rely on. Robust combiners attempt to solve this problem. Given several implementations of a certain primitive, e.g., of a commitment scheme, a combiner merges them into a new implementation that is secure if a minimum number of the input implementations are secure. A (k;n)-robust combiner merges n implementations, where k of them are required to remain secure. In this thesis, we investigate combiners for various primitives. We show which combiners for commitment schemes are possible and which combiners do not exist. We show that a certain combiner construction is impossible if only half of the input implementations are secure (technically speaking, we prove that transparent black-box (1; 2)-robust combiners for commitment schemes do not exist). Furthermore, we give explicit constructions for combiners where the majority of the input implementations are assumed to be secure. We make further investigations about combiners for interactive proof systems. However, this scenario is far more complicated and therefore, the statements made are somewhat crude. For oblivious transfer, a yet unpublished paper of Meier et al. proposes more tolerant constructions using a “swap” operation. We show that such an operation is necessary for certain types of combiners. Zusammenfassung Combiners werden in der Kryptographie verwendet, um sich gegen ungewisse berechenmassige Annahmen abzusichern. Gegeben sind Implementationen einer Primitive, zum Beispiel Bit Commitment. Ein Combiner verknupft diese Implementationen so, dass die Kombination sicher ist, wenn mindestens eine gewisse Anzahl der gegebenen Implementationen sicher ist. In dieser Arbeit befassen wir uns mit Combinern fur verschiedene Primitiven. Wir untersuchen, welche Combiners fur Commitment Schemes existieren und welche unmoglich sind. Wir zeigen, dass transparent black-box Combiner Konstruktionen nur moglich sind, falls die Mehrheit der gegebenen Implementationen sicher ist und konstruieren einen solchen Combiner. Weiter haben wir uns mit Combinern fur interaktive Beweissysteme befasst. Diese Ausgangslage ist viel komplizierter und die gemachten Aussagen sind eher einfacher Natur. Fur Oblivious Transfer werden in einer noch unveroffentlichten Arbeit von Meier et al. tolerantere Konstruktionen vorgeschlagen, welche nur mit einer “swap”-Operation funktionieren. Wir zeigen, dass eine Operation dieser Art notwendig ist.
In cryptography, we do not know which computational assumptions are the most secure to rely on. Robust combiners attempt to solve this problem. Given several implementations of a certain primitive, e.g., of a commitment scheme, a combiner merges them into a new implementation that is secure if a minimum number of the input implementations are secure. A (k;n)-robust combiner merges n implementations, where k of them are required to remain secure. In this thesis, we investigate combiners for various primitives. We show which combiners for commitment schemes are possible and which combiners do not exist. We show that a certain combiner construction is impossible if only half of the input implementations are secure (technically speaking, we prove that transparent black-box (1; 2)-robust combiners for commitment schemes do not exist). Furthermore, we give explicit constructions for combiners where the majority of the input implementations are assumed to be secure. We make further investigations about combiners for interactive proof systems. However, this scenario is far more complicated and therefore, the statements made are somewhat crude. For oblivious transfer, a yet unpublished paper of Meier et al. proposes more tolerant constructions using a “swap” operation. We show that such an operation is necessary for certain types of combiners. Zusammenfassung Combiners werden in der Kryptographie verwendet, um sich gegen ungewisse berechenmassige Annahmen abzusichern. Gegeben sind Implementationen einer Primitive, zum Beispiel Bit Commitment. Ein Combiner verknupft diese Implementationen so, dass die Kombination sicher ist, wenn mindestens eine gewisse Anzahl der gegebenen Implementationen sicher ist. In dieser Arbeit befassen wir uns mit Combinern fur verschiedene Primitiven. Wir untersuchen, welche Combiners fur Commitment Schemes existieren und welche unmoglich sind. Wir zeigen, dass transparent black-box Combiner Konstruktionen nur moglich sind, falls die Mehrheit der gegebenen Implementationen sicher ist und konstruieren einen solchen Combiner. Weiter haben wir uns mit Combinern fur interaktive Beweissysteme befasst. Diese Ausgangslage ist viel komplizierter und die gemachten Aussagen sind eher einfacher Natur. Fur Oblivious Transfer werden in einer noch unveroffentlichten Arbeit von Meier et al. tolerantere Konstruktionen vorgeschlagen, welche nur mit einer “swap”-Operation funktionieren. Wir zeigen, dass eine Operation dieser Art notwendig ist.
A (1,2)-robust combiner for a cryptographic primitive P is a construction that takes two candidate schemes for P and combines them into one scheme that securely implement P even if one of the candidates fails. Robust combiners are a useful tool for ensuring better security in applied cryptography, and also a handy tool for constructing cryptographic protocols. For example, we discuss using robust combiners for obtaining universal schemes for cryptographic primitives (a universal scheme is an explicit construction that implements P under the sole assumption that P exists). In this paper we study what primitives admit robust combiners. In addition to known and very simple combiners for one-way functions and equivalent primitives, we show robust combiners for protocols in the world of public key cryptography, namely for Key Agreement(KA). The main point we make is that things are not as nice for Oblivious Transfer (OT) and in general for secure computation. We prove that there are no “transparent black-box ” robust combiners for OT, giving an indication to the difficulty of finding combiners for OT. On the positive side we show a black box construction of a (2, 3)-robust combiner for OT, as well as a generic construction of (1, n)-robust OT-combiners from any (1, 2)-robust OT-combiner.
In der vorliegenden Arbeit behandeln wir verschiedene Themen aus dem Gebiet der Quanteninformationstheorie. Die unterschiedlichen Ergebnisse sollen entweder die Anwendung theoretischer Konzepte auf reale Experimente erleichtern oder bei der weiterfuhrenden Arbeit an zentralen Fragen helfen. Im Detail werden folgende Punkte untersucht: Wir wenden uns als Erstes der Fragestellung zu, unter welchen Vorraussetzungen eine gegebene Menge an Erwartungswerten mit den ersten beiden Momenten der Spinoperatoren eines Zustandes von Gesamtspin j kompatible ist. Hierbei liegt das Hauptaugenmerk auf einer operationellen Beschreibung, so dass man direkt mit den Momenten arbeiten kann, anstatt den kompletten Dichteoperator zu verwenden. Wir zeigen, dass diese Charakterisierung physikalischer Momente zu dem Problem der Bose-symmetrischen Erweiterungen fur speziell bestimmte Zweiqubit Zustande aquivalent ist. Mittels dieser Umformulierung bestimmen wir operationelle Teil- und Ubermengen der exakten Menge, um somit auf einfache Art und Weise Momente identifizieren zu konnen, die sicher physikalisch sind, als auch andere, die eindeutig inkompatibel mit den Vorhersagen der Quantenmechanik sind. Diese approximative Losung gewinnt mit steigender Gesamtspinzahl j an Genauigkeit, und konvergiert im Limes gegen die exakte Losung. Im nachsten Abschnitt beschaftigen wir uns mit dem Konzept der Verschrankungszeugen; der gebrauchlichsten Methode zur Verschrankungsdetektion. Wir untersuchen, wie man die Qualitat eines linearen Verschrankungszeugen durch quadratische, nichtlineare Terme verbessen kann, so dass man mehr verschrankte Zustande auf einmal detektiert. Das betrachtete Verbessungsschema hat den Vorteil dass man es iterative benutzen kann. Dies liefert eine Abfolge von Verschrankungszeugen mit Nichtlinearitaten immer hoherer Ordnung, deren Starke in jedem Schritt zunimmt. Die entwickelte Iterationsmethode kann fur verschiedene Aufgaben verwendet werden und wir betrachten zwei ausgezeichnete Extremfalle: Entweder optimieren wir fur einen vorgegeben Zielzustand oder fur alle moglichen Zustande gleichmassig. Im restlichen Teil der Arbeit untersuchen wir verschiedene Moglichkeiten, wie man bereits vorhandene Ideen besser an reale Experimente anpasst. Hier sei angemerkt dass viele Anwendungen der Quanteninformationstheorie nur fur stark idealisierte Systeme vorgeschlagen und diskutiert wurden und somit nicht direkt fur das Experiment anwendbar sind. Dieser Punkt ist fur das Feld der Quantenschlusselverteilung von besonderer Bedeutung, da man die vorbehaltslose Sicherheit eines realen, durch ein Experiment generierten Schlussels zeigen mochte und nicht nur fur die einer idealisierten Version davon. Mit diesem Ziel im Hinterkopf untersuchen wir zuerst die theoretische Idee des Squash Modells. Dieses bietet einen eleganten Ausrechentrick', der es erlaubt, die Sicherheitsanalyse eines idealisierten Quantenschlusselverteilungsprotokolls direkt fur das reale Experiment zu verwenden. Wir entwickeln einen Formalismus zur Prufung dieses Squash Modells fur einen gegebenen Messaufbau und betrachten relevante Messschemen mit und ohne dieser Eigenschaft. Im Gegensatz zu diesem theoretischen Modell behandlen wir auch eine experimentelle Moglichkeit, die es uns erlaubt, die Sicherheitsanalyse des idealisierten Systems direkt fur das reale Experiment zu verwenden. Dazu benutzen wir die Idee, dass man durch die Kombination eines variablen Strahlteilers mit einem einfachen Click/No-Click' Detektor, die Statistik von photonauflosenden Detektoren erhalten kann. Durch diese Hardwareanderung ist es moglich, die sicherheitsrelevanten Parameter direkt abzuschatzen. Diese Methode bietet somit auch einen Weg, die Sicherheit eines realen Quantenschlusselverteilungsexperiments zu beweisen, fur das die theoretische Squash Modell Idee nicht funktioniert. Als Ergebnis erhalt man unter anderem einen neuen Distanzrekord fur ein reales Quantenschlusselverteilungsexperiment mit derzeitiger Technologie. Als letzten Punkt betrachten wir das Problem der experimentellen Verschrankungsverifizierung. Bei dieser Verifizierung hat man oftmals ein Praktikabilitatsproblem, weil man---ob verschiedener Grunde---meistens nur ein sehr vereinfachtes Modell fur die verwendenten Messapparate benutzt. Wir zeigen, dass man in diesem Fall der Fehlinterpretation der beobachteten Messausgange durchaus Fehler machen kann, allerdings untersuchen wir in erster Linie Bedingungen, unter denen ein falschlicher Verschrankungsnachweis ausgeschlossen werden kann. Zu diesem Zweck verwenden wir ein dem Squash Modell ahnliches, aber weniger restriktives Konzept. Eine interessante Anwendung liefern die ublicherweise mittels Tomographie durchgefuhrten Verschrankungstests, die man typischerweise fur parametrische Fluoreszenz Quellen oder fur photonische Mehrparteienexperimente verwendet. Wir zeigen, dass diese sehr einfach fehlerfrei gemacht werden konnen.
A robust combiner for a cryptographic primitive gives a secure implementation of the primitive when at least some of the input candidates are secure. Such constructions provide robustness against insecure implementations and incorrect assumptions underlying the candidate schemes. Robust combiners are useful tools for ensuring better security in applied cryptography. Combiners from the perspective of threshold schemes have been previously studied. However, such threshold schemes typically fail to capture all possible scenarios. In this paper, we characterize the possibility of a transparent black-box combiner for oblivious transfer (OT), given an access structure over the candidate implementations. We also propose a circuit-based framework for the construction of such combiners, and hence reduce the problem of optimal OT combiners to circuit optimization.
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. 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.
It is well known that the secure computation of non-trivial functionalities in the setting of no honest majority requires computational assumptions. We study the way such computational assumptions are used. Specifically, we ask whether the secure protocol can use the underlying primitive (e.g., one-way trapdoor permutation) in a black-box way, or must it be nonblack-box (by referring to the code that computes this primitive)? Despite the fact that many general constructions of cryptographic schemes (e.g., CPA-secure encryption) refer to the underlying primitive in a black-box way only, there are some constructions that are inherently nonblack-box. Indeed, all known constructions of protocols for general secure computation that are secure in the presence of a malicious adversary and without an honest majority use the underlying primitive in a nonblack-box way (requiring to prove in zero-knowledge statements that relate to the primitive).In this paper, we study whether such nonblack-box use is essential. We present protocols that use only black-box access to a family of (enhanced) trapdoor permutations or to a homomorphic public-key encryption scheme. The result is a protocol whose communication complexity is independent of the computational complexity of the underlying primitive (e.g., a trapdoor permutation) and whose computational complexity grows only linearly with that of the underlying primitive. This is the first protocol to exhibit these properties.
Abgesehen davon, dass Subfaktoren ein interessantes mathematisches Gebiet für sich darstellen, haben sie auch die Aufmerksamkeit von Physikern erregt, da vermutet wird, dass es einen Zusammenhang zwischen Subfaktoren und konformen Feldtheorien (CFT) gibt. Obwohl inzwischen eine überzeugende Menge an Hinweisen für die Gültigkeit dieser Vermutung erbracht wurde, existieren immer noch einige Lücken: Es gibt eine Reihe außergewöhnlicher Subfaktoren, für die keine entsprechende CFT bekannt ist. Daher ist es notwendig, neue Techniken für die Konstruktion einer CFT aus einem Subfaktor zu entwickeln. Hier ist es sinnvoll, die zugrunde liegende mathematische Struktur genauer zu untersuchen: Aus den sogenannten ,,even parts'' eines Subfaktors ergeben sich zwei unitäre Fusionskategorien (UFCs). Ein vielversprechender Ansatz ist, aus diesen Kategorien Quantenspinsysteme zu konstruieren und zu untersuchen, um eine Verbindung zu CFTs zu finden. Das einfachste Beispiel, das neue Techniken zur Konstruktion einer CFT erfordert, ist der Haagerup Subfaktor, da er der kleinste Subfaktor mit einem Index größer als vier ist. In dieser Arbeit untersuchen wir mithilfe von ein- und zweidimensionalen Gittermodellen die Frage, ob eine CFT existiert, die zum Haagerup Subfaktor gehört. Die erste Aufgabe hierbei besteht darin, die F-Symbole der Kategorie zu berechnen, da diese bei allen Modellen, die in dieser Arbeit untersucht werden, einen entscheidenden Bestandteil der Konstruktion darstellen. Wir betrachten die folgenden Modelle: 1. Das sogenannte ,,Golden Chain''-Modell, bei dem es sich um eine eindimensionale Spinkette handelt, deren Grundzustand Informationen (wie zum Beispiel den Wert der zentralen Ladung) über die hypothetische CFT enthält. 2. Quantenspinketten (wie die Golden Chain) mit Defekten. Die Konstruktion der Vertices, die die Kette mit Defekten bilden, liefert Einblicke in eine mögliche Konstruktion einer unitären modularen Tensorkategorie (UMTC) über die sogenannte Annulare Kategorie. 3. Das Levin-Wen Modell, welches ein zweidimensionales Gittermodell mit exakt lösbarem Hamiltonian ist, das eine topologische Quantenfeldtheorie liefert. Am interessantesten für uns ist, dass die Anregungen des Systems eine UMTC ergeben. Wir stellen fest, dass die Untersuchung der UFCs selbst keine Hinweise auf eine Haagerup CFT liefert, und schließen daraus, dass es notwendig ist, diese Untersuchung auf die entsprechende UMTC auszudehnen, die zum Beispiel über die Anregungen des Levin-Wen Modells konstruiert werden kann.