Date of Degree

9-2015

Document Type

Dissertation

Degree Name

Ph.D.

Program

Mathematics

Advisor(s)

Delaram Kahrobaei

Subject Categories

Mathematics

Keywords

computational complexity; cryptography; group theory

Abstract

Computational aspects of polycyclic groups have been used to study cryptography since 2004 when Eick and Kahrobaei proposed polycyclic groups as a platform for conjugacy based cryptographic protocols.

In the first chapter we study the conjugacy problem in polycyclic groups and construct a family of torsion-free polycyclic groups where the uniform conjugacy problem over the entire family is at least as hard as the subset sum problem. We further show that the conjugacy problem in these groups is in NP, implying that the uniform conjugacy problem is NP-complete over these groups. This is joint work with Delaram Kahrobaei. We also present an algorithm for the conjugacy problem in groups of the form $\Z^n \rtimes_\phi \Z$.

We continue by studying automorphisms of poly-$\Z$ groups and successive cyclic extensions of arbitrary groups. We study a certain kind of extension that we call "deranged", and show that the automorphisms of the resulting group have a strict form. We also show that the automorphism group of a group obtained by iterated extensions of this type contains a non-abelian free group if and only if the original base group does. Finally we show that it is possible to verify that a finitely presented by infinite cyclic group is finitely presented by infinite cyclic, but that determining that a general finitely presented group is finitely generated by infinite cyclic is undecidable. We then discuss implications the latter result has for calculating the Bieri-Neumann-Strebel invariant. This is joint work with Jordi Delgado, Delaram Kahrobaei, Ha Lam, and Enric Ventura and is currently in preparation.

In the final chapter we discuss secret sharing schemes and variations. We begin with classical secret sharing schemes and present variations that allow them to be more practical. We then present a secret sharing scheme due to Habeeb, Kahrobaei, and Shpilrain. Finally, we present an original adjustment to their scheme that involves the shortlex order on a group and allows less information to be transmitted each time a secret is shared. Additionally, we propose additional steps that allow participants to update their information independently so that the scheme remains secure over multiple rounds. This is joint work with Delaram Kahrobaei.

Included in

Mathematics Commons

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.