Seminar: Komplexität und Kryptologie

Dozenten: Prof. Johannes Köbler, Olaf Beyersdorff


Termin:	SE Mi 17-19 (RUD 25, 4.112) Prof. J. Köbler, O. Beyersdorff

Zuordnung:	Hauptstudium, Seminar

Inhalte und Lernziele

In diesem Seminar werden aktuelle Themen der Theoretischen Informatik, insbesondere der Komplexitätstheorie und der Kryptologie behandelt. Hierbei gehen wir auch gern auf Teilnehmerwünsche ein.

In diesem Semester wollen wir uns schwerpunktmäßig den Themen Pseudozufallsgeneratoren und Derandomisierung widmen. Die Erzeugung von Bitfolgen mit "zufälligen" Eigenschaften besitzt zahlreiche Anwendungen in der Kryptografie. Darüber hinaus sind Pseudozufallsgeneratoren ein zentrales Konzept der modernen Komplexitätstheorie, welches u.a. für die Derandomisierung probabilistischer Komplexitätsklassen genutzt werden kann.

Vorkenntnisse aus der Komplexitätstheorie sind zum Besuch dieses Seminars nützlich, jedoch nicht unabdingbar.

In den Vorträgen behandelte Themenbereiche

18.10.	Themenvorstellung	Johannes Köbler

16.11. 23.11. 30.11. 07.12.	Ununterscheidbarkeit, Unvorhersagbarkeit, Beziehungen zu Einwegfunktionen	Stephan Edel Ulf Hermann
14.12. 11.01. 18.01.	Derandomisierung von Komplexitätsklassen	Frank Habermann Olaf Schulz
25.01. 01.02.	Kommunikationskomplexität und Pseudo- zufallsgeneratoren für LOGSPACE	Helmut Weidner-Kim
08.02.	Schwächen des Key Scheduling Algorithm von RC4	Martin Apel

Empfohlene Literatur

Neben neueren Originalarbeiten ist folgende Literatur für dieses Seminar nützlich:

O. Goldreich. Foundations of Cryptography, Cambridge University Press, 2001. (Siehe auch: http://theory.lcs.mit.edu/~oded/frag.html )
O. Goldreich. Modern Cryptography, Probabilistic Proofs and Pseudorandomness, Springer-Verlag, Berlin Heidelberg, 1999.
R. Impagliazzo and A. Wigderson. P=BPP unless E has sub-exponential circuits: derandomizing the XOR lemma. In Proc. 29th ACM Symposium on Theory of Computing, pages 220-229. ACM Press, 1997.
V. Kabanets. Derandomization: a brief overview. Bulletin of the EATCS, 76:88--103, 2002.
N. Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449--461, 1992.
N. Nisan. Using Hard Problems to Create Pseudorandom Generators. PhD thesis, MIT Press, 1992.
D.R. Stinson. Cryptography: Theory and Practice. CRC Press, 1995.
A.C. Yao. Theory and applications of trapdoor functions. In Proc. 23rd IEEE Symposium on the Foundations of Computer Science, pages 80-91. IEEE Computer Society Press, 1982.
M. Luby. Pseudorandomness and Cryptographic Applications, Princeton University Press, 1996.
R. Motwani, P. Raghavan. Randomized Algorithms, Cambridge University Press, 1995.
M. Tompa. Lecture Notes on Probabilistic Algorithms and Pseudorandom Generators, 1991.
L. Trevisan. Lecture Notes from IAS Summer School on Computational Complexity, 2000.

Carsten Schwarz