Vorlesung im Wintersemester 2003/04

Algorithmen für Gruppen und Codes

(Prof. Dr. Thomas Beth, Dr. Markus Grassl)

9. Vorlesung: Faktorisierung in Gruppen und Kryptosysteme

(R. Steinwandt)

• logarithmische Signaturen
• Bijektion Z/|G|Z→G, Gemischtbasisdarstellung
• Verwendung von log. Signaturen zur Konstruktion einer (Trapdoor-)One-Way-Permutation
• Konstruktion eines Public-Key Encryption Scheme auf der Basis einer logarithmischen Signatur
• Schlüssellänge, Länge der log. Signatur
  "l(α)≥Σa(p) p" für |G|=Πp^a(p)
• untere Schranke wird angenommen für:
  • alle auflösbaren Gruppen
  • symmetrische Gruppen S_n
  • alle Gruppen G bis zur Ordnung 175559
  • offen: einfache Janko-Gruppe J₁ der Ordnung 175560
  • außerdem bekannt (nicht in der Vorlesung behandelt):
    • alternierende Gruppen A_n
    • PSL₂(q)

• M. I. González Vasco and R. Steinwandt.
  "Obstacles in Two Public Key Cryptosystems Based on Group Factorizations".
  Tatra Mountains Mathematical Publications, vol. 25, pp. 23-37, 2002.
• M. I. González Vasco, M. Rötteler, and R. Steinwandt.
  "On Minimal Length Factorizations of Finite Groups".
  Experimental Mathematics, 12(1): 1-12, 2003.
  online.
• S. S. Magliveras, D. R. Stinson, and Tran van Trung.
  "New Approaches to Designing Public Key Cryptosystems Using One-Way Functions and Trapdoors in Finite Groups".
  Journal of Cryptology, Vol. 15, No. 4, September 2002, pp. 285-297.
  SpringerLink
• S. S. Magliveras.
  "Secret- and Public-Key Cryptosystems from Group Factorizations;.
  Proceedings TatraCrypt '01, 2001.
  PostScript