Back to search

University of South Florida

Applications of Contracting Self-Similar Groups to Cryptography and Scale Groups

Abstract

dc:description

Given 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 × 9

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.usf.edu/etd/10883

Chain of custody

source
Harvested from
University of South Florida
Base URL
digitalcommons.usf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Malik, Arsalan Akram. Applications of Contracting Self-Similar Groups to Cryptography and Scale Groups. Dissertation thesis, University of South Florida, 2025. https://digitalcommons.usf.edu/etd/10883