Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Isogeny based cryptography

Jonas Meers

Published Sep 18, 2026• 0 citations
Publisher

Abstract

Kryptografie sichert unsere digitale Kommunikation. Zentral ist die Public-Key-Kryptografie, die zwei Parteien einen Geheimnisaustausch ohne vorherige Interaktion ermöglicht. Mit Quantencomputern werden die meisten dieser Protokolle jedoch obsolet. Die isogeniebasierte Kryptografie erreicht Post-Quanten-Sicherheit über die Schwierigkeit, eine Isogenie zwischen zwei supersingulären elliptischen Kurven zu finden. Selbst für Quantencomputer ist dies ein schweres Problem. Diese Komplexität erschwert jedoch auch das Protokolldesign und wirft in der jungen Kryptanalyse Fragen zu Leakage-Angriffen auf. Diese Arbeit erweitert den Stand der Technik in zwei Bereichen: Wir geben neuartige Konstruktionen für Updatable Encryption, Authenticated Key Encapsulation und Non-Interactive Timed Commitments an, die Sicherheit, Effizienz oder Kompaktheit verbessern. Zudem entwickeln wir Leakage-Angriffe auf Schlüsselaustausch- und Signaturschemata und zeigen teils inhärente Resilienz.

DOI
10.13154/294-14972

Related papers

Cryptographic Protocols from Physical Assumptions

Alexander Koch

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.

•Jan 1, 2019•19 citations

Über Kryptographische Protokolle aus der Echten Welt für Ende-zu-Ende Verschlüsselte Backups und KeyConfirmation

Tobias Handirk

Die weite Verbreitung des Internets erzeugt große Mengen an digitaler Kommunikation und macht Kryptographie zu einem unverzichtbaren Teil des täglichen Lebens, da unzählige Anwendungen nur durch den Schutz von sensitiven Daten ermöglicht werden. Ein fundamentaler kryptographischer Baustein ist authentifizierter Schlüsselaustausch, welcher mit Hilfe des Key Confirmation Paradigmas entwickelt werden kann. Im ersten Teil dieser Arbeit zeigen wir einen inhärenten Nachteil des Paradigmas auf, durch den die Parametergrößen bei der Instanziierung linear mit der Anzahl der Nutzer wachsen müssen. Im zweiten Teil dieser Arbeit widmen wir uns Instant Messaging Anwendungen, welche eine der populärsten Anwendungen im Internet sind. Zunächst analysieren wir die formalen Sicherheitsgarantien des Backup Systems von WhatsApp, und entwickeln anschließend drei neue Backup Protokolle, welche unterschiedliche Kompromisse zwischen Effizienz und benötigtem Vertrauen in die tatsächliche Sicherheit von vermeintlich sicherer Hardware bieten.

•Jan 1, 2025•0 citations

Qutrit-Based Device-Independent Quantum Key Distribution Secure Against Collective Attacks

Katrin Bieglmayer

Klassische Kryptographie beruht auf der rechnerischen Schwierigkeit bestimmter Probleme, doch Fortschritte im Quantencomputing gefährden diese Annahmen. Der Quantenschlüsselaustausch (Quantum Key Distribution - QKD) nutzt die Prinzipien der Quantenmechanik und ermöglicht es zwei räumlich getrennten Parteien, einen gemeinsamen geheimen Schlüssel mit informationstheoretischer Sicherheit zu erzeugen, selbst gegenüber Angreifer*innen mit unbegrenzter Rechenleistung. In QKD sind Annahmen über Messgeräte und Quantenzustandsquellen zentral für die Sicherheitsanalyse und bestimmen verschiedene Familien von Protokollen. Geräteunabhängige QKD (Device Independent QKD - DI-QKD) bietet das höchste Sicherheitsniveau: Weder Geräte noch Quellen müssen vertrauenswürdig sein und könnten sogar von einer Angreifer*in kontrolliert werden. In diesem Kontext beruht die Sicherheit auf der Beobachtung starker Quantenkorrelationen, die sich durch die Verletzung einer Bell-Ungleichung manifestieren. Die Berechnung der Schlüsselrate, welche die Effizienz der Schlüsselgenerierung beschreibt, beinhaltet eine Optimierung über alle Messungen und Quantenzustände beliebiger Hilbertraumdimension, die mit der beobachteten Verletzung einer Bell Ungleichung konsistent sind. Für Bell Ungleichungen mit zwei Messeinstellungen und zwei Messergebnissen pro Partei, wie die CHSH-Ungleichung, lässt sich diese Optimierung auf Qubits beschränken, was analytische Lösungen für die Schlüsselrate ermöglicht. In dieser Arbeit untersuchen wir diesen Ansatz im Detail mit dem Ziel, ihn auf Bell-Ungleichungen mit drei Messergebnissen zu übertragen, wobei angenommen wird, dass Alice und Bob einen Zwei-Qutrit-Zustand teilen. Während diese Einschränkung den DI-Anspruch abschwächt, ist dieses Setting dennoch von Interesse, da es trotzdem Einblicke in höherdimensionale DI-QKD über numerische Resultate hinaus liefern und Intuition darüber geben könnte, ob höhere Dimensionen eine größere Rauschtoleranz ermöglichen.

