Events for 05/14/2025 from all calendars

Groups and Dynamics Seminar

Time: 3:00PM - 4:00PM

Location: BLOC 628

Speaker: Dmytro Savchuk, University of South Florida

Title: Simultaneous Conjugacy Search Problem in Contracting Self-similar Groups

Abstract: Many modern group-based cryptographic protocols are based on the variants of conjugacy search problem. We study the simultaneous conjugacy search problem (SCSP) in the class of self-similar contracting groups. This class of groups contains extraordinary examples like Grigorchuk group, which is known to be non-linear as a group of intermediate growth, thus has a potential to withstand certain cryptanalytic attacks. The groups in this class admit a natural normal form based on the notion of a nucleus portrait and admit a fast polynomial time algorithm solving the word problem. While for some groups in the class the conjugacy search problem has been studied, there are many groups for which no such algorithms are known. We discuss benefits and drawbacks of using these groups in cryptography and provide computational analysis of variants of the length based attack on SCSP for some groups in the class, including Grigorchuk group. Additionally, we discuss another effective heuristic attack on SCSP for contracting groups acting on a binary tree. The talk is based on two projects joint with Delaram Kahrobaei, Arsalan Malik, and Luciana Scuderi and Kerry Seekamp.