Kryptographie II

Vorlesung im Wintersemester 2004 an der Technischen Universität Berlin.
Auf dieser Seite werden im Lauf der VL relevante Informationen zur Verfügung gestellt.

Dozenten: Prof. Dr. F. Heß, Dipl.-Math. M. Wagner

Zeiten und Adressen

Vorlesung:	Di 10-12 Uhr im MA851 und Do 12-14 im MA545
Übung:	Fr 8-10 Uhr im MA850

Sprechzeiten: F. Heß nach der Vorlesung und nach Vereinbarung, M. Wagner Fr 13-14 und nach Vereinbarung.

F. Heß	MA804	hess@math.tu-berlin.de 314-25062
M. Wagner	MA812	wagner@math.tu-berlin.de 314-23761
Teilnehmer der VL Kryptographie II		krypto2@math.tu-berlin.de

Inhalt

Im folgenden findet sich eine Auswahl an möglichen Themen. Welche davon behandelt werden, wird auch vom Interesse der Teilnehmer abhängig gemacht.

Gitter, LLL-Algorithmus und gitterbasierte Kryptosysteme - Lineare Codes und Kryptosysteme - Identitätsbasierte Kryptographie und supersinguläre elliptische Kurven - Globale Körper, Kurven, Picardgruppen, Index-Calculus - Beweisbare Sicherheit - Protokolle (elektronische Wahlen etc.) - Kryptographische Funktionen der Campuskarte - Einwegfunktionen, Pseudozufallsgeneratoren, interaktive Beweissysteme, Zero-Knowledge Beweise - Quantencomputer, -algorithmen und -kryptographie.

Vorausgesetzt werden die VL Kryptographie SS04 bzw. entsprechende Kryptographie- und Algebrakenntnisse.

Unterlagen und Übungsblätter

Unterlagen zur Vorlesung:
- 19.10. Wiederholung vom SS2004 (Folien)
- 21.10. Moduln und Matrizen über Hauptidealringen (pdf,ps)
- 26.10. Gitter - Definitionen und Diskretheit
- 28.10. Gitter - Andere Skalarprodukte und Auszählen
- 02.11. Gitter - Kürzeste Vektoren, sukzessive Minima
- 04.11. Gitter - Sukzessive Minima, Basisreduktion
- 09.11. Gitter - Basisreduktion: Längen-, Paar-, Gaußreduktion
- 11.11. Gitter - Basisreduktion: LLL
- 16.11. Gitter - Basisreduktion: LLL im einzelnen
- 18.11. Gitter - Basisreduktion: LLL nochmal und Kryptosystem NTRU
- 23.11. Gitter - Basisreduktion: LLL Laufzeit
- 25.11. Gitterbasierte Kryptosysteme (pdf,ps)
- 30.11. Gitterbasierte Kryptosysteme
- 02.12. Gitterangriff auf RSA mit kleinem Exponent (pdf,ps)
- 07.12. Bitsicherheit des DHP (pdf,ps)
- 10.12. Invertierbarkeit von Elementen des NTRU-Polynomringes (pdf )
- 14.12. Algorithmen für das CVP (pdf,ps)
- 16.12. Algorithmen für das CVP. Lineare Codes und Kryptosysteme (pdf,ps)
- 17.12. Identitätsbasierte Kryptographie, Signaturverfahren (ps)
- 04.01. Quantencomputer und Quantenkryptographie: Übersicht, Quantenzustände und Messungen, Qubits, Tensorprodukte.
- 06.01. Wiederholung und Vertiefung von letzem Mal, Evolution durch unitäre Transformationen, einfache Beispiele (Hadamard et al.), Schaltkreise und Komplexität, reversible Berechnungen.
- 11.01. Quantenschaltkreise: Universelle Gatter, Approximation von Gattern, Satz von Solovay-Kitaev, Fehlerfortpflanzung.
- 13.01. Erste Quantenalgorithmen von Deutsch-Jozsa, Bernstein-Vazirani und Simon.
- 18.01. Klassische Lösung des Problems von Simon. Quantenfouriertransformation: Fourieranalyse auf endlichen abelschen Gruppen (pdf,ps) (Korrektur auf S. 8 am 25.01.)
- 20.01. Quantenfouriertransformation: Fourieranalyse auf endlichen abelschen Gruppen, Darstellung durch Qubits im Hinblick auf Tensorprodukte, Produktdarstellung der Fouriertransformation.
- 25.01. Quantenfouriertransformation: Produktdarstellung der Fouriertransformation für zyklische Gruppe der Ordnung 2 hoch n, schnelle Fouriertransformation und Anwendungen
- 27.01. Schnelle Fouriertransformation zweiter Teil. Hidden Subgroup Problem und Quantenalgorithmus zur Lösung des HSP.
- 01.01. Der Quantenalgorithmus zur Faktorisierung ganzer Zahlen (pdf,ps)
- 03.02. Der Quantenalgorithmus zur Faktorisierung ganzer Zahlen.
- 08.02. Reduktion verschiedener Probleme auf Hidden Subgroup Probleme: DLP, Graph Isomorphie, Kürzeste Vektoren in Gittern (SVP).
- 10.02. Der Suchalgorithmus von Grover.
- 15.02. Quantenkryptographie - BB84 Schlüsselaustausch
- 17.02. Über- und Ausblick über Überlagerungsangriffe auf elliptische Kurven (Weil Abstieg Methodologie).
- Skript zu den Gittern (wird sukzessive ergänzt, Version vom 29.11.2004 pdf ps)
- Für Quantencomputer und Quantenkryptographie verwenden wir die Skripte von Torán, Vazirani und Preskill. Zur Fouriertransformation und dem Faktorisierungsalgorithmus von Shor siehe auch die Kurzskripte bei den obigen VL. Informationen, wie Quantencomputer beziehungsweise Qbits physikalisch-technisch realisiert werden können, findet sich auch bei Meglicki.

Übungsblätter zur Vorlesung:
- Blatt 1 (pdf ps)
- Blatt 2 (pdf ps)
- Blatt 3 (pdf ps)
- Blatt 4 (pdf ps)
- Blatt 5 (pdf ps)
- Blatt 6 (pdf ps)
- Blatt 7 (pdf ps)
- Blatt 8 (pdf ps)
- Blatt 9 (pdf ps)
- Musterlösungen pdf ps

KASH-Code: (NTRU)

Gruppenarbeit in Zweier-Gruppen. Scheinkriterium: 60% der erreichbaren Punkte in jeder Semesterhälfte.

Die Abgabe der praktischen Aufgaben hat am selben Tag zu erfolgen wie die Übungsaufgaben. Ist ein Kash-Programm gefragt, so wird ein lauffähiges Kash-Programm verlangt, das als Attachment per Mail an wagner@math.tu-berlin.de geschickt wird.

Weitere Informationen

Webseite der Kryptographie-VL im Sommersemester 2004