Kryptologie und Komplexität SS01 Zur aktuellen Vorlesung im WS03/04

Dozent Klaus Reinhardt
Sprechstunde Nach Vereinbarung, Raum 140, Sand 13, Tel. 77566
Zeit / Ort Mo 15:15-17, Mi 15:15-17 Morgenstelle N8
Umfang 4h
Begin 23.04.2001
Vorbesprechung -
Turnus 2-jährig
Prüfungsfach Theoretische Informatik

Beschreibung:

Kryptologie ermöglicht nicht nur geheime Kommunikation sondern auch Authentifikation, elektronische Unterschrift/Signatur und vieles mehr. Mit der rasanten Entwicklung elektronischer Kommunikationstechniken wie z.B. e-mail, WWW, Internet-banking, E- Shopping usw. und der zunehmenden Verbreitung ihrer Anwendungen ist die Nachfrage nach solchen Sicherheitsdienstleistungen in den letzten Jahren enorm gestiegen.

Ziel der Vorlesung soll es sein, sowohl die Grundlagen der Methoden wie z.B. RSA, Einwegfunktionen usw. zu verstehen, als auch deren Anwendungen z.B. elektronisches Geld (siehe CFN88), PGP usw. kennenzulernen.

Ferner werden wir Zusammenhänge zu den Komplexitätsklassen NP, RP, UP und BPP und Zeroknowledge/interaktive Beweissysteme (siehe Bab90) betrachten.


Voraussetzungen:


Bemerkungen:


Literaturliste: Kopie im Ordner

ADS93
M. Andrasiu, J. Dassow, A. Salomaa, G. Paun. Language-theoretic problems arising from Richelieu cryptosystems. Theoretical Computer Science 116, 1993.

Bab90
Lazlo Babai. E-mail and the unexpected power of interaction. Proceedings of the 5-th Structure, 1990.

BBE92
C. H. Bennett, G. Brassard, A. K. Ekert. Quanten-Kryptographie. Spectrum der Wissenschaft Dec. 1092

Beu87
Albrecht Beutelspacher. Kryptologie. Vieweg, 1987.

BSW95
Beutelspacher, J. Schwenk und K.-D. Wolfenstetter. Moderne Verfahren der Kryptographie. Vieweg, 1995.

CFN88
D. Chaum, A. Fiat, M. Naor. Untracable Electronic Cash. Proceedings of the CRYPTO88, 319­327.

CGMA85
B. Chor, S. Goldwasser, S. Micaili, B. Awerbuch. Verifiable Secrect Sharing and Achieving Simultaneity in the Presence of Faults. Proceedings of the FOCS'85, 383­395.

Des88
Yvo Desmedt. Abuses in Cryptogrphy and How to Fight Them. Proceedings of the CRYPTO88, 374­389.

EY80
Shimon Even, Yacov Yacobi. Cryptocomplexity and NP-Completeness. 7-th ICALP 90, 195--207, 1980.

FS86
A. Fiat, A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. Proceedings of the CRYPTO'86, 186-194.

Gol
Oded Goldreich. Foundations of Cryptography. Postscript File

Kar89
J. Kari. A Cryptosystem Based on Propositional Logic. Proceedings of the 5th IMYCS' 89, LNCS 381, 210--219, 1989

Kob98
Neal Koblitz. Algebraic Aspects of Cryptography. Springer, 1998

Kra86
Evangelos Kranakis. Primality and cryptography. Stuttgart, Teubner, 1986

MOV90
A. A. J. Menzes, P. C. van Oorschot and S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1997.

NS84
M. Naor, A. Shamir. Visual Cryptography. Proceedings of the Eurocrypt'94, 1-12. [ps]

Pap94
Christos H. Papadimitriou. Computational complexity. Addison-Wesley, 1994

Riv90
Ronald L. Rivest. Cryptographie. in L. van Leeuwen: Handbook of Theoretical Computer Science Volume A, The MIT Press/Elsevier, 1990.

Sal90
Arto Salomaa. Public-key Cryptographie. EATCS monographs on theoretical computer science, Springer, 1990.

Sch96
B. Schneier. Angewandte Kryptographie. Addison-Wesley, 1996.