•Sep 1, 2026•0 citations

Novel schemes for QKD

Florian Hipp

Quanten Kryptographie oder genauer gesagt Quanten-Schluessel Verteilung (Quantum Key Distribution - QKD) ist die erste Anwendung der Quantentheorie die kurz davor steht den Sprung vom Experiment zur industriellen Verwertung zu schaffen. Ermoeglicht wurde diese Erfolgsgeschichte durch zahllose theoretische und experimentelle Arbeiten innerhalb der letzten 30 Jahre. Thema dieser Arbeit sind experimentelle Fortschritte der juengsten Zeit, QKD Protokolle und Attacken auf QKD sowie eine moegliche Integration dieser quantenbasierten Technologie in die 'klassische Welt'. Die groesste Herausforderung bei dieser Zusammenfuehrung ist in drei Bereichen zu finden, naemlich die unzureichende technische Ausgereiftheit der verwendeten Hardware, die das Gebiet des 'quanten Hackens' hervorgebracht hat, QKD ueber lange Distanzen (100km und mehr) und die Integration von QKD in bereits verlegte Backbone und Access Netzwerke. Zwar werden alle drei Gebiete in dieser Arbeit behandelt, neue Erkenntnisse werden zu den beiden letzteren eroertert, da das Ausnutzen von technischen Fehlern in Hardware im Prinzip nicht mehr als ein Wettlauf zwischen Hackern und Hersteller ist, der im Prinzip schon durch hardwareunabhaengige QKD Modelle geloest wurde. Als moeglicher Ansatz zum Ueberbruecken grosser Distanzen mit QKD Technologie bietet sich die satellitenbasierte Kommunikation zwischen entfernten Punkten auf der Erde an. Zu diesem Zweck stellt diese Arbeit zwei Generationen von Lithiumniobat Wellenleitern vor, die auf spontaner parametrischer Downconversion (SPDC) und Quasi Phasen Anpassung (QPS) zur Erzeugung verschraenkter Photonenpaare basiert. Das Ziel ist die Entwicklung einer autonomen, komplett integrierten Quelle polarisationsverschraenkter Photonen im C-Band. Verglichen mit anderen Quellen ist in diesem Fall der Herstellungsprozess des Wellenleiters sowie dessen Integration in fasergebundene Optik bei einem eingeschraenkten Formfaktor (< 0,5m 2) eine zusaetzliche Herausforderung. In einem nicht fasergebundenen Aufbau wurde fuer die erste Generation von Wellenleiter eine 'Visibility' von ueber 91% und eine 'spectrale Brightness' von 10 6 Paare /(s nm W) gemessen. Bei der zweiten Generation von Wellenleitern, komplett fasergebunden, wurde hingegen nur 75% 'Visibility' and 4 ∙10 3 Paare /(s nm W) 'spectrale Brightness' erreicht. Dieser wesentlich schlechtere Wert kommt von hohen Verlusten beim Uebergang von Kristall auf Faser und ruehrt vom Anbringen der Faser auf den Wellenleiter her. Das zweite grosse Thema dieser Arbeit ist die moegliche Integration von QKD in bereits bestehende Netzwerkinfrastruktur und der damit einhergehende Einfluss starker klassischer Datensignale auf die sehr schwachen Quantensignale. Trotz erarbeiteter Konzepte die es erlauben die klassischen Kanaele zu ueberbruecken und den Quantenkanal von diesen zu trennen, muessen Beeintraechtigungen durch nichtlineare Prozesse, ueberwiegend Ramanstreuung, beruecksichtigt werden, gerade wenn alle Kanaele ueber dieselbe Faser laufen, wie es in der sogenannten Single-Feeder Methode ueblich ist. Sensible Raman Messungen bis zur Energie von Einzelphotonen, durchgefuehrt an einem 20 Kanal DWDM Netzwerk, zeigen, dass sogar ueber 200nm weg von den klassischen Daten Kanaelen ca. 10 6 photonen / (s nm) erzeugt werden. Unsere Simulationen und experimentellen Daten ergaben weiterhin, dass ein Quantenkanal durchaus in passive optische Netzwerke integrierbar ist, wenn ausreichend spektraler Abstand sowie passende Wellenlaengen und zeitliche Filter verwendet werden, die es erlauben die einzelnen Photonen vom Hintergrund zu trennen. Diese Resultate wurden mit einer Quelle polarisationsverschraenkter Photonen gemessen, bestehend aus einem ppKTP Kristall in Sagnac Konfiguration, der Photonenpaare bei 589nm und im O-Band bei 1310nm erzeugt. Damit ist es gelungen eine full-duplex Punkt zu Punkt Verbindung ueber 13.2km aufzubauen bei der sowohl klassische Signale als auch Quantensignale ueber dieselbe Faser geschickt werden. Die Erkenntnisse die in dieser Arbeit praesentiert werden zeigen die Moeglichkeiten aber auch die Grenzen von QKD sowohl fuer die Uebertragung ueber weite Strecken durch satellitenbasierte Systeme als auch fuer die Integration in optische Netzwerke. Diese Arbeit wird mithelfen Standards fuer moegliche zukuenftige Entwicklungen im Bereich QKD zu setzen. Abgesehen von dieser Arbeit wurden die Ergebnisse im Journal Optics Express (2015), den SPIE Proceedings (2016) und der CLEO Europe Konferenz (2015) sowie anderen kleineren Konferenzen vorgestellt.

