Seminar "Kryptographie und Komplexität" im SS 2005

Prof. Dr. C.-P. Schnorr, R. Hartung, A. Scemama

Inhalt:

Das Seminar beschäftigt sich mit verschiedenen Kryptoschemata, die auf der Schwierigkeit des Diskreten Logarithmus beruhen. Im Vordergrund steht dabei die Frage, inwieweit sich Protokolle, die für Gruppen mit bekannter Ordnung entworfen wurden, auf Gruppen mit unbekannter Ordnung übertragen lassen. Ein wichtiges Beispiel für eine Gruppe mit unbekannter Ordnung ist etwa die multiplikative Gruppe des Rings Z/nZ, wobei n eine zusammengesetzte Zahl ist, deren Primfaktorzerlegung geheim gehalten wird.

Zusatzmaterial:



Zum Problem des Übergangs von Gruppen bekannter Ordnung auf Gruppen unbekannter Ordnung vgl. Endre Bangerter, Jan Camenisch, Ueli Maurer: Efficient Proofs of Knowledge of Discrete Logarithms and Representations in Groups with Hidden Order. Public Key Cryptography 2005: 154-171. Diese Arbeit bildet auch die Grundlage für die beiden vorletzten Vorträge.
Als Hintergrund hierzu (gleichzeitig das Material für den Eröffnungsvortrag) findet sich in einem Vorlesungsskript von I. Damgard zu Sigma-Protokollen; ferner in der kurzen Arbeit von Marc Girault: An identity-based identification scheme based on discrete logarithms modulo a composite number, in EUROCRYPT 1990, S. 481-486. Ferner kann die Dissertation von Ronald Cramer, Modular Design of Secure yet Practical Cryptographic Protocols, auf Wunsch bei mir eingesehen werden
Zu allgemeinen Fragen zu bestimmten Schemata oder Protokolltypen in der Kryptographie vgl. etwa das inoffizielle (!) Vorlesungsskript pdf ps.
Bei speziellen Fragen zu den einzelnen Artikeln empfiehlt sich auch ein Blick in das jeweilige Literaturverzeichnis.
Allgemein erfordern alle Themen eine profunde Kenntnis modularer Arithmetik und des Diskreten Logarithmus sowie ein grundlegendes Verständnis für Fragen der Komplexität. Bei Schwierigkeiten ist eine eingehende Beschäftigung mit Diskreter Mathematik dringend angeraten; Material etwa hier.

Programm:

Die untenstehende Tabelle gibt das vorläufige Programm des Seminars wieder. Bis Semesterbeginn können noch größere Umstellungen auftreten. Die Vorträge finden immer mittwochs von 14 c.t. - 16 im Raum 901 statt; eine Ausnahme bildet die letzte Sitzung (s.u.). Das Seminar beginnt erst am 25. Mai (5. Vorlesungswoche).


Bitte beachtet die Terminänderungen!


Vorträge
   25. 5. Antoine Scemama: Sigma-Protokolle
  1. 6. Rudolf Polzer: Integer Commitment in Gruppen unbekannter Ordnung
  8.6. keine Sitzung!
  15.6. keine Sitzung!
   22. 6. Matthias Krieger: Elektronische Wahlen (I)
  29. 6. Hassan Moussif: Elektronische Wahlen (II)
   06. 7. Sebastian Herzog: "Non-Malleability" bei Commitment Schemes
   13. 7. Olga Davidoff / Marina Gurewitsch: Sigma-Protokolle in Gruppen unbekannter Ordnung (I)
   20. 7. Olga Davidoff / Marina Gurewitsch: Sigma-Protokolle in Gruppen unbekannter Ordnung (II)



Organisatorisches:

An alle Teilnehmer: Bitte beachtet, dass Eure Vortragsvorbereitung zwei Wochen vor dem geplanten Vortragstermin vollständig abgeschlossen sein soll; das schließt auch die Erstellung eines Handouts ein. Zu diesem Zeitpunkt möchte ich Eure Ausarbeitung mit Euch diskutieren und einen Eindruck von Eurem Vortrag bekommen ("Probevortrag"). Für den Vortrag stehen 60 Minuten zur Verfügung. Aber auch zuvor wird erwartet, dass Ihr regelmäßig über den Stand Eurer Vorbereitungen Auskunft gebt.
Fortgeschrittene Teilnehmer des Seminars sind auch zum Besuch der AG der Mathematischen Informatik eingeladen.



Rupert Hartung



Homepage des ISMI