The first Grigorchuk group and its applications to Group-based Cryptography
(2026) In Bachelor’s Theses in Mathematical Sciences MATK11 20261Mathematics (Faculty of Engineering)
Mathematics (Faculty of Sciences)
Centre for Mathematical Sciences
- Abstract
- In this thesis, we study groups of superpolynomial growth, with a particular focus on the first Grigorchuk group. Introduced by Rostislav Grigorchuk in 1980, this group serves as a fundamental example of a finitely generated group of intermediate growth.
The main result concerns the superpolynomial growth of the first Grigorchuk group, illustrating its relevance for the conjugacy search problem as an application to group-based cryptography.
This result contributes to understanding the connection between the growth rate of groups and algorithmic complexity required for public-key cryptographic protocols, which is briefly discussed here. - Popular Abstract
- Group theory can be regarded as the mathematical language for describing and measuring symmetry. Symmetry is defined as the property of an object to remain unchanged under certain transformations, and \textit{groups} provide a natural way to study such transformations algebraically.
The structure of a group is quite simple: take a set, and allow one operation on the elements of the set, such that they satisfy certain axioms.
Despite this simplicity, groups are one of the fundamental structures in pure mathematics, but they play an important role in other physical sciences as well. For example, in chemistry symmetry is used to classify molecules by their shape, in physics group theory is applied in quantum mechanics and in biology it is... (More) - Group theory can be regarded as the mathematical language for describing and measuring symmetry. Symmetry is defined as the property of an object to remain unchanged under certain transformations, and \textit{groups} provide a natural way to study such transformations algebraically.
The structure of a group is quite simple: take a set, and allow one operation on the elements of the set, such that they satisfy certain axioms.
Despite this simplicity, groups are one of the fundamental structures in pure mathematics, but they play an important role in other physical sciences as well. For example, in chemistry symmetry is used to classify molecules by their shape, in physics group theory is applied in quantum mechanics and in biology it is used in molecular systems. Last but not least, public-key cryptography relies on group theory, specifically finite groups.
Now, what is public-key cryptography? Also known as asymmetric cryptography, this is a method of encrypting or signing data with a pair of mathematically related keys, a public key for encryption and a private key for decryption. It enables secure communication without requiring a shared secret key beforehand, as the public key can be openly distributed.
Until the introduction of the asymmetric public-key cryptography in 1976, symmetric cryptography (where both parties need the same private key) was the dominant method for secure communication.
As a concrete example of cryptography, think of online banking, digital signatures, authentication protocols, or any similar process when information must be transferred safely - and to do this, information is encrypted through some algorithm, often based on mathematical problems that are easy to perform computationally but difficult to reverse without additional information.
To ensure that the encryption process is as safe as possible, some mathematicians have come up with certain criteria regarding the elements (numbers, or even functions) used during the encryption of the data. One criteria concerns the so-called \textit{growth rate} of the group from which these elements are taken from. In particular, the first Grigorchuk group is one which was shown to satisfy this growth requirement.
What this means in practice is that considering this group as a basis for the encryption algorithm would possibly give a secure way to transfer data.
The purpose of this thesis is to study the growth rate of the first Grigorchuk group, and to discuss its relevance for some protocols in group-based cryptography. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/student-papers/record/9240400
- author
- Kiss, Flora Golda LU
- supervisor
- organization
- course
- MATK11 20261
- year
- 2026
- type
- M2 - Bachelor Degree
- subject
- keywords
- The first Grigorchuk group, group-based cryptography, growth rate of groups, superpolynomial growth, binary rooted tree
- publication/series
- Bachelor’s Theses in Mathematical Sciences
- report number
- LUNFMA-4192-2026
- ISSN
- 1654-6229
- other publication id
- 2026:K14
- language
- English
- id
- 9240400
- date added to LUP
- 2026-07-27 11:38:48
- date last changed
- 2026-07-27 11:38:48
@misc{9240400,
abstract = {{In this thesis, we study groups of superpolynomial growth, with a particular focus on the first Grigorchuk group. Introduced by Rostislav Grigorchuk in 1980, this group serves as a fundamental example of a finitely generated group of intermediate growth.
The main result concerns the superpolynomial growth of the first Grigorchuk group, illustrating its relevance for the conjugacy search problem as an application to group-based cryptography.
This result contributes to understanding the connection between the growth rate of groups and algorithmic complexity required for public-key cryptographic protocols, which is briefly discussed here.}},
author = {{Kiss, Flora Golda}},
issn = {{1654-6229}},
language = {{eng}},
note = {{Student Paper}},
series = {{Bachelor’s Theses in Mathematical Sciences}},
title = {{The first Grigorchuk group and its applications to Group-based Cryptography}},
year = {{2026}},
}