University of South Florida
Applications of Contracting Self-Similar Groups to Cryptography and Scale Groups
Abstract
dc:descriptionGiven their peculiar properties, self-similar groups are of great interest both from applications and theoretical standpoints. In this work we study the scope of their applications in post-quantum cryptography and in constructing scale groups via lifting maps. We propose self-similar contracting groups as a platform for cryptographic schemes based on simultaneous conjugacy search problem (SCSP). This class of groups admits fast polynomial-time algorithms for the word problem and element multiplication that can be used for effective encryption and decryption of messages. It contains extraordinary examples like the Grigorchuk group, which is known to be non-linear, thus making some of existing attacks against SCSP inapplicable. The elements of groups in this class admit a natural normal form based on the notion of a nucleus portrait that plays a key role in our approach. While for some of these groups, the conjugacy search problem has been studied, there is no general algorithm working for a large class, and there are currently no studies of the simultaneous version of the problem. We discuss benefits and drawbacks of using these groups in group-based cryptography and provide computational analysis of one of our proposed variants of the length-based attack on SCSP for some purposefully selected groups in the class, including the Grigorchuk and Basilica groups. Our analysis shows that the studied version of the length-based attack is least effective when a platform group has a large nucleus and is acting on a tree of a large degree. We study the multi-EGS groups that, as we prove, satisfy both of these properties. We explicitly compute the contracting nuclei of the groups in this class and specialize our results to the classes of multi-edge spinal groups and EGS-groups. Additionally, we provide sufficient conditions for these groups to be liftable and thus to produce new examples of groups acting transitively on regular trees of finite degree stabilizing one of the ends, whose closures are scale groups as defined by Willis.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy (Ph.D.)
- Level thesis:degree_level
- Dissertation
- Discipline thesis:degree_discipline
- Mathematics and Statistics
- Grantor
- University of South Florida
- Year dc:date
- 2025
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Malik, Arsalan Akram
- Contributors dc:contributor
-
- Dmytro Savchuk, Ph.D.
- Brian W. Curtin, Ph.D.
- Nataša Jonoska, Ph.D.
- Rostislav Grigorchuk, Ph.D.
Subjects
dc:subject × 9Identifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.usf.edu/etd/10883