Physical Sciences and Mathematics Commons^™

Algorithmic Properties Of Poly-Z Groups And Secret Sharing Using Non-Commutative Groups, Bren Cavallo

Dissertations, Theses, and Capstone Projects

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 …