Group Factorizations and Cryptology

Abstract

Asymmetric cryptosystems, also called public-key systems, can for instance be used for encrypting data, authentication and integrity checking of data. Such systems can be found in numerous protocols, e.g. in the areas World Wide Web (HTTPS based on SSL/TLS), e-mail (S/MIME, OpenPGP/PGP), remote command execution (SSH), file transfer (SCP), and many more. One-way functions are functions that can be computed efficiently, but are hard to invert. One-way functions that can be inverted efficiently with an additional information (the private key) are called trap-door functions. Asymmetric cryptosystems are based on trap-door functions. Most of the currently used asymmetric systems, especially RSA and ElGamal, are based on such functions in commutative algebraic structures. Whether commutative structures are a security issue due to their properties is unknown up to now. In any case the development and analysis of systems that are based on non-commutative structures is reasonable. A cryptosystem called MST1, which has been introduced by S. S. Magliveras, D. R. Stinson and T. van Trung, is based on so-called logarithmic signatures of arbitrary (also including non-commutative, i.e. non-abelian) finite groups. For a finite group G an ordered set L of subsets of G is being regarded, where each element of G has a unique representation as product of one element from each subset in L. L is then called a logarithmic signature. An interesting question now is whether there exist logarithmic signatures where it is hard to find a factorization as product in L for a given group element. If yes, this would be a one-way function: products of group elements (with factors from L) can be computed efficiently, but the inversion, i.e. finding a factorization as product in L, would be hard.

In this dissertation the realizability and security of MST1 is analyzed for various groups and logarithmic signature types.

The first part of the dissertation deals with the generation of logarithmic signatures. The ability to efficiently generate logarithmic signatures is a requirement for a concrete realization of the MST1 cryptosystem. We first investigate transformations of logarithmic signatures (their effect on factorization mappings, subclasses of transformations, compositions of transformations, etc.). Based on this, we develop an algorithm for generating logarithmic signatures. This algorithm also works with non-abelian groups, and for abelian groups the set of generated logarithmic signatures is typically a proper superset of the logarithmic signatures generated by the methods usually used in literature.

Subsequently, we regard the factorization problem with respect to logarithmic signatures for various groups. For abelian groups we develop factorization algorithms that are efficient for specific classes of logarithmic signatures. Furthermore, we develop a generic factorization algorithm, which not only works with logarithmic signatures but all block sequences (and the run-time depends on the structure of the input), and for which the efficiency can be shown for some large classes of logarithmic signatures. Moreover, we analyze logarithmic signatures of dihedral groups, and present efficient factorization algorithms for specific types of logarithmic signatures. These results are generalized and extended: we analyze the generalized quaternion group and wreath products.

In the previous investigations we used a specific representation of the group. In another part of the dissertation we analyze in which cases one can give an efficient algorithm for converting elements of an arbitrarily represented group (black box group) with known structure to the representation used in the previous chapters.

Finally, we present our program, in which a cryptosystem (based on a generalized MST1) and the various generation and factorization algorithms developed in this work have been implemented.

