Seminar im Wintersemester 2007/2008

Lehrveranstaltung:   Post-Quantum Kryptographie
Veranstaltungsform:  S2
Hochschullehrer:     Prof. J. Buchmann / R. Lindner / A. Schmidt
Sprechstunden:       Mo 13:30 (Schmidt), Fr 12:35  (Lindner)
Ort / Zeit:          S: S2/02-A213:: Do 16.15-17.55
Voraussetzungen:     Lineare Algebra / Einführung in die Kryptographie
Vorbesprechung:      18.10.2007
Forum:               LINK
Anmeldung:
Die Anmeldung ist abgeschlossen. Alle Bewerber wurden genommen.

Inhalt:
Aktuelle Standard-Kryptosysteme wie z.B. RSA, DSA und ECC können von Quantencomputern leicht gebrochen werden. Das Seminar befasst sich mit Post-Quantum-Kryptographie, das heißt mit Kryptosystemen, die selbst von Quantencomputern nicht effizient gebrochen werden können. Es sollen die Grundlagen der wichtigsten Systeme und bekannte Angriffe darauf erarbeitet werden.

Sprechstunden:
Da die Raumlage im Piloty in den Zeiten unserer Sprechstunden sehr angespannt ist, bitten wir euch zur Sprechstunde in unsere Büros zu kommen. Falls es dann zu voll wird suchen wir gemeinsam einen leeren Raum und hinterlassen für Nachzügler einen Hinweis.

Zielsetzung:
Die Teilnehmeranzahl ist auf 20 begrenzt. Es sollen in Zweier-Teams die fünf wichtigsten PQ-Systeme und bekannte Angriffe darauf in Zehn Präsentationen von ca. 30-45 Minuten vorgestellt werden. Zu jedem Vortrag wird ein 2-4 seitiges Handout angefertigt. Die Note setzt sich zu gleichen Teilen aus der gezeigten Präsentation und dem Handout zusammen.

Liste der Vorträge:

Nr Datum Thema Vortragende(r) Referenzen
18.10.07 Einführung [ppt] Lindner, Schmidt
25.10.07 LaTeX und Vortragsstil [ppt] Lindner, Schmidt [1, 2]
1.11.07
1 8.11.07 GGH Public Key [pdf,ppt] Mirza, Wodniok [3, 4, 5]
2 15.11.07 GGH Signature [pdf,ppt] Rahmen, Wang [3, 5, 11]
3 22.11.07 NTRU Public Key [pdf,ppt] Hansel, Franz [6, 7, 8]
4 29.11.07 NTRU Signature [pdf,odp] Müller, Rudel [9, 10, 11]
5 6.12.07 McEliece Public Key [pdf,ppt] Yang, Qian [12, 13, 25]
6 13.12.07 McEliece Signature [pdf,pdf] Cankir, Kart [14, 25]
20.12.07
27.12.07
3.1.08
8 10.1.08 MQ Signature [pdf,pdf] Huber, Dagdelen [22, 23, 24]
7 17.1.08 MQ Public Key [pdf,ppt] Heuser, Klement [19, 20, 21]
9 24.1.08 Merkle Signature [pdf,ppt] Fan, Braun [15,16]
10 24.1.08 Merkle Tree Traversal [pdf,ppt] Kim, Nguena [17,18]
31.1.08

