NEW RESULTS IN GROUP THEORETIC CRYPTOLOGY by Michal Sramka A Dissertation Submitted to the Faculty of The Charles E. Schmidt College of Science in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy Florida Atlantic University Boca Raton, Florida December 2006 UMI Number: 3239161 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted.
Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. ® UMI UMI Microform 3239161 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code.
ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 NEW RESULTS IN GROUP THEORETIC CRYPTOLOGY by Michal Sramka This dissertation was prepared under the direction of the candidate's dissertation advisor, Dr. Magliveras, Department of Mathematical Sciences, and has been approved by the members of his supervisory committee. It was submitted to the faculty of The Charles E.
Schmidt College of Science and was accepted in partial fulfillment of the requirements for the degree of Doctor of Philosophy. SUPERVISORY COMMITTEE: arty 7 m.mụa Sciences Seo. Dean Ththarles Jess ES lege of Science „wWf2, 4.06 raduate Stites fd Programs Date ii Acknowledgments My foremost thanks go to my advisor and committee chair, Spyros Magliveras, for his guidance, encouragement, and support. Without him, this dissertation would not have been possible.
I thank him for his kindness and patience that helped during the difficult times, and for his insights and suggestions that shaped my academic and research skills. I thank the members of my committee — Professors Frederick Hoffman, Lee C. Klingler, and Ronald C. Mullin - who have dedicated their time to read and improve my dissertation, and provided invaluable help.
It has been a great privilege to spend several years in the Department of Mathematical Sciences at Florida Atlantic University. It has been a great pleasure working with the faculty, staff, and fellow graduate students. Many of these people have inspired, guided, and helped me during the time I worked on this dissertation. Finally, I would like to thank my family, my friends who are too numerous to mention, and all who trusted and supported me over the years.
Thank you all; you will always remain dear to me. iti Abstract Author: Michal Sramka Title: New Results in Group Theoretic Cryptology Institution: Florida Atlantic University Dissertation Advisor: Dr. Magliveras Degree: Doctor of Philosophy Year: 2006 With the publication of Shor’s quantum algorithm for solving discrete logarithms in finite cyclic groups, a need for new cryptographic primitives arose; namely, for more secure primitives that would prevail in the post-quantum era. The aim of this dissertation is to exploit some hard problems arising from group theory for use in cryptography.
Over the years, there have been many such proposals. We first look at two recently proposed schemes based on some form of a generalization of the discrete logarithm problem (DLP), identify their weaknesses, and cryptanalyze them. By applying the expertise gained from the above cryptanalyses, we define our own generalization of the DLP to arbitrary finite groups. We show that such a definition leads to the design of signature schemes and pseudo-random number generators with provable security under a security assumption based on a group theoretic problem.
In particular, our security assumption is based on the hardness of factorizing elements of the projective special linear group over a finite field in some representations. We construct a one-way function based on this group theoretic assumption and provide a security proof. iv Table of Contents 1 Introduction 1.1 Goals of the dissertation. c kg cu ng gà cv va va 1.2 Outline of the dissertation.2 Traditional DLP in cyclic groups .1 Shank’s baby step - giant step method.2 Schemes of Diffie-Hellman and ElGamal.3 Logarithmic signatures and covers.
eee eee ee ee 2.1 Traditional DLP and wild covers .4 Combinatorial group theory .000 ee eee ee eee 3 The Encryption Scheme of Kashyap et al. gà ga và g kg và va hán.‹đ«đadá 4 The Key Exchange Scheme of Stickel 4.1 The worst-case complexity analysis.2 The case of Scheme 42. 5 The Public-Key Cryptosystem of Wagner and Magyarik 31 5.1 The word choice problem .2 The Wagner-Magyarik (WM) cryptosystem and its critique .3 Our PKC based on finitely presented transformation groups.1 Some design issues .2 Additional observations and proofS. CS — — 43 6 A Generalization of the DLP and Construction of OWFs 44 6.) and the set p(s).2 The discrete logarithm problem for Sy(---) .3 A construction of one-way functions.
ee eee so 51 6.4 The projective special linear group PSL¿(fpg).1 A concrete instance of OWFs .5 Summary and open problems Ce —. 65 Bibliography 67 vi 1 Introduction The word cryptology was formed from the Greek words kryptés (hidden) and /ógos (word). In today’s information society, cryptology as the science of hidden, disguised information has become one of the main tools for secure communication, privacy, trust, access control, electronic payments, electronic voting, and for countless other applications. Cryptology is concerned with three dominant areas: cryptography, the science of designing secure schemes, cryptanalysis, the science of breaking them, and steganography, the science of hiding information by concealing the communications channel.
In the past, the use of cryptography was a privilege reserved for armies, governments, and highly skilled specialists. This is no longer true. Cryptographic schemes have become available for everyone. The main idea behind cryptanalysis is to find and exploit weaknesses or insecurity in cryptographic schemes.
Cryptanalysis might be undertaken by a hostile attacker, attempting to subvert a system, or simply by a system designer wishing to evaluate whether the proposed cryptographic scheme is secure. The results of cryptanalysis can be (and often are) used in cryptography to design more secure schemes. As cryptography evolved over decades and centuries, so did cryptanalysis. One important result from cryptanalysis says that cryptographic schemes based on the integer factorization problem or the discrete logarithm problem can be easily broken on a quantum computer [29].
From this follows one of the motivations to design new cryptographic schemes. In particular, the result of P. Shor [29] and the possibility of existence of quantum computers motivate the design of schemes that would withstand attacks by a quantum computer, so that these schemes would survive in the post-quantum era. There are two other commonly accepted motivations for proposing new cryptographic schemes.
The first is to propose a scheme that is more efficient in some way, compared to other known schemes. The second motivation is to propose a scheme that is provably secure.1 Goals of the dissertation This dissertation presents results from four research papers that in one way or another contribute to the area of group theoretic cryptology. Although the four papers do not necessarily explore cryptographic schemes based on the same underlying mathematical problem, the outcome of the research follows the goal of the dissertation — to study and cryptanalyze selected existing proposals in order to gain knowledge about group theoretic problems suitable for cryptographic purposes. Two major goals of this dissertation are to propose a Wagner-Magyarik-like public-key cryptosystem based on combinatorial group theory, and to define a generalization of the traditional discrete logarithm problem (DLP) to non-cyclic, preferably non-abelian, groups.
As a consequence, we use this definition to build one-way functions that lead to provably secure cryptographic schemes. Finally, a significant aim of this dissertation is to present selected cryptanalytic attacks which compromise recent cryptographic schemes based on group theory. Our motivation follows from the belief that many of the known decision and computation problems coming from group theory cannot be efficiently solved on a quantum computer. This belief is supported by the fact that some group theoretic decision problems are in fact algorithmically unsolvable (e., the word problem, as defined by Max Dehn in 1911).
Our approach to the goals of this dissertation follows the path mentioned in the previous paragraphs. In essence, we first study similar proposals by other authors, learn the advantages and tricks, discover and criticize the drawbacks, and when possible, cryptanalyze these proposals. The knowledge from cryptanalysis provides us with ways to avoid many common and trivial problems. In my first paper [31], I consider a proposed extension of the traditional DLP in a cyclic group to two generators of this group.
A simple cryptanalysis of the proposal reveals the computational triviality of such an extension and an equivalence with a known cryptographic scheme. This paper was accepted for publication in a refereed journal, but has not yet appeared. The research of my cryptanalysis of this scheme was presented at the 2nd Annual Science Research Symposium & Expo at FAU on September 21, 2006 and at the Algebra-Crypto Seminar at FAU in Fall 2006. My second paper [32] discusses a key exchange scheme based on a simple extension of the DLP to two non-commuting elements.
We provide a cryptanalysis of the scheme by exhibiting a procedure for significantly reducing the computational effort required to solve such an extension of the DLP in general abstract groups and also in the proposed matrix groups. My research in this paper was presented at the 20th Midwest Conference on Combinatorics, Cryptography and Computing in Wichita, Kansas on October 5-7, 2006. The paper has been submitted to the Journal of Combinatorial Mathematics and Combinatorial Computing which will publish the proceedings of the conference. Parts of the research from the paper were also presented at the Algebra-Crypto Seminar at FAU in Fall 2006.
In my third paper [3], the cryptanalysis of a cryptosystem based on the word problem in abstract groups leads to the design of another, more secure public-key cryptosystem. This is an example of a straightforward application of cryptanalytic results in cryptography. The research contained in this paper was presented at the WartaCrypt ’04 conference in Bedlewo, Poland on July 1-3, 2004. Parts of the research were also presented at the Southeastern Weekend Algebra Meeting in Hammond, Louisiana on November 5-7, 2004; at the 69th Florida Academy of Sciences Annual Meeting in Tampa, Florida on March 18-19, 2005; and at the Algebra-Crypto Seminar at FAU in Fall 2004.
My fourth paper (not yet submitted for publication) included in this dissertation deals with the definition of a generalized DLP to finitely generated non-abelian groups, and the necessary theory to construct a provably secure pseudo-random number generator and a provably secure signature scheme. In particular, the projective special linear group over a finite field of prime order is used, for which the security assumption is believed to hold. This research was presented at the Southeastern Algebra Conference in Auburn, Alabama on October 27-29, 2006. It remains to mention similar works that have been published in the area of proposing definitions and/or designing schemes based on some generalizations of the traditional DLP.
We do not claim that this list is complete. General extensions of the traditional DLP were proposed by A. Schemes based on some modification or extension of the traditional DLP include the schemes by S. Kashyap et al.2 Outline of the dissertation Today, there is a vast amount of cryptologic research and publications.
For the purpose of making this dissertation more self contained, we provide crucial definitions and known results in the “Preliminaries” section. This includes the definition of the traditional discrete logarithm problem in a cyclic group, its complexity, known attacks, and basic schemes based on the DLP. Some topics from combinatorial group theory and complexity theory related to cryptography are also presented here. The four sections following the “Preliminaries” section closely follow the four papers mentioned in the previous paragraphs.
Each research topic is summarized and concluded at the end of the particular section.