Sti95
Douglas R. Stinson. Cryptography - Theory and Practice. CRC Press, 1995. ISBN 0-8493-8521-0.
Zu diesem Buch existiert auch eine Fehlerliste .


Inhalt

23.04.01: Geschichtlicher "Uberblick [Beu87] S 7 ff, Transpositionchiffre: Skytala, Substitutionschiffre: Caesar, Vigenere, Affine Chiffre [Sti95] S 8, Richelieu, Vernam,
Quanten-Kryptographie [BBE92],
25.04.01: RSA [Beu87] S67 ff bzw. [Sti95] S 114 ff: Schl"usselerzeugung, Euklidscher Algorithmus, Satz von Euler-Fermat,
30.04.01: Elektronisches Geld mit RSA [Beu87] S99, Primzahltests [Sti95] S 129 ff bzw. [Kra86]: Sieb des Eratosthenes, Wilson's Test, Lucas's Test,
02.05.01: Monte Carlo primzahltests: Fermat-test, Eulersches Kriterium, Jacobi symbol, Solovay-Strassen-test, Miller-Rabin-test
07.05.01: Pratt's Test: Pimzahlen in NP.
09.05.01: Faktorisierung: Pollard's rho. , p-1, bei bekanntem phi(n) oder bekanntem RSA-secret-key [Sti95] S 138 ff bzw. [MOV90] S 87 ff
14.05.01: Quadratisches Sieb, Rabin Kryptosystem.
16.05.01: Einwegfunktionen [Pap94] S 281, Komplexit"atsklassen,
21.05.01: Starke und schwache Einwegfunktionen [Gol] S 46 ff, Einweg Hashfunktionen [Sti95] S 233 ff oder [Gol] S 35 ff, W"orterbuchangriff, Geburtstagsangriff, Chaum-van Heijst-Pfitzmann Hashfunktion, diskreter Logartihmus,
23.05.01: Hashfunktion <=> Kryptosystem, diskreter Logartihmus, Shanks Alggorithmus, Pohlig Hellmann Algorithmus, ElGamal Kryptosystem [Sti95] S 163, ElGamal Signaturschema [Sti95] S 206,
28.05.01: Weitere Signaturschemata [Sti95] 30.05.01: Endliche Koerper und Elliptische Kurven [Sti95] S 177,
06.06.01: Schl"usselverteilung: Blom's Schema, Diffie-Hellmann Schl"usselverteilung, Kerberos. [Sti95] S 259
11.06.01: Schl"usselaustausch [Sti95] S 269, Zero-Knowledge Beweissysteme, Interaktive Beweissysteme [Sti95] S 387 ff oder [Gol] S 143 ff Graph-Nicht-Isomorphismus in IP, Graph-3-colorability in IP [Sti95] S 403 ff, [Gol] S 180 ff,
13.06.01: NP, BPP \subseteq IP(1), starker, schwacher interaktiver Beweis, [Sti95] S 387 ff, [Gol] S 153 ff, polynomielle Hierarchie in P^{#P}, Permanente #P-vollst.. LFKN Protokoll zur Pr"ufung der Permanente [Bab90],
18.06.01: IP=PSPACE
20.06.01: Kryptosysteme und NP-vollst"andigkeit [EY80], Merkle-Hellmann Knapsack System [Sti95] S 191,
25.06.01: Meet-in-the-middle Algorithmus, L^3 Gitter Basis Reduktion, Knapsack mit geringer Dichte [MOV90] S 118,
27.06.01: Gibt es NP-harte Public-Key Kryptosysteme? [EY80], McEliece System [Sti95] S 194,
02.07.01: nichtverfolgbares elektronisches Geld nichtverfolgbare elektronische Schecks [CFN88],
04.07.01: Kartenspiel "ubers Netz, Bestimmung des "alteren ohne Altersangabe, M"unzwurf per Telephon (Bit-commitment),
09.07.01: Das Teilen von Geheimnissen [Sti95] S 327, verifizierbares Teilen von Geheimnissen.[CGMA85]
11.07.01: Visuelle Kryptographie [NS94]

Kryptologie und Komplexität interaktiv
2001-01-029 Klaus Reinhardt (reinhard@informatik.uni-tuebingen.de)