Bibliographie:

  1. Englische LaTeX-Vorlage fürs Handout
  2. Deutsche LaTeX-Vorlage fürs Handout
  3. Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Public-key cryptosystems from lattice reduction problems. In Advances in Cryptology CRYPTO 97, volume 1294 of Lecture Notes in Computer Science. Springer-Verlag,1997., pages 112--131.
  4. Phong Nguyen: Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem. In Advances in Cryptology -- Proceedings of CRYPTO '99, vol. 1666 of Lecture Notes in Computer Science, Springer-Verlag. Pages 288--304.
  5. Daniele Micciancio: Improving Lattice Based Cryptosystems Using the Hermite Normal Form. CaLC 2001, LNCS 2146, pp. 126--145
  6. Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NTRU: A ringbased public key cryptosystem. Algorithmic Number Theory, ANTS-III, volume 1423 of Lecture Notes in Computer Science. Springer-Verlag, 1998, pages 267--288.
  7. Don Coppersmith and Adi Shamir. Lattice attacks on NTRU. Advances in Cryptology EUROCRYPT 97, volume 1233 of Lecture Notes in Computer Science. Springer-Verlag, 1997, pages 52--61.
  8. NTRUEncrypt Parameters
  9. Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman, and William Whyte. NTRUsign: Digital signatures using the NTRU lattice. Lecture Notes in Computer Science, 2612:122--140, 2003.
  10. NTRUSign Parameters
  11. P. Q. Nguyen and O. Regev. Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. In Proc. of Eurocrypt 06, volume 4004 of LNCS, pages 215--233. IACR, Springer-Verlag, 2006.
  12. R.J. McEliece: A public key cryptosystem based on algebraic coding theory, DSN progress report 42-44, S. 114-116, 1978
  13. Anne Canteaut and Nicolas Sendrier: Cryptanalysis of the Original McEliece Cryptosystem, Advances in Cryptology - ASIACRYPT'98, LNCS Volume 1514/1998
  14. Nicolas T. Courtois, Matthieu Finiasz , and Nicolas Sendrier: How to Achieve a McEliece-Based Digital Signature Scheme. Asiacrypt 2001
  15. Ralph C. Merkle, A certified digital signature, Proc. Crypto'89, volume 435 of LNCS, S. 218-238. Springer-Verlag, 1989
  16. J. Buchmann, L.C. Coronado Garcia, E. Dahmen, M. Doering, E. Klintsevich, CMSS - An Improved Merkle Signature Scheme, 7th International Conference on Cryptology in India - Indocrypt'06, LNCS 4392, Springer, 2006, S. 349-363
  17. M Szydlo - Merkle tree traversal in log space and time - Proceedings of Eurocrypt, 2004 - Springer
  18. M Jakobsson, T Leighton, S Micali, M Szydlo - Fractal Merkle Tree Representation and Traversal - RSA Cryptographers Track, RSA Security Conference, 2003 - Springer
  19. Christopher Wolf und Bart Preneel: Taxonomy of Public Key Schemes based on the problem of Multivariate Quadratic equations, Cryptology ePrint Archive, Report 2005/077, 2005
  20. Hideki Imai, Tsutomu Matsumoto: Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption, Eurocrypt 1988, Springer Verlag, S. 419-453
  21. Jintai Ding: A New Variant of the Matsumoto-Imai Cryptosystem through Perturbation, PKC 2004, LNCS 2947, S. 305-318, Springer Verlag, 2004
  22. Nicolas T. Courtois, Louis Goubin and Jacques Patarin: SFLASHv3, a fast asymmetric signature scheme, Cryptology ePrint Archive, Report 2003/211, 2003
  23. Jintai Ding and Dieter Schmidt: Cryptanalysis of SFlash v3, Cryptology ePrint Archive, Report 2004/103, 2004
  24. Vivien Dubois and Pierre-Alain Fouque and Adi Shamir and Jacques Stern: Practical Cryptanalysis of SFLASH, Cryptology ePrint Archive, Report 2007/141, 2007
  25. Daniela Engelbert, Raphael Overbeck, Arthur Schmidt: A Summary of McEliece-Type Cryptosystems and their Security (preprint)
Code-basierte Kryptosysteme: McEliece
  • J. Stern, A method for finding codewords of small weight, Coding Theory and Applications 388, S. 106-133, 1989, LNCS, Springer Verlag
Hash-basierte Kryptosysteme: Merkle
  • Leslie Lamport, Constructing digital signatures from a one way function, Technical Report SRI-CSL-98, SRI International Computer Science Laboratory, 1979

Printerenglisch deutsche Flagge   Impressum