Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

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.
Im Seminar sind Vorträge einführenden und vertiefenden Charakters zu folgenden Themenbereichen geplant:
  • Pseudozufallsgeneratoren
  • Derandomisierung
  • Nisan- Wigderson- Generatoren
  • Arthur- Merlin- Klassen
  • Hitting- Set- Generatoren
  • Extractoren

In den Vorträgen behandelte Themenbereiche

  1. Einführung und Themenvergabe am 19. Oktober 2005
    Johannes Köbler


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 )
  • D. Gutfreund, R. Shaltiel A. Ta-Shma: If NP languages are hard on the worst-case then it is easy to find their hard instances, Proceedings of the Twentieth Annual IEEE Conference on Computational Complexity, 2005.
  • D.E. Knuth: The Art of Computer Programming, Band 2, Addison-Wesley, 1982.
  • D.E. Knuth und A.C. Yao: The Complexity of Nonuniform Random Number Generation. In: Algorithms and Complexity, J.F Traub (Ed.), Academic Press, 1976.
  • J.C. Lagarias: Pseudorandom Number Generators in Cryptography and Number Theory. In: Cryptology and Computational Number Theory, C. Pomerance(Ed.), American Mathematical Society, 1990.
  • M. Luby: Pseudorandomness and Cryptographic Applications, Princeton University Press, 1996.
  • R. Motwani, P. Raghavan: Randomized Algorithms, Cambridge University Press, 1995.
  • D.R. Stinson: Cryptography, CRC 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.
  • R. Shaltiel, C. Umans: Pseudorandomness for Approximate Counting and Sampling, Proceedings of the Twentieth Annual IEEE Conference on Computational Complexity, 2005.