Diese Arbeit behandelt kritische Bedrohungen in realen kryptografischen Anwendungen, diem¨oglicherweise nicht sofort offensichtlich sind, aber jederzeit auftreten k¨onnen. Der Autor identifiziert und geht auf drei solche Bedrohungen ein, die die Sicherheit moderner cyber-physischer Systemnetzwerke in Frage stellen. Zunächst wird die Bedrohung durch Quantencomputer untersucht und die Notwendigkeit für kryptografische Annahmen hervorgehoben, die quantensicher sind, d.h. sie bleiben sowohl gegenüber klassischen als auch gegenüber Quantencomputern sicher. Die Arbeit des Autors geht auf diese Herausforderungen durch eine Reihe von Fortschritten ein, die womöglich quantensichere Annahmen einbeziehen. Zweitens wird in der Arbeit die Bedrohung durch interne Angreifer behandelt, die oft in der industriellen Sicherheit zweitrangig behandelt wurde. Der Autor argumentiert jedoch, dass das Vernachl¨assigen von Schutzmaßnahmen gegen interne Angreifer die Gesamtsicherheit untergräbt, da interne Komponenten kompromittiert werden k¨onnen. Dies wird durch die Entwicklung sicherer Protokolle f¨ur Anwendungen wie Kontaktverfolgung verdeutlicht, bei denen das Risiko einer landesweiten Überwachung durch interne Angreifer durch ein ”honest-but-curious” Modell gemindert wird. Dar¨uber hinaus präsentiert die Arbeit ein Protokoll f¨ur ausgelagerte Berechnungen, das es erm¨oglicht, sensible Daten sicher zu verarbeiten, auch wenn der Server mit Clients kolludieren kann. Dies geschieht durch eine formale Neubetrachtung eines Paradigmas f¨ur ausgelagerte Berechnungen, das den Schutz personenbezogener Daten vor internen Bedrohungen gewährleistet. Schließlich wird die Bedrohung durch den Zufalls-Orakel-Ansatz (Random Oracle) untersucht, der die Zuverl¨assigkeit des Einsatzes des Random Oracles in kryptografischen Konstruktionen diskutiert. Obwohl die Random Oracle Heuristik in der realen Kryptografie von unsch¨atzbarem Wert ist, ist auch Funktionen ersetzt wird. Als Reaktion darauf präsentiert die Arbeit ein sicheres Kommunikationsprotokoll, das den Bedarf an Zufalls-Orakeln vermeidet und einen formal fundierteren Ansatz für sichere Nachrichten¨ubertragungen bietet. Obwohl dieses Protokoll weniger effizient ist als seine Pendants, die auf dem Zufalls-Orakel basieren, erreicht es wesentliche Verbesserungen gegen¨uber früheren nicht-Zufalls-Orakel-Konstruktionen. Insgesamt trägt diese Arbeit zur Entwicklung kryptografischer Lösungen bei, die unbehandelte Bedrohungen in realen Anwendungen angehen und darauf abzielen, sowohl die Sicherheit als auch die praktische Anwendbarkeit kryptografischer Systeme angesichts der sich entwickelnden Herausforderungen zu verbessern.
Diese Arbeit behandelt kritische Bedrohungen in realen kryptografischen Anwendungen, diem¨oglicherweise nicht sofort offensichtlich sind, aber jederzeit auftreten k¨onnen. Der Autor identifiziert und geht auf drei solche Bedrohungen ein, die die Sicherheit moderner cyber-physischer Systemnetzwerke in Frage stellen. Zunächst wird die Bedrohung durch Quantencomputer untersucht und die Notwendigkeit für kryptografische Annahmen hervorgehoben, die quantensicher sind, d.h. sie bleiben sowohl gegenüber klassischen als auch gegenüber Quantencomputern sicher. Die Arbeit des Autors geht auf diese Herausforderungen durch eine Reihe von Fortschritten ein, die womöglich quantensichere Annahmen einbeziehen. Zweitens wird in der Arbeit die Bedrohung durch interne Angreifer behandelt, die oft in der industriellen Sicherheit zweitrangig behandelt wurde. Der Autor argumentiert jedoch, dass das Vernachl¨assigen von Schutzmaßnahmen gegen interne Angreifer die Gesamtsicherheit untergräbt, da interne Komponenten kompromittiert werden k¨onnen. Dies wird durch die Entwicklung sicherer Protokolle f¨ur Anwendungen wie Kontaktverfolgung verdeutlicht, bei denen das Risiko einer landesweiten Überwachung durch interne Angreifer durch ein ”honest-but-curious” Modell gemindert wird. Dar¨uber hinaus präsentiert die Arbeit ein Protokoll f¨ur ausgelagerte Berechnungen, das es erm¨oglicht, sensible Daten sicher zu verarbeiten, auch wenn der Server mit Clients kolludieren kann. Dies geschieht durch eine formale Neubetrachtung eines Paradigmas f¨ur ausgelagerte Berechnungen, das den Schutz personenbezogener Daten vor internen Bedrohungen gewährleistet. Schließlich wird die Bedrohung durch den Zufalls-Orakel-Ansatz (Random Oracle) untersucht, der die Zuverl¨assigkeit des Einsatzes des Random Oracles in kryptografischen Konstruktionen diskutiert. Obwohl die Random Oracle Heuristik in der realen Kryptografie von unsch¨atzbarem Wert ist, ist auch Funktionen ersetzt wird. Als Reaktion darauf präsentiert die Arbeit ein sicheres Kommunikationsprotokoll, das den Bedarf an Zufalls-Orakeln vermeidet und einen formal fundierteren Ansatz für sichere Nachrichten¨ubertragungen bietet. Obwohl dieses Protokoll weniger effizient ist als seine Pendants, die auf dem Zufalls-Orakel basieren, erreicht es wesentliche Verbesserungen gegen¨uber früheren nicht-Zufalls-Orakel-Konstruktionen. Insgesamt trägt diese Arbeit zur Entwicklung kryptografischer Lösungen bei, die unbehandelte Bedrohungen in realen Anwendungen angehen und darauf abzielen, sowohl die Sicherheit als auch die praktische Anwendbarkeit kryptografischer Systeme angesichts der sich entwickelnden Herausforderungen zu verbessern.
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.
In dieser Arbeit werden Algorithmen zur Lösung zahlentheoretischer Probleme für klassische Computer und Quantencomputer entwickelt und analysiert sowie ihre Auswirkungen auf Public-Key-Kryptosysteme untersucht. Im Jahr 1994 veröffentliche Shor einen Quantenalgorithmus [Shor, 1994], der das Periodengitter einer gegebenen Funktion in Quanten-Polynomzeit bestimmt. Mit diesem Algorithmus läßt sich das Faktorisierungs- und das Diskreter-Logarithmus-Problems in endlichen abelschen Gruppen in Quanten-Polynomzeit lösen. Dadurch werden die meisten heutzutage verwendeten Public-Key-Kryptoverfahren unsicher, sollten hinreichend große Quantencomputer eines Tages gebaut werden können. Der erste Quantencomputer wurde 1998 gebaut [Chuang/Vandersypen/Zhou/Leung/Lloyd, 1998]. Er bestand aus zwei Qubits. Der größte Quantencomputer, der bis heute gebaut wurde, besteht aus nur sieben Qubits [Vandersypen/Steffen/Breyta/Yannoni/Sherwood/Chuang, 2001]. Es hat sich herausgestellt, daß das Bauen von großen Quantencomputern ein extrem schwieriges Problem ist. Aus diesem Grund kann davon ausgegangen werden, daß die Größe der Quantencomputer, d.h. die Anzahl der Qubits, aus denen ein Quantencomputer besteht, nur langsam wachsen wird. Deshalb ist es von Interesse, Shors Quantenalgorithmus an verschiedene abelsche Gruppen sowie gruppenähnliche Strukturen zu adaptieren und ihre genaue Komplexität zu untersuchen, um daraus die Bedrohungen für die betroffenen Kryptosysteme genau zu bestimmen. In dieser Arbeit werden Quantenalgorithmen zur Lösung des Ordnungsproblems und des DL-Problems in der Klassengruppe der Ideale eines imaginär-quadratischen Zahlkörpers angegeben und ihre Komplexität, d.h. die Anzahl der Qubits und der elementaren Quantenoperationen, bestimmt. Darüberhinaus werden Algorithmen zur Bestimmung des Regulators und zur Lösung des Hauptidealproblems und des erweiterten Diskreter-Logarithmus-Problems in reell-quadratischen Zahlkörpern präsentiert. Shors Algorithmus wird dabei auf Funktionen angewendet, die nicht injektiv innerhalb einer Periode sind. Auch in diesem Fall wird die Komplexität der Algorithmen genau bestimmt. Im Falle von Zahlkörpern eines beliebigen Grades wird eine weitere Modifikation von Shors Algorithmus entwickelt: Es wird das Periodengitter einer Funktion bestimmt, deren Periodengitter irrational ist. Dieser Algorithmus wird benutzt, um die Einheitengruppe eines beliebigen endlich-dimensionalen Zahlkörpers zu berechnen. Als nächstes werden die Auswirkungen von Quantenalgorithmen auf die Sicherheit von Public-Key-Kryptosystemen untersucht. Es wird ein neuer Sicherheitsbegriff eingeführt. Die Sicherheit zweier Kryptosysteme wird als gleich definiert, wenn die Anzahl der Qubits zum Brechen dieser Kryptosysteme gleich ist. Basierend auf der neuen Sicherheitsdefinition wird die Geschwindigkeit und die Schlüsselgröße von einigen Kryptosystemen verglichen. Im letzten Kapitel wird ein deterministischer klassischer Algorithmus zur Berechnung der Struktur einer endlichen abelschen Gruppe aus einem Erzeugendensystem präsentiert, dessen Laufzeit nur linear von der Anzahl der gegebenen Erzeuger abhängt und dessen Speicherplatzkomplexität unabhängig von der Anzahl der gegebenen Erzeuger ist. Das stellt eine exponentielle Verbesserung zu früheren Algorithmen dar, bei denen sowohl die Laufzeit als auch die Speicherplatzkomplexität exponentiell von der Anzahl der Erzeuger im gegebenen Erzeugendensystem abhängt [Buchmann/Jacobson/Teske, 1997].
Diese Dissertation besteht aus einer Sammlung von Projekten, welche unter der Betreuung von Prof. Caslav Brukner durchgeführt wurden. Die Arbeit gliedert sich in zwei Hauptteile. Der erste Teil widmet sich dem operativen Zugang zu der Quan- tenmechanik. Die Hauptaufgabe besteht hierbei darin, die exklusiven Eigenschaften der Quantenmechanik in einer größeren Klasse probabilistischer Theorien zu identifizieren. Der zweite Teil beschäftigt sich mit der typischen Charakteristik der Quantenphysik, wie der Quantenstatistik, den Quantenkorellationen und Quantensimulationen. Man kann sicherlich sagen, dass wir derzeit noch keine der Intuition zugänglichen, und allgemein akzeptierte physikalische Prinzipien haben, welche die Grundlage der Quantemechanik darstellen. Der Mangel solcher Prinzipien ist die Hauptursache für die derzeitige Koexistenz von vielen Interpretationen der Quantenmechanik, die von Konzepten Gebrauch machen, welche sich gegenseitig ausschließen. Eine Hauptaufgabe des ersten Kapitel besteht in der Spezifizierung von Theorien mit grundsätzlich beschränkten Informationsgehalt, welche aufgrund dieser Tatsache eine probabilistische Beschreibung besitzen. Unter dem “beschränkten Informationsgehalt eines Systems”, verstehen wir eine grundsätzliche Beschränkung der Information welche durch eine Messung über die Preparation eines Zustandes gewonnen werden kann. Ein Ergebnis dieses Kapitels ist die Charakterisierung der gesamten Hierarchie der Theorien, welchen diese Eigenschaft gemein sind. Auf den unteren Stufen dieser Hierarchie sind die klassische, wie auch die quantenmechanische Wahrscheinlichkeitstheorie enthalten. Um die Quantentheorie und klassische Theorie von der ganzen Klasse der Wahrscheinlichkeitstheorien zu unterscheiden, wurden zusätzliche Annahmen getroffen. Diese Annahmen sind Lokalität und Umkehrbarkeit. Unter dem Prinzip der Lokalität verstehen wir, dass der Gesamtzustand eines Systems durch die Statistik der individuellen Untersysteme rekonstruiert werden kann. Das Prinzip der Umkehrbarkeit drückt aus, dass zwei reine Zustände immer durch eine umkehrbare Transformation auseinander hervorgehen. Darüber hinaus, wurde ein weiteres fundamentales Prinzip der Quantenmechanik, das Komplementaritätsprinzip, mittels “mutually unbiased bases” untersucht. Es wurde eine Verbindung zu dem bekannten mathematischen Problem der orthogonalen lateinischen Quadraten hergestellt. Eine plausible klassische Beschreibung der Quantenstatistik benötigt nicht eingängige Konzepte wie die quantenmechanische “Nicht-lokalität” und “Kontextualität”. Der zweite Teil dieser Dissertation widmet sich einer weiteren Frage, der Frage nach dem “Kostenaufwand” im Sinne der beschreibenden Ressourcen welche eine plausible klassische Beschreibung der Quantenstatistik zulassen. Es wurde gezeigt, dass die klassische Simulation der Quantenstatistik nur eine polynomiale Anzahl an Ressourcen, so genannte verborgene Variablen, für die Verschiedenen Messeinstellungen benötigt. Darüber hinaus bestätigt dieses Simulationsmodell auch, dass in einem vernünftigen Limes, die optimale Beschreibung der Quantenstatistik die Quantenmechanik selbst ist. Quantenkorrelationen sind für die quantenmechanische Nicht-lokalität verantwortlich, wie auch für den “computational speedup” in der Quanten Informationsverarbeitung. Es gibt Beispiele von Quanteninformationsprotokollen, die mit Sicherheit kein Verschränkung nutzen aber dennoch von quantenmechanischen Korrelationen Gebrauch machen. Es ist daher nicht möglich die Korrelationen in ihrer allgemeinen Form mit der Verschränkung gleich zu setzen. Das zweite Kapitel behandelt die Frage der nicht-klassischen Eigenschaften der Quantenkorrelationen welche durch den “quantum discord” beschrieben werden. Das Hauptergebnis ist eine experimentell einfach zugängliche, hinreichend wie auch notwendige, Bedingung für nicht-verschwindenden quantum discord. Darüber hinaus stellen wir eine Analyse der Ressourcen in “mixed-state quantum computation” vor, welche zeigt, dass die Rolle des “quantum discord” in der Quanteninformationsverarbeitung weiterhin unklar ist. Schließlich widmet sich das letzte Kapitel dieses Teils der Untersuchung von Quanensimulationen, sowohl theoretisch als auch experimentell. Quantensimulatoren können verwendet werden um die Zeitenwicklung eines bestimmten quantenmechanischen system darzustellen, eine Aufgabe, die für klassische Computer sehr schwierig ist. Es wird ein kleiner photonischer Quantensimulator vorgestellt, der in der Lage ist ein frustriertes Spin Tetramer zu simulieren. Die Simulation macht von verschränkten Photonpaaren, verstellbaren Quantengattern und durch Messung induzierten Nichtlinearitäten Gebrauch.
Dans cette thèse, nous étudions la cryptographie classique et quantique dans des modèles quantiques idéalisés. Des travaux antérieurs ont montré que les ressources quantiques peuvent être utilisées pour réaliser des tâches cryptographiques qui sont prouvées ou supposées impossibles dans le paradigme classique. Dans cette thèse, nous prouvons tout d'abord des bornes inférieures sur l'efficacité de n'importe quel algorithme quantique cherchant une couverture par sous-ensembles d'une fonction aléatoire, un problème conjecturé difficile et utilisé pour évaluer la sécurité du schéma de signature post-quantique SPHINCS+. Ensuite, nous étendons les résultats d'impossibilité existants concernant la construction de schémas de chiffrement à clé publique dans le modèle quantique de l'oracle aléatoire, en montrant qu'un type plus général de chiffrement à clé publique n'existe pas dans ce modèle. Nous étudions ensuite des hypothèses quantiques pour la cryptographie qui semblent plus faibles que les fonctions à sens unique, à savoir les générateurs d'états quantique pseudoaléatoires, ainsi que leur relation avec les schémas quantiques de chiffrement à clé publique et de signature, en clarifiant et en améliorant les constructions et les preuves d'impossibilité déjà existantes. Enfin, nous établissons l'importance de la taille des états quantique pseudoaléatoires en prouvant qu'un état quantique pseudoaléatoire ne peut pas être compressé, et nous progressons vers la démonstration qu'il ne peut pas non plus être amplifié.
Diese Dissertation behandelt die Kodierung und Verschickung von Information durch einen Quantenkanal. Ein Quantenkanal besteht aus einem quantenmechanischen System, welches vom Sender manipuliert und vom Empfänger ausgelesen werden kann. Dabei repräsentiert der individuelle Zustand des Kanals die Nachricht. Die zwei Themen der Dissertation umfassen 1) die Möglichkeit, eine Nachricht in einem Quantenkanal verlustfrei zu komprimieren und 2) die Möglichkeit eine Nachricht von einer Partei zu einer einer anderen direkt und auf sichere Weise zu übermitteln, d.h. ohne dass es einer dritte Partei möglich ist, die Nachricht abzuhören und dabei unerkannt zu bleiben. Die wesentlichen Ergebnisse der Dissertation sind die folgenden. Ein allgemeiner Formalismus für Quantencodes mit variabler Länge wird ausgearbeitet. Diese Codes sind notwendig um verlustfreie Kompression zu ermöglichen. Wegen der Quantennatur des Kanals sind die codierten Nachrichten allgemein in einer Superposition von verschiedenen Längen. Es zeigt sich, daß es unmöglich ist eine Quantennachricht verlustfrei zu komprimieren, wenn diese dem Sender nicht apriori bekannt ist. Im anderen Falle wird die Möglichkeit verlustfreier Quantenkompression gezeigt und eine untere Schranke für die Kompressionsrate abgeleitet. Des weiteren wird ein expliziter Kompressionsalgorithmus konstruiert, der für beliebig vorgegebene Ensembles aus Quantennachrichten funktioniert. Ein quantenkryptografisches Prokoll - das “Ping-Pong Protokoll” - wird vorgestellt, welches die sichere direkte übertragung von klassischen Nachrichten durch einen Quantenkanal ermöglicht. Die Sicherheit des Protokolls gegen beliebige Abhörangriffe wird bewiesen für den Fall eines idealen Quantenkanals. Im Gegensatz zu anderen quantenkryptografischen Verfahren ist das Ping-Pong Protokoll deterministisch und kann somit sowohl für die Übermittlung eines zufälligen Schlüssels als auch einer komponierten Nachricht verwendet werden. Das Protokoll is perfekt sicher für die Übertragung eines Schlüssels und quasi-sicher für die direkte Übermittlung einer Nachricht. Letzteres bedeutet, dass die Wahrscheinlichkeit eines erfolgreichen Abhörangriffs exponenziell mit der Länge der Nachricht abnimmt.
Cryptographie fondée sur les réseaux euclidiens dans une contexte quantique : preuves de sécurité et attaques L'émergence des machines quantiques crée des défis et des opportunités pour la cryptographie. En particulier, les preuves de sécurité doivent être révisées en raison des capacités quantiques des adversaires. Cette thèse propose deux contributions à cet égard : un résultat positif et un résultat négatif. La transformation de Fiat-Shamir avec des rejets est l’un des principaux paradigmes pour concevoir des schémas de signature post-quantiques. Une partie de cette thèse consiste en une analyse détaillée de cette transformation dans le modèle de l’oracle aléatoire quantique. Tous les travaux précédents proposant une analyse de sécurité de cette transformation ont négligé des détails subtils, compromettant la correction des preuves. Par conséquent, notre preuve de sécurité est la première de son genre à être correcte. De plus, nous analysons le temps d'exécution et la correction des signatures obtenues à partir de cette transformation. Le problème learning with errors (LWE) a été largement utilisé pour construire des schémas cryptographiques sécurisés contre les adversaires quantiques. Une hypothèse liée à LWE stipule que la génération d'une instance LWE sans connaître son secret est difficile pour tous les algorithmes polynomiaux. On peut utiliser cette hypothèse pour prouver la sécurité de certains arguments de connaissance succints. Bien que cela semble être une tâche difficile pour les algorithmes classiques, nous présentons un algorithme quantique polynomial qui génère des instances LWE sans connaître le secret. Notre algorithme invalide ainsi les analyses de sécurité de ces arguments de connaissance succints dans le contexte quantique.