Seminar: Komplexität und Kryptologie
| Termin: | SE Mi 13-15 (RUD 25, 4.112) Prof. J. Köbler, S. Kuhnert |
| Zuordnung: | Hauptstudium, Seminar |
Der Seminarbeginn ist der Mi., 24.10.2007 (Einführung und Themenvergabe).
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:
- Einwegfunktionen
- Pseudozufallsgeneratoren
- Derandomisierung
- Nisan-Wigderson-Generatoren
- Arthur-Merlin-Klassen
- Hitting-Set-Generatoren
- Extraktoren
In den Vorträgen behandelte Themenbereiche
- Einführung und Themenvergabe am 24. Oktober 2007
Johannes Köbler - 07.11. und 14.11.: Äquivalenz der Existenz von schwachen und starken Einwegfkt.
Mark Kibanov
- 21.11.: Äquivalenz der Definitionen von sicheren PZG von Blum-Micali und Yao
Sebastian Kuhnert - 28.11.: Visuelle Kryptographie
Martin Apel - 05.12.: Derandomisierung von probabilistischen Komplexitätsklassen
Nils Alberti - 12.12. und 19.12.: Weitere Anwendungen: Multiparty Computations
Sarah Hauser
- 09.01.08 und 16.01.: Äquivalenz der Existenz von Einwegfkt. und PZG
Martin Stigge
- 30.01.
Nils Alberti
Empfohlene Literatur
Neben neueren Originalarbeiten ist folgende Literatur für dieses Seminar nützlich:
- S. Arora, B. Barak. Computational Complexity: A Modern Approach. Kapitel 10. Cryptography und Kapitel 16. Derandomization, Expanders and Extractors. Erscheint 2008. Online unter http://www.cs.princeton.edu/theory/complexity
- O. Goldreich: Foundations of Cryptography, Cambridge University Press, 2001. (Siehe auch: http://www.wisdom.weizmann.ac.il/~oded/ln00.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.