AG von zur Gathen - Algorithmische Mathematik

Wintersemester 2000/01

Seminar Kryptographie(VKomm)

Nichtwissen ist alles

Goldwasser, Micali & Rackoff  haben 1989 die ``Nullwissenprotokolle'' erfunden.  Sie haben die erstaunliche Eigenschaft, dass man einen Skeptiker von der Wahrheit einer Aussage überzeugen kann, ohne aber mehr als diese Wahrheit zu verraten.  Z.B. kann man jemand von der Lösbarkeit gewisser Gleichungen überzeugen, ohne etwas über die Lösung zu verraten.  Dies kann man gut in der Kryptographie einsetzen, etwa um jemanden von meiner Identität zu überzeugen.

Es hat sich dann gezeigt, dass ``alle'' berechnungsmässig wichtigen Probleme, nämlich alle in NP, solche Nullwissenprotokolle zulassen.

Im Seminar werden die Begriffe und Ergebnisse von Anfang an entwickelt.

Nützliche Parallelveranstaltungen

Organisatorisches

Zeit und Ort: Mittwoch 16-18 Uhr, H7.312.
Vorbesprechung: 18. Oktober 2000, 1615 Uhr, D3.230.
Studiengänge: LS II (Medienschein möglich), Mathematik Diplom, Informatik Diplom.
Scheinerwerb: Vortrag und Ausarbeitung.
Qualifizierter SN: Ja.

Themen

 
Datum Thema Vortragende(r)
25.10.2000
08.11.2000		 Perfektes Nullwissen. Bela Kovac
Dani Kräutle
15.11.2000
22.11.2000		 Pseudozufallsgeneratoren. Stefan Bertels
Barbara Fritsch
29.11.2000 Bitfestlegungen. Michael O'Swald
06.12.2000 Zwei DLP-basierte Festlegungsschemata. Rüdiger Hanke
13.12.2000 Graph-3-Färbbarkeit ist beweisbar in Nullwissen. Markus Diekämper
20.12.2000 Details zu G3C ist Nullwissen. Jules Simo
10.01.2001 Jedes NP-Problem ist beweisbar in Nullwissen. Marc Jesse
17.01.2001 Alles Beweisbare ist beweisbar in Nullwissen. Marcel Ackermann
24.01.2001 Rücksetzbares Nullwissen (Diplomarbeit, 452kB). Olaf Müller
31.01.2001 Weitere Nullwissenbeispiele. Tobias Jakob

Links und Literatur


Author: Michael Nüsken, last change: