Cryptographic protocols based on inner product spaces and group theory with a special focus on the use of Nielsen transformations

Abstract

The topic of this thesis is established in the area of mathematical cryptology, more precisely in group based cryptology. We give extensions of cryptographic protocols, develop new cryptographic protocols concerning the mathematical background and give modifications of them. In addition cryptographic analysis as well as examples are given. The focus lays on the development of new cryptographic protocols using non-commutative groups and of techniques, which are typically studied in combinatorial group theory. Automorphisms on finitely generated free groups are used, which can be generated by Nielsen transformations or Whitehead-Automorphisms. With the help of the Whitehead-Automorphisms we develop an approach for choosing automorphisms randomly of the automorphism group Aut(F), with F a finitely generated free group. Altogether twelve cryptographic protocols are explained. Among these are two extensions of a (n,t)-secret sharing protocol, which is introduced by C. S. Chum, B. Fine, G. Rosenberger and X. Zhang. Both extensions depend on the Closest Vector Theorem in a real inner product space. The first one (Protocol 1) is a symmetric key cryptosystem and the second one is a challenge and response system (Protocol 2), which can be used by a variation as a two-way authentication. Furthermore, the HKKS-key exchange protocol by M. Habbeb, D. Kahrobaei, C. Koupparis and V. Shpilrain, which uses semidirect products of (semi)groups, is extended to an ElGamal like public key cryptosystem (Protocol 3) and to a signature protocol (Protocol 4). There is an ongoing research about the HKKS-key exchange protocol with linear algebra attacks as well as research about suitable platforms, which also affects the ElGamal like public key cryptosystem and the signature protocol. A short overview of the research is given in this thesis. Furthermore, a purely combinatorial secret sharing scheme (Protocol 5) is introduced, which uses a share distribution method explained by D. Panagopoulos for a (n,t)-secret sharing scheme. We show that this share distribution method is a special case of a multiple assignment scheme introduced by M. Ito, A. Saito and T. Nishizeki. Furthermore, the introduced combinatorial secret sharing protocol is shown to be similar to a variation of a secret sharing protocol explained by J. Benaloh and J. Leichter. The idea of enhancing the combinatorial secret sharing scheme by using automorphisms on finitely generated free groups leads to two new secret sharing schemes. In addition a comparison to Shamir's secret sharing scheme is given. The first one is a secret sharing scheme using a finitely generated abstract free group F, a finitely generated free subgroup in SL(2,Q) and Nielsen transformations (Protocol 6). Protocol 6 is the basis for Protocol 7-12, which are also based on combinatorial group theory. The other secret sharing scheme (Protocol 7) uses a finitely generated free group F=< X | >, a Nielsen reduced set U ne X and a Nielsen equivalent set V to U and gives therefore the final input for the newly developed cryptographic Protocols 8-12, which are the main result in this thesis. Two new private key cryptosystems with similar modifications (Protocol 8 and Protocol 9) were developed, another new private key cryptosystem (Protocol 10), a new ElGamal like public key cryptosystem (Protocol 11) and a new challenge and response system (Protocol 12), which all use the combinatorial group theory and automorphisms on finitely generated free groups. Depending on the protocols the security is based on a linear congruence generator, the discrete logarithm problem in cyclic subgroups of the automorphism group of a finitely generated free group, the unknown algorithmic solution of the (constructive) membership problem in matrix groups over the rational numbers or Hilbert's Tenth Problem.