•Oct 1, 2016•0 citations

Operational tools for moment characterization, entanglement verification and quantum key distribution

Tobias Moroder

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.

•Jan 1, 2009•0 citations

Zur Lösung von zahlentheoretischen Problemen mit klassischen und Quantencomputern

Schmidt, Arthur

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].

•Jan 1, 2008•1 citation
Kryptografie sichert unsere digitale Kommunikation. Zentral ist die Public-Key-Kryptografie, die zwei Parteien einen Geheimnisaustausch ohne vorherige Interaktion ermöglicht. Mit Quantencomputern werden die meisten dieser Protokolle jedoch obsolet. Die isogeniebasierte Kryptografie erreicht Post-Quanten-Sicherheit über die Schwierigkeit, eine Isogenie zwischen zwei supersingulären elliptischen Kurven zu finden. Selbst für Quantencomputer ist dies ein schweres Problem. Diese Komplexität erschwert jedoch auch das Protokolldesign und wirft in der jungen Kryptanalyse Fragen zu Leakage-Angriffen auf. Diese Arbeit erweitert den Stand der Technik in zwei Bereichen: Wir geben neuartige Konstruktionen für Updatable Encryption, Authenticated Key Encapsulation und Non-Interactive Timed Commitments an, die Sicherheit, Effizienz oder Kompaktheit verbessern. Zudem entwickeln wir Leakage-Angriffe auf Schlüsselaustausch- und Signaturschemata und zeigen teils inhärente Resilienz.
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.
Die weite Verbreitung des Internets erzeugt große Mengen an digitaler Kommunikation und macht Kryptographie zu einem unverzichtbaren Teil des täglichen Lebens, da unzählige Anwendungen nur durch den Schutz von sensitiven Daten ermöglicht werden. Ein fundamentaler kryptographischer Baustein ist authentifizierter Schlüsselaustausch, welcher mit Hilfe des Key Confirmation Paradigmas entwickelt werden kann. Im ersten Teil dieser Arbeit zeigen wir einen inhärenten Nachteil des Paradigmas auf, durch den die Parametergrößen bei der Instanziierung linear mit der Anzahl der Nutzer wachsen müssen. Im zweiten Teil dieser Arbeit widmen wir uns Instant Messaging Anwendungen, welche eine der populärsten Anwendungen im Internet sind. Zunächst analysieren wir die formalen Sicherheitsgarantien des Backup Systems von WhatsApp, und entwickeln anschließend drei neue Backup Protokolle, welche unterschiedliche Kompromisse zwischen Effizienz und benötigtem Vertrauen in die tatsächliche Sicherheit von vermeintlich sicherer Hardware bieten.
Klassische Kryptographie beruht auf der rechnerischen Schwierigkeit bestimmter Probleme, doch Fortschritte im Quantencomputing gefährden diese Annahmen. Der Quantenschlüsselaustausch (Quantum Key Distribution - QKD) nutzt die Prinzipien der Quantenmechanik und ermöglicht es zwei räumlich getrennten Parteien, einen gemeinsamen geheimen Schlüssel mit informationstheoretischer Sicherheit zu erzeugen, selbst gegenüber Angreifer*innen mit unbegrenzter Rechenleistung. In QKD sind Annahmen über Messgeräte und Quantenzustandsquellen zentral für die Sicherheitsanalyse und bestimmen verschiedene Familien von Protokollen. Geräteunabhängige QKD (Device Independent QKD - DI-QKD) bietet das höchste Sicherheitsniveau: Weder Geräte noch Quellen müssen vertrauenswürdig sein und könnten sogar von einer Angreifer*in kontrolliert werden. In diesem Kontext beruht die Sicherheit auf der Beobachtung starker Quantenkorrelationen, die sich durch die Verletzung einer Bell-Ungleichung manifestieren. Die Berechnung der Schlüsselrate, welche die Effizienz der Schlüsselgenerierung beschreibt, beinhaltet eine Optimierung über alle Messungen und Quantenzustände beliebiger Hilbertraumdimension, die mit der beobachteten Verletzung einer Bell Ungleichung konsistent sind. Für Bell Ungleichungen mit zwei Messeinstellungen und zwei Messergebnissen pro Partei, wie die CHSH-Ungleichung, lässt sich diese Optimierung auf Qubits beschränken, was analytische Lösungen für die Schlüsselrate ermöglicht. In dieser Arbeit untersuchen wir diesen Ansatz im Detail mit dem Ziel, ihn auf Bell-Ungleichungen mit drei Messergebnissen zu übertragen, wobei angenommen wird, dass Alice und Bob einen Zwei-Qutrit-Zustand teilen. Während diese Einschränkung den DI-Anspruch abschwächt, ist dieses Setting dennoch von Interesse, da es trotzdem Einblicke in höherdimensionale DI-QKD über numerische Resultate hinaus liefern und Intuition darüber geben könnte, ob höhere Dimensionen eine größere Rauschtoleranz ermöglichen.
Quanten Kryptographie oder genauer gesagt Quanten-Schluessel Verteilung (Quantum Key Distribution - QKD) ist die erste Anwendung der Quantentheorie die kurz davor steht den Sprung vom Experiment zur industriellen Verwertung zu schaffen. Ermoeglicht wurde diese Erfolgsgeschichte durch zahllose theoretische und experimentelle Arbeiten innerhalb der letzten 30 Jahre. Thema dieser Arbeit sind experimentelle Fortschritte der juengsten Zeit, QKD Protokolle und Attacken auf QKD sowie eine moegliche Integration dieser quantenbasierten Technologie in die 'klassische Welt'. Die groesste Herausforderung bei dieser Zusammenfuehrung ist in drei Bereichen zu finden, naemlich die unzureichende technische Ausgereiftheit der verwendeten Hardware, die das Gebiet des 'quanten Hackens' hervorgebracht hat, QKD ueber lange Distanzen (100km und mehr) und die Integration von QKD in bereits verlegte Backbone und Access Netzwerke. Zwar werden alle drei Gebiete in dieser Arbeit behandelt, neue Erkenntnisse werden zu den beiden letzteren eroertert, da das Ausnutzen von technischen Fehlern in Hardware im Prinzip nicht mehr als ein Wettlauf zwischen Hackern und Hersteller ist, der im Prinzip schon durch hardwareunabhaengige QKD Modelle geloest wurde. Als moeglicher Ansatz zum Ueberbruecken grosser Distanzen mit QKD Technologie bietet sich die satellitenbasierte Kommunikation zwischen entfernten Punkten auf der Erde an. Zu diesem Zweck stellt diese Arbeit zwei Generationen von Lithiumniobat Wellenleitern vor, die auf spontaner parametrischer Downconversion (SPDC) und Quasi Phasen Anpassung (QPS) zur Erzeugung verschraenkter Photonenpaare basiert. Das Ziel ist die Entwicklung einer autonomen, komplett integrierten Quelle polarisationsverschraenkter Photonen im C-Band. Verglichen mit anderen Quellen ist in diesem Fall der Herstellungsprozess des Wellenleiters sowie dessen Integration in fasergebundene Optik bei einem eingeschraenkten Formfaktor (< 0,5m 2) eine zusaetzliche Herausforderung. In einem nicht fasergebundenen Aufbau wurde fuer die erste Generation von Wellenleiter eine 'Visibility' von ueber 91% und eine 'spectrale Brightness' von 10 6 Paare /(s nm W) gemessen. Bei der zweiten Generation von Wellenleitern, komplett fasergebunden, wurde hingegen nur 75% 'Visibility' and 4 ∙10 3 Paare /(s nm W) 'spectrale Brightness' erreicht. Dieser wesentlich schlechtere Wert kommt von hohen Verlusten beim Uebergang von Kristall auf Faser und ruehrt vom Anbringen der Faser auf den Wellenleiter her. Das zweite grosse Thema dieser Arbeit ist die moegliche Integration von QKD in bereits bestehende Netzwerkinfrastruktur und der damit einhergehende Einfluss starker klassischer Datensignale auf die sehr schwachen Quantensignale. Trotz erarbeiteter Konzepte die es erlauben die klassischen Kanaele zu ueberbruecken und den Quantenkanal von diesen zu trennen, muessen Beeintraechtigungen durch nichtlineare Prozesse, ueberwiegend Ramanstreuung, beruecksichtigt werden, gerade wenn alle Kanaele ueber dieselbe Faser laufen, wie es in der sogenannten Single-Feeder Methode ueblich ist. Sensible Raman Messungen bis zur Energie von Einzelphotonen, durchgefuehrt an einem 20 Kanal DWDM Netzwerk, zeigen, dass sogar ueber 200nm weg von den klassischen Daten Kanaelen ca. 10 6 photonen / (s nm) erzeugt werden. Unsere Simulationen und experimentellen Daten ergaben weiterhin, dass ein Quantenkanal durchaus in passive optische Netzwerke integrierbar ist, wenn ausreichend spektraler Abstand sowie passende Wellenlaengen und zeitliche Filter verwendet werden, die es erlauben die einzelnen Photonen vom Hintergrund zu trennen. Diese Resultate wurden mit einer Quelle polarisationsverschraenkter Photonen gemessen, bestehend aus einem ppKTP Kristall in Sagnac Konfiguration, der Photonenpaare bei 589nm und im O-Band bei 1310nm erzeugt. Damit ist es gelungen eine full-duplex Punkt zu Punkt Verbindung ueber 13.2km aufzubauen bei der sowohl klassische Signale als auch Quantensignale ueber dieselbe Faser geschickt werden. Die Erkenntnisse die in dieser Arbeit praesentiert werden zeigen die Moeglichkeiten aber auch die Grenzen von QKD sowohl fuer die Uebertragung ueber weite Strecken durch satellitenbasierte Systeme als auch fuer die Integration in optische Netzwerke. Diese Arbeit wird mithelfen Standards fuer moegliche zukuenftige Entwicklungen im Bereich QKD zu setzen. Abgesehen von dieser Arbeit wurden die Ergebnisse im Journal Optics Express (2015), den SPIE Proceedings (2016) und der CLEO Europe Konferenz (2015) sowie anderen kleineren Konferenzen vorgestellt.
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.
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].