Seminar: Interaktives Beweisen
| Termin: | SE Di 9-11 (RUD 25, 4.112) Prof. J.
Köbler, S. Kuhnert |
| Zuordnung: |
Hauptstudium, Seminar |
Inhalte und Lernziele
Normalerweise versteht man unter einem Beweis etwas statisches: Man kann ihn einmal aufschreiben und er bleibt in dieser Form unverändert gültig. In diesem Seminar betrachten wir eine Erweiterung dieses Prinzips: Zwei Akteure, der Beweiser und der Überprüfer, tauschen Nachrichten aus. Dabei möchte der Beweiser den Überprüfer von der Gültigkeit einer Aussage überzeugen, und der Überprüfer möchte nur Beweise für wahre Aussagen akzeptieren. In der Komplexitätstheorie sind in letzter Zeit zahlreiche Aussagen bewiesen worden, in denen interaktive Beweissysteme eine zentrale Rolle spielen.
Ein interessanter Spezialfall von interaktiven Beweisen sind die zero knowledge proofs, bei denen der Überprüfer durch die Interaktion mit dem Beweiser keine zusätzliche Information über die zu beweisende Aussage bekommt, sondern nur ihre Gültigkeit. Dies ermöglicht interessante Anwendungen in der Kryptographie.
Detaillierte Ankündigung mit Referatsthemen und Literatur
Themen für Referate
(die Termine sind noch vorläufig)- 5.5.: IP=PSPACE (Sophia Börner)
- 12.5.: AM[const]=AM[2] (Arite Lauschke)
- 19.5.: 3-Coloring in ZK (Roy Lieck)