Das Thema dieser Arbeit ist angesiedelt in dem Gebiet der mathematischen Kryptologie, insbesondere in der gruppenbasierenden Kryptologie. Wir erweitern bestehende kryptographische Protokolle, entwickeln neue kryptographische Protokolle bezüglich des mathematischen Hintergrundes und geben Modifikationen für diese an. Erweitert wird die Arbeit durch Kryptoanalysen und Beispiele. Der Schwerpunkt dieser Arbeit liegt auf der Entwicklung von neuen kryptographischen Protokollen basierend auf nichtkommutativen Gruppen und Techniken, die typischerweise in der kombinatorischen Gruppentheorie Anwendung finden. Es werden Automorphismen von endlich erzeugten freien Gruppen genutzt, die mit Hilfe von Nielsen-Transformationen oder Whitehead-Automorphismen erzeugt werden können. Mit der Hilfe von Whitehead-Automorphismen entwickeln wir einen Vorschlag, um zufällig Automorphismen der Automorphismengruppe Aut(F) zu erzeugen, hierbei ist F eine endlich erzeugte freie Gruppe. Es werden insgesamt zwölf kryptographische Protokolle vorgestellt, die für diese Arbeit entwickelt wurden. Darunter sind zwei Erweiterungen eines (n,t)-Secret-Sharing-Verfahrens, das auf einer Idee von C. S. Chum, B. Fine, G. Rosenberger und X. Zhang basiert. Sie beruhen auf dem Dichtesten-Vektor-Theorem in einem euklidischen Vektorraum. Die erste Erweiterung (Protokoll 1) ist ein symmetrisches Kryptosystem. Die zweite ist ein Challenge-and-Response-Verfahren (Protokoll 2), das durch eine Variation auch als Zwei-Wege-Authentifizierung genutzt werden kann. Weiterhin werden zwei Erweiterungen des HKKS-Schlüsselaustausch-Protokolls von M. Habbeb, D. Kahrobaei, C. Koupparis und V. Shpilrain gegeben. Das HKKS-Schlüsselaustausch-Protokoll nutzt semidirekte Produkte von (Halb-)Gruppen und wird zu einem ElGamal ähnlichen asymmetrischen Kryptosystem (Protokoll 3) sowie zu einem Signatur-Protokoll (Protokoll 4) erweitert. Aktuell wird an dem HKKS-Schlüsselaustausch-Protokoll geforscht, so gibt es Angriffe basierend auf der linearen Algebra und es wird nach passeden Plattformen für dieses Verfahren gesucht. Diese Forschung betrifft auch das ElGamal ähnliche asymmetrische Kryptosystem und das Signatur-Protokoll. Ein kurzer Überblick über die Forschung zum HKKS-Schlüsselaustausch-Protokoll wird gegeben. Darüber hinaus wird ein rein kombinatorisches Secret-Sharing-Verfahren (Protokoll 5) vorgestellt. Dieses nutzt die Verteilung der Geheimnisse, wie sie D. Panagopoulos für ein (n,t)-Secret-Sharing-Verfahren erklärt. Wir zeigen, dass diese Verteilung der Geheimnisse, nach D. Panagopoulos, ein Spezialfall eines Multiple-Assignment-Verfahrens ist, das von M. Ito, A. Saito und T. Nishizeki eingeführt wird. Des Weiteren wird gezeigt, dass das vorgestellte kombinatorische Secret-Sharing-Protokoll ähnlich zu einer Variation eines Secret-Sharing-Protokolls von J. Benaloh und J. Leichter ist. Die Idee der Erweiterung des kombinatorischen Verfahrens durch die Benutzung von Automorphismen von endlich erzeugten freien Gruppen führt zu zwei neuen Secret-Sharing-Verfahren. Ein Vergleich zu Shamirs Secret-Sharing-Verfahren wird gegeben. Das erste der beiden neuen Secret-Sharing-Verfahren, nutzt eine endlich erzeugte freie Gruppe F, eine endlich erzeugte freie Untergruppe in der SL(2,Q) und Nielsen-Transformationen (Protokoll 6). Es bildet die Basis für die Protokolle 7-12, die auch auf der kombinatorischen Gruppentheorie basieren. Das andere Secret-Sharing-Verfahren (Protokoll 7) benutzt eine endlich erzeugte freie Gruppe F=< X | >, eine Nielsen reduzierte Menge U ne X und eine Nielsen äquivalente Menge V zu U und gibt somit den abschließenden Input für die neu entwickelten kryptographischen Protokolle 8-12, die das Hauptergebnis dieser Arbeit darstellen. Es war möglich zwei symmetrische Kryptosysteme mit ähnlichen Modifikationen (Protokoll 8 und Protokoll 9), ein weiteres symmetrische Kryptosystme (Protokoll 10), ein ElGamal ähnliches asymmetrisches Kryptosystem (Protokoll 11) und ein Challenge-and-Response-Protokoll (Protokoll 12) neu zu entwickeln, die alle die kombinatorische Gruppentheorie und Automorphismen auf endlich erzeugten freien Gruppen nutzen. Je nach Protokoll beruht die Sicherheit auf einem linearen Kongruenzgenerator, dem diskreten Logarithmus-Problem für zyklische Untergruppen der Automorphismengruppe einer endlich erzeugten freien Gruppe, der unbekannten algorithmischen Lösung des (konstruktiven) Untergruppenzugehörigkeitproblems in Matrixgruppen über rationalen Zahlen oder dem zehnten Problem von Hilbert.