Analysis of a Group of Automorphisms of a Free Group as a Platform for Conjugacy-Based Group Cryptography

Author

Pavel Shostak, The Graduate Center, City University of New YorkFollow

Date of Degree

5-2019

Document Type

Dissertation

Degree Name

Ph.D.

Program

Computer Science

Advisor

Alexei Miasnikov

Committee Members

Robert Haralick

Vladimir Shpilrain

Alexander Ushakov

Subject Categories

Algebra | Information Security

Abstract

Let F be a finitely generated free group and Aut(F) its group of automorphisms.

In this monograph we discuss potential uses of Aut(F) in group-based cryptography.

Our main focus is on using Aut(F) as a platform group for the Anshel-Anshel-Goldfeld protocol, Ko-Lee protocol, and other protocols based on different versions of the conjugacy search problem or decomposition problem, such as Shpilrain-Ushakov protocol.

We attack the Anshel-Anshel-Goldfeld and Ko-Lee protocols by adapting the existing types of the length-based attack to the specifics of Aut(F). We also present our own version of the length-based attack that significantly increases the attack' success rate. After discussing attacks, we discuss the ways to make keys from Aut(F) resistant to the different versions of length-based attacks including our own.

Recommended Citation

Shostak, Pavel, "Analysis of a Group of Automorphisms of a Free Group as a Platform for Conjugacy-Based Group Cryptography" (2019). CUNY Academic Works.
https://academicworks.cuny.edu/gc_etds/3239