Asymmetrische Kryptosysteme, auch Public-Key-Systeme genannt, können u.a. zur Verschlüsselung von Daten, Authentifizierung und Sicherstellung der Integrität von Daten eingesetzt werden. Solche Systeme sind in zahlreichen Protokollen zu finden, z.B. in den Bereichen World Wide Web (HTTPS basierend auf SSL/TLS), E-Mail (S/MIME, OpenPGP/PGP), entfernte Befehlsausführung (SSH), Dateitransfer (SCP), und vielen weiteren. Einwegfunktionen sind Funktionen, die sich effizient berechnen lassen, aber sehr schwierig zu invertieren sind. Einwegfunktionen, die sich mit einer Zusatzinformation (dem privaten Schlüssel) doch effizient invertieren lassen, werden Falltürfunktionen genannt. Asymmetrische Kryptosysteme basieren auf Falltürfunktionen. Die meisten der heute verwendeten asymmetrischen Verfahren, insbesondere RSA und ElGamal, basieren auf solchen Funktionen in kommutativen algebraischen Strukturen. Ob kommutative Strukturen aufgrund deren Eigenschaften ein Sicherheitsproblem darstellen könnten, lässt sich derzeit nicht sagen. Auf jeden Fall ist die Entwicklung und Untersuchung von Verfahren, die auf nicht-kommutativen Strukturen beruhen, sinnvoll. Ein Kryptosystem namens MST1, das von S. S. Magliveras, D. R. Stinson und T. van Trung vorgestellt wurde, basiert auf sogenannten logarithmischen Signaturen von beliebigen (also auch nicht-kommutativen, d.h. nicht-abelschen) endlichen Gruppen. Für eine endliche Gruppe G wird eine geordnete Menge L von Teilmengen von G betrachtet, wobei jedes Element von G eine eindeutige Darstellung als Produkt von jeweils einem Element aus den Teilmengen in L haben soll. L wird dann eine logarithmische Signatur genannt. Interessant ist nun die Frage, ob es logarithmische Signaturen gibt, für die es schwierig ist, für ein gegebenes Gruppenelement eine solche Faktorisierung als Produkt in L zu finden. Falls ja, dann wäre dies eine Einwegfunktion: Produkte von Gruppenelementen (mit Faktoren aus L) können effizient berechnet werden, aber die Invertierung, d.h. das Finden einer Faktorisierung als Produkt in L, wäre schwierig.

In dieser Dissertation wird für verschiedene Gruppen und Typen logarithmischer Signaturen die Realisierbarkeit und Sicherheit von MST1 untersucht.

Der erste Teil der Dissertation befasst sich mit der Erzeugung von logarithmischen Signaturen. Logarithmische Signaturen effizient erzeugen zu können ist eine Voraussetzung für eine konkrete Realisierung des MST1-Kryptosystems. Wir untersuchen zunächst Transformationen logarithmischer Signaturen (deren Effekt auf Faktorisierungsabbildungen, Unterklassen von Transformationen, Hintereinanderausführungen von Transformationen, usw.). Basierend darauf entwickeln wir einen Algorithmus zur Erzeugung logarithmischer Signaturen. Dieser funktioniert auch mit nicht-abelschen Gruppen, und bei abelschen Gruppen werden in der Regel mehr logarithmische Signaturen erzeugt als bei den üblicherweise in der Literatur verwendeten Verfahren.

Danach betrachten wir das Faktorisierungsproblem bzgl. logarithmischer Signaturen für verschiedene Gruppen. Für abelsche Gruppen entwickeln wir Faktorisierungsalgorithmen, die bei bestimmten Klassen von logarithmischen Signaturen effizient sind. Außerdem entwickeln wir einen generischen Faktorisierungsalgorithmus, der nicht nur mit logarithmischen Signaturen sondern mit allen Blocksequenzen funktioniert (wobei die Laufzeit von der Struktur der Eingabe abhängig ist), und bei dem für einige große Klassen logarithmischer Signaturen die Effizienz gezeigt werden kann. Des Weiteren untersuchen wir logarithmische Signaturen von Diedergruppen, und geben effiziente Faktorisierungsalgorithmen für bestimmte Typen logarithmischer Signaturen an. Diese Ergebnisse werden verallgemeinert und ausgebaut; wir untersuchen u.a. die verallgemeinerte Quaternionengruppe und Kranzprodukte.

Bei den vorherigen Untersuchungen wurde jeweils eine bestimmte Darstellung der Gruppe verwendet. In einem weiteren Teil der Dissertation analysieren wir, in welchen Fällen sich für eine beliebig gegebene Gruppe (Black-Box-Gruppe) mit bekannter Struktur ein effizienter Algorithmus zur Konvertierung von Gruppenelementen in die Darstellung, die in den vorherigen Kapiteln verwendet wurde, angeben lässt.

Abschließend stellen wir unser Programm vor, in dem ein Kryptosystem (basierend auf einem verallgemeinerten MST1) und die verschiedenen in dieser Arbeit entwickelten Erzeugungs- und Faktorisierungsalgorithmen implementiert wurden.