Skip to Main Content

Group-based Cryptography in the Quantum Era

Delaram Kahrobaei
Ramón Flores
Marialaura Noce

Communicated by Notices Associate Editor Reza Malek-Madani

1. Introduction

Today’s digital infrastructure relies on cryptography in order to ensure the confidentiality and integrity of digital transactions. At the heart of these techniques is public key cryptography, which provides a method for two parties to communicate privately, despite the lack of any pre-arranged security keys.

Graphic without alt text

These protocols mainly rely on the fact that deciphering encoded communications is tantamount to solving mathematical problems which are widely thought to be infeasible (two such examples are the factoring problem and the discrete logarithm problem). Yet we know that with the advent of large-scale quantum computers (devices that compute according to the laws of quantum mechanics), both the factoring and discrete logarithm problems are completely broken, meaning that our existing public-key cryptography infrastructure has become insecure.

We are thus at a crossroads in terms of security: Is the security of our digital infrastructure ready for the advent of quantum computers? While security is the common goal, the mathematical theory of group theory is the common methodology. Group theory is a broad and rich theory that models the technical tools used for the design and analysis in this research.

Some of the candidates for post-quantum cryptography (PQC) have been known for years, while others are still emerging.

Group theory, and in particular non-abelian groups, offers a rich supply of complex and varied problems for cryptography; reciprocally, the study of cryptographic algorithms built from these problems has contributed results to computational group theory.

In 2015, NSA and NIST made an announcement for post-quantum cryptosystems. In July 5, 2022, the round four finalists were announced NIS22. Among them, the following were short-listed: lattice-based, code-based, isogeny-based, and hash-based primitives.

In 2016 Anshel, Atkins, Goldfeld, and Gunnells, submitted a proposal to the NIST competition which faced several attacks by Petit et al (PKC 2017), Blackburn et al (ASIACRYPT 2018), Ushakov et al (DCC 2019). Recently in AAGG21, the same authors have proposed a group-based digital signature WalnutDSA which the authors claim is safe against all those attacks and quantum-resistant.

In 1999, Anshel, Anshel, and Goldfeld AAG99 proposed the commutator key-exchange protocol based on braid groups. Ko, Lee et al. proposed a non-commutative version of Diffie–Hellman using braid groups in 2000 KLC00.

Though braid groups were the suggested platform for both protocols, researchers have been motivated to find other suitable classes of groups for non-commutative group-based cryptography. On the other hand, in the last couple of decades, the complexity of some group-theoretic problems have been studied.

We now present a brief history of the proposed platform groups and algorithmic group theoretic problems for cryptography.

In 2004, Eick and Kahrobaei proposed polycyclic groups as a new platform for cryptography. These groups are natural generalizations of cyclic groups with more complex algorithmic theory (see Section 3.1 for more details). Grigoriev and Ponomarenko in 2004 suggested groups of matrices for a homomorphic encryption scheme. In 2008, Ostrovsky and Skeith determined sufficient and necessary conditions for the existence of a fully homomorphic encryption scheme (FHE) over a nonzero ring if and only if there exists an FHE over a finite non-abelian simple group. Simple groups have also been proposed for hash functions by Petit and Quisquater in 2016.

In 2017, Chatterji, Kahrobaei et al studied the subgroup distortion problem in hyperbolic groups. Kahrobaei and Mallahi-Karai proposed arithmetic groups as a new platform for the same protocol in 2019. Since 2016 graph groups have been proposed for various cryptographic protocols by Flores, Kahrobaei, and Koberda, since several of the algorithmic problems in these groups are NP-complete which provides quantum-resistant cryptosystems (see FKK19, Section 7). We extensively address this in section 2.2. In 2019, Kahrobaei, Tortora, and Tota proposed nilpotent groups for making multi-linear maps. We conclude by mentioning that several other classes of groups were proposed in the last couple of decades for platforms for group-based cryptography. This list includes automata groups (1991 by Garzon and Zalcstein, in 2019 by Grigorchuk and Grigoriev), Thompson group (Shpilrain and Ushakov, 2006), free metabelian groups (Shpilrain and Zapata in 2006, and Kahrobaei and Habeeb in 2012), small cancellation groups (Habeeb, Kahrobaei, Shpilrain 2012), free nilpotent -groups (Kahrobaei and Shpilrain, 2016), Engel groups (Kahrobaei and Noce, 2020), and infinite pro- groups (Kahrobaei and Stanojkovski, 2021).

Next we discuss aspects that should be considered for post-quantum group-based primitive.

The security of classical cryptographic schemes such as RSA, and Diffie–Hellman are based on the difficulty of factoring large integers and of finding discrete logarithms in finite cyclic groups, respectively. A quantum computer is able to solve the aforementioned problems attacking the security of these cryptographic algorithms. More precisely, Shor’s algorithm factors discrete logarithm problems and Grover’s algorithm can improve brute force attacks by significantly reducing search spaces for private keys. As a result, researchers are now interested in cryptography that is secure in a post-quantum world.

We recall that a subgroup of a group is hidden by a function from to a set if it is constant over all cosets of , and takes distinct values on distinct cosets.

Figure 1.

The hidden subgroup problem.

Graphic without alt text

In other words, for any , if and only if . This problem asks then whether, given a finitely generated group and an efficiently computable function from to some finite set such that is constant and distinct on left-cosets of a subgroup of finite index, we can find a finite generating set for . Given a hidden subgroup , the hidden subgroup problem (HSP) asks to find a generating set for using information from evaluations of via an oracle.

In summary, to analyze whether group-based cryptosystems are post-quantum one studies the relationship between the proposed algorithmic problems and the HSP, and Grover’s search algorithm for the proper parameters in the proposed platform groups. Note that cryptosystems based on NP-complete problems are not vulnerable at this time to quantum cryptanalysis.

In this paper, we present the current status and the approach of post-quantum group-based cryptography. In particular, we focus our attention on two classes of groups as platform groups for possible cryptographic protocols: polycyclic and graph groups. About the former, the complexity of algorithmic problems made polycyclic groups suitable platforms for cryptography. Likewise, graph groups are good post-quantum systems since many of the algorithmic problems presented are NP-complete.

We remark that our treatment of the algorithmic problem in graph groups in Section 2.2 is more detailed, because these groups are defined more concretely and possess a very useful normal form, so their behavior with respect to these problems is better understood than that of polycyclic groups.

We address this paper to survey several classical and novel algorithmic problems for both polycyclic and graph groups with a view toward applications to cryptography. Finally, we present a real-life implementation of a combinatorial algebraic fully homomorphic encryption scheme which has been used for data analysis of encrypted medical data. We also include a list of open problems, which we hope will guide researchers who wish to work in this field.

2. Platform Groups

The study of groups mostly as combinatorial objects (using group presentation with generators and relators) is the area of group theory known as combinatorial group theory, which has been developed in order to find solutions to the so-called decision problems (i.e., problems with “yes” or “no” answers).

More precisely, let and , where the latter is called the set of formal inverses. The elements of and its formal inverses are called letters, and a word in is a finite (possibly empty) sequence of letters of . A word in the set is freely reduced over if it contains no adjacent symbols or . The group is a free group with basis if is a set of generators for and no nonempty freely reduced word over represents, as a product, the identity element of (note that the empty string represents the identity element). As an example, one can consider the group of the integers, which is the free group with a single generator.

The following three decision problems were introduced by Dehn in 1911, and are usually called the “Dehn problems.” They are defined as follows:

Word Problem: For any , determine if is the identity element of .

Conjugacy Problem: For any , determine if and are conjugate, that is, if there exists an element (a conjugator) such that .

Isomorphism Problem: Let and be groups given by finite presentations, determine if is isomorphic to .

In general, decision problems are problems of the following nature: given a property and an object , find out whether or not the object has the property . Search problems are of the following nature: given a property and an object with the property , find something “material” establishing the property ; for example, given two conjugate elements of a group, find a conjugator. In other words, given a group and where is a conjugate of , the conjugacy search problem is the problem to find an element such that . The conjugation is usually denoted by .

There are many other algorithmic problems which have been used in group-based cryptography; see Section 2.2 for more examples in graph groups.

2.1. Polycyclic groups

We start this section by stating the main definitions we need. A series of a group G is a chain of subgroups such that each is normal in . A group is said to be polycyclic if it has a subnormal series such that the quotient groups are cyclic. This series is called a polycyclic series. The Hirsch length of a polycyclic group is the number of infinite factors in its polycyclic series. Though a polycyclic group can have more than one polycyclic series, it is a consequence of the Schreier Refinement Theorem that its Hirsch length is independent of the choice of series.

Every polycyclic group can be described by a polycyclic presentation of the following form:

where are words in the generators and is the set of indices such that is finite.

A group is said to be nilpotent if and only if possess a central series, that is, if there exists a chain of subgroups of : such that for any , normal in and , where is the center of .

If a group is nilpotent, the minimal length of a central series is said to be the nilpotency class of and it is denoted by cl.

Finally, given a prime number , a group is a -group if the order of every element is a power of . Nilpotent groups of class 1 are abelian groups, and finite -groups of order are nilpotent of class at most .

Polycyclic groups have been always of interest in classical cryptography. Cyclic groups are obviously polycyclic and they have been used in the classical cryptosystems such as RSA and Diffie–Hellman.

Polycyclic groups are natural generalizations of cyclic groups with more complex algorithmic problems which provide suitable platforms for cryptography. Finitely generated nilpotent groups are polycyclic and -groups are nilpotent. We discuss both applications of finite and infinite polycyclic groups here.

Regarding the Dehn problems in polycyclic groups, the word problem can be solved efficiently, while the solution of the conjugacy problem is conjectured to be exponential time, and in particular seems not efficient. Many experiments have been run by Eick and Kahrobaei in 2004, as well as by Garber, Kahrobaei, and Lam in 2013, which back up this conjecture for some classes of polycyclic groups.

There are polycyclic groups that are metabelian, as for example the group of permutations of three elements. Recall that a group is metabelian if it is an extension of abelian groups. In GKMP19 Gryak, Kahrobaei, and Martínez-Pérez analyzed the computational complexity of an algorithm to solve the conjugacy search problem in a certain family of metabelian groups. They proved that in general the time complexity of the conjugacy search problem for these groups is at most exponential. They also showed that for a different subfamily, namely the generalized metabelian Baumslag–Solitar groups the conjugacy search problem reduces to the discrete logarithm problem.

In GHK20 Gryak, Kahrobaei, and Haralick solved the conjugacy problem in certain groups via machine learning methods. These methods, improving the pre-existent machine learning and pattern recognition techniques for algorithmic problems in free groups, allow to find heuristically the conjugate of a pair of random elements of some groups. The groups considered are Baumslag–Solitar group and some non-metabelian generalisation of it, and non-virtually nilpotent polycyclic groups.

2.1.1. Cryptographic applications

Polycyclic groups have many applications in group-based cryptography, see GK16 for a complete survey. Such applications include the commutators key-exchange protocol based on the simultaneous conjugacy search problem and the subgroup membership search problem; the non-commutative Diffie–Hellman key exchange protocol based on the conjugacy search problem; the non-commutative ElGamal key-exchange based on the power conjugacy search problem proposed by Kahrobaei and Khan; a key-exchange using the subgroup membership search problem; an authentication scheme based on the twisted conjugacy problem; authentication schemes based on semigroup actions (such as the endomorphism and the isomorphism problem) and a secret sharing scheme using the fact that there is an efficient solution for the word problem.

Below we describe a non-commutative digital signature which was proposed in 2012 by Kahrobaei and Koupparis KK12 based on polycylcic groups.

Non-commutative digital signature. Let be an infinite polycyclic group, and consider two functions and as follows , which encodes elements of the group as binary strings, and , known as the collision-resistant hash function.

The functions and , and the group are public and the message is signed and verified as follows:

Key Generation: The signer first chooses an element , whose centralizer (the set of elements that commute with ) contains only the identity of and powers of . The private key is an element and , where is chosen to be highly composite. The public key is .

Signing Algorithm: To sign a message , the signer chooses a random element and a random factorization of , and computes the following, where denotes concatenation:

The signature and the message are then sent to the message recipient.

Verification: To verify, the recipient computes , and accepts the message as authentic if and only if the following equality holds: .

The security of the signature scheme is based on the collision resistance of the hash function and the hardness of the conjugacy search problem in in the platform group.

Multilinear maps. In the last decades, multilinear maps have attracted attention in cryptography. In 2003, Boneh and Silverberg proposed multilinear maps in cryptography, exploring in particular how to build these maps. In 2017 Mahalanobis and Shinde presented a novel bilinear cryptosystem in groups of nilpotency class 2. In order to explore more deeply these maps, Kahrobaei, Tortora, and Tota proposed multilinear cryptosystem using identities in nilpotent groups in 2019. Recently, Kahrobaei and Stanojkovski proposed pro- groups in general form for such maps and analyzed the security KS21.

In order to explain the aforementioned results, we give a couple of useful definitions. We first recall that given a group and a simple commutator of weight is defined recursively by the rules , and

if . Sometimes we will use the following shorthand notation

Let now be a positive integer and an arbitrary group. A map is said to be a multilinear map if for any and any we have

Moreover, we say that the map is non-degenerate if there exists such that .

If furthermore is a nilpotent group, there are additional properties for multilinear maps. So let be a nilpotent group of class and elements of . One can easily prove by induction on that for any the following identity holds:

Hence if is nilpotent, the map

is a multilinear map. In addition, if we fix , we can construct another multilinear map given by

If the multilinear map is non-degenerate, then one can propose multilinear cryptosystems using identities in nilpotent groups in multiparty key-exchange protocols, in which the security is based on the discrete logarithm problem. The protocol presented by Kahrobaei, Tortora, and Tota reads as follows.

Let be a positive integer, and suppose that the public group is nilpotent of class , but not -Engel. We recall that a group is an -Engel group if there exists such that , for all . Consider then users that wish to agree on a shared secret key. Each user selects a private integer , computes , and sends it to the other users. Then we are in the following situation:

The user computes .

For , the user computes .

The user computes .

Since the identity 1 holds in all nilpotent groups, all elements computed by the users are equal to

where is the shared key.

In KS21, Kahrobaei and Stanojkovski propose a new protocol employing multilinear maps for an arbitrary number of users. This protocol is a non-interactive key-exchange in which the users agree on a symmetric shared key without any interaction, and for this reason is said to be non-interactive. Note that one of the most known non-interactive key exchange schemes (NIKE) is the Diffie and Hellman key-exchange protocol over cyclic groups.

Let be an integer greater than 2, and let be a nilpotent group of nilpotency class . We set:

Public: .

Users: , who choose an integer .

Private keys: .

Public shared data: with and .

Shared secret key: , which can be computed from the shared data since the commutator is a multilinear map.

The security of the above protocol is based on the difficulty to recover the shared key. For a finite -group this can be reduced to solve the discrete logarithm problem in a cyclic group of order , which is known to be classically hard. We observe that the case already was analyzed by Mahalanobis and Schinde in 2017.

Motivated by the use of the protocol above in a more general context and for an arbitrary number of users, Kahrobaei and Stanojkovski in 2021 employed infinite pro- groups. More precisely, consider a non-nilpotent profinite -group with an integer. It is known that then has a finite quotient of nilpotency class and so, over , one can construct a key-exchange protocol between users. Kahrobaei and Stanojkovski proved that such a group exists and it can be used as a platform for an arbitrary number of users.

It is worth mentioning here the definition of the generalised discrete logarithm problem, as it is connected to the security of the aforementioned multilinear maps. Let be a finite group. Given , the discrete logarithm problem (DLP) is the problem to find whether there exists a positive integer such that . Notice that this is usually defined in the setting of cyclic groups because the Discrete Logarithm exists for all elements and all nontrivial bases. The DLP can be generalized to several components as follows. Let be a tuple of elements such that . Given , the generalised discrete logarithm problem of with respect to is to find such that can be written uniquely as

where for any .

In 2011 Sutherland presented a generic algorithm to compute Generalised Discrete Logarithms in every finite abelian -group by using some direct methods to compute a basis for Sut11. It is an interesting problem to find the complexity of this problem for any finite -group.

Semidirect product key-exchange protocol. Habeeb, Kahrobaei, Koupparis, Shpilrain in 2013 proposed a key-exchange protocol using semidirect product HKKS13. A few platforms have been proposed, for example, in KS16, free nilpotent -groups were proposed. Recently, Battarbee, Kahrobaei, Perret, and Shahandashti gave the first dedicated security analysis of the semidirect discrete logarithm problem. In particular, they provide a connection between the semidirect discrete logarithm problem and group actions, a context in which quantum subexponential algorithms are known to apply BKPS22.

Here we give general ideas of this protocol. Let be a (semi)group. An element is chosen and made public as well as an arbitrary automorphism (or an arbitrary endomorphism ). Bob chooses a private , while Alice chooses a private . Both Alice and Bob are going to work with elements of the form , where . Note that two elements of this form are multiplied as follows: .

Alice computes and sends only the first component of this pair to Bob. Thus, she sends to Bob only the element of the (semi)group .

Bob computes and sends only the first component of this pair to Alice. Thus, he sends to Alice only the element of the (semi)group .

Alice computes . Her key is now . Note that she does not actually “compute” because she does not know the automorphism , and also recall that it was not transmitted to her, but she does not need it to compute .

Bob computes . His key is now . Again, Bob does not actually “compute” because he does not know the automorphism .

Since , we should have , the shared secret key.

The proposed algorithmic problem on which the security of this scheme is based is a cousin of the computational Diffie–Hellman problem. There is no known reduction from this problem to the DLP.

2.2. Graph groups

Graph groups (also called partially commutative groups, semifree groups, right-angled Artin groups, or simply RAAGs in the literature), were defined by Baudisch (1977), as a kind of interpolation between free groups and and free abelian groups. They admit a presentation where the only relations are commutativity relations which are codified in a finite simplicial graph, see the definition below. The fact that these groups are defined by means of a graph implies that there is a tight connection between algorithmic graph theoretic problems and group theoretic problems for graph groups. Since the graph theoretic problems have been of central importance in complexity theory, it is natural to consider some of these graph theoretic problems via their equivalent formulation as group theoretic problems about graph groups.

In general, given a property of a graph, it is easy to figure out the corresponding group-theoretic property of the associated graph group, via the graph that defines it. However, given an intrinsic property of the graph group (i.e., not depending on any particular set of generators), it is usually hard to characterize the corresponding graph property, and not always possible. For example, if a graph is not connected it is nearly immediate that the associated graph group decomposes as a free product, but the reciprocal result is a highly nontrivial theorem. Since the eighties, an important line of research has been developed in order to model group-theoretic properties of graph groups in terms of properties of the graph.

The previous approach permits in particular to convert graph theoretic problems for finite graphs into group theoretic ones for graph groups. Motivated by the fact that some of these group theoretic problems can be used for cryptographic purposes, such as authentication schemes, secret sharing schemes, zero-knowledge proofs, hash functions and key-exchange protocols, Flores, Kahrobaei, and Koberda have considered these groups as a promising platform for several cryptographic schemes (see FKK19, FKK21a, FKK21b, FKK22). It is important, in this sense, that good knowledge of the group-theoretic structure of these groups (normal forms, centralizers, automorphisms, subgroups, etc.) makes their algorithmic properties very tractable.

Next we will define rigorously graph groups and describe some of their main features from the cryptographic point of view.

2.2.1. Main definitions

Here we define graph groups: Let be a finite simplicial graph. We write for the finite set of vertices and for the set of edges, viewed as unordered pairs of vertices. The graph group on is the group

In other words, is generated by the vertices of , and the only relations are given by commutation of adjacent vertices. For example, if is just an edge, then is , the free abelian group in two generators.

The previous presentation is frequently called a standard presentation of the graph group, and the generators the standard generators or Artin generators. The number of vertices of the graph is the rank of the group. It is clear by the definition that the graph determines the group, and by the work of Droms (1987), the converse is also true. In the following, given a graph , we will denote by is the associated graph group, and conversely, given a graph group , we will denote by its associated graph. We will always assume that the graphs that appear in this section are finite.

2.2.2. Algorithmic problems

Next we will comment on the main algorithmic problems in the context of graph groups, and the different solutions that have been given to them throughout the years.

Word problem. Servatius, using normal forms, gave in 1987 a first solution of the word problem for graph groups, although he paid no attention to the complexity of the construction of the normal forms. A bit later, Wrathall (1988) used good properties of a presentation of the monoid of positive words to prove that the word problem is solvable for graph groups in linear time. Expanding these methods, Liu–Wrathall–Zeger (1990) established that the generalised word problem (i.e., given two words and in the group, check if some power of is equal to some power of ) is also solvable in linear time, where the argument of linearity is the length of the product.

Conjugacy problem. The approaches just described by Servatius and Liu, Wrathall, and Zeger were also useful to prove respectively that the conjugacy problem for graph groups is solvable in linear time. More recently (2009), Crisp, Godelle, and Wiest use a version of the Viennot and pyramidal pilings for graph groups to construct a new normal form. In this way, they are able to prove that in fact the complexity of the conjugacy problem in this context is linear in terms of the sum of the lengths of the elements involved. The technique consists of constructing the normal forms out of the corresponding pilings, and comparing them. In this way these authors also prove the linearity of the conjugacy problem for an important family of subgroups of graph groups, namely fundamental groups of Haglund–Wise special (or virtually special) cube complexes. It is worth mentioning here that the richness of the subgroup structure of graph groups gives rise to finitely presented examples. In general, the corresponding problem is not solvable for subgroups of graph groups, not even if they are finitely generated. Bridson (2013) found a finite index subgroup of a graph group and a finitely generated free group such that the isomorphism problem is not solvable for the finitely presented subgroups of , and then for subgroups of , which is a graph group.

Subgroup isomorphism problem. Recall that the Subgroup isomorphism problem asks if given two groups and by presentations, can be embedded as a subgroup of or not. If and are graph groups given by standard presentations, a sufficient condition for to be a subgroup of is that the graph associated to is an induced subgraph of the graph associated to (i.e., a subgraph such that if and are vertices of and the edge belongs to , then it also belongs to ). It is known that this problem is NP-complete in general. However, in principle it would be possible to always find an embedding that does not involve the graph, as for example any embedding of free groups. But this is not possible: using the techniques of the previous paragraph, Bridson also proved that there is no general solution for the Subgroup isomorphism problem in graph groups.

Group homomorphism problem. The general version of the group homomorphism problem asks if given two groups and , is there a nontrivial homomorphism . For example, if is simple and does not contain a copy of , the answer is clearly negative. In turn, recall that given two graphs and , a homomorphism is an assignation that takes vertices to vertices and edges to edges. It is easy to see that not every homomorphism between graph groups can be realized as a homomorphism between the associated graphs, even if it takes standard generators to standard generators. For example, the first projection should be given by a homomorphism , which does not exist. Here denotes the complete graph in vertices, also called -clique.

Hence, from the point of view of cryptography, it is very useful to consider only the homomorphisms between two graph groups and with standard presentations that take standard generators of the first to standard generators of the second, and such that two commuting standard generators are taken to two different standard generators that commute. Now if we are restricted to this case, the problem of finding such a homomorphism between and is equivalent to the graph homomorphism problem for the associated graph, which is known to be an -complete coloring problem (Johnson, 1979).

The membership problem. Given a group and a subgroup and presentations of and , the membership problem consists in deciding if an element of belongs to . Recall that given a presentation of a group , the norm of an element of is defined as the minimal length of a word (in the given generators and their inverses) that represents . Then, given two elements and in the group, the distance between and is defined as the norm of . In this way a metric on is defined, called the word metric. For example, in the free group , the distance between and is . Now consider presentations of groups and , the associated word metrics and associated to the presentations and a monomorphism . Then is undistorted in if the embedding is a quasi-isometry, i.e. there exist constants , such that for every we have

Otherwise is said to be distorted in . For every , we can define the distortion function as .

It was proved by Flores, Kahrobaei, and Koberda FKK19 that if is a group where the word problem is solvable in at most exponential time, the membership problem is so for every finitely generated undistorted subgroup. In particular, we have seen above that the word problem is in fact linear for graph groups, so they fit in this framework. Moreover, in that paper it is shown that there exists a graph group and a subgroup isomorphic to the fundamental group of a compact surface such that a) its distortion function has exponential growth, and b) its membership problem is also solvable in at most exponential time (it could be even polynomial). On the contrary, Bridson has described examples of distorted subgroups of graph groups for which the membership problem remains unsolvable.

The geodesic problem. For a given presentation of a group , a word in the generators is said to be geodesic if its number of letters coincides with the length of the element of the group that it represents; in other words, it is a shortest word in these generators representing the element. There are several classical algorithmic problems involving geodesics and length. The geodesic problem is, given an element in a group , to find a geodesic word that represents the elements. The geodesic length problem consists in computing the length of an element in the group. There is a bounded version of the latter, where it is intended to determine for a natural if the length of an element is smaller or equal to . It is known that these three problems have the same complexity (as each of them is reducible to each other), and in the case of graph groups this complexity is polynomial by a result of Holt and Rees (2013).

The decomposition problem. Recall that given two graphs and , their join is the graph whose vertex set is and whose edges set is given by and all the possible edges that start in and end at . Then it is known (Servatius, 1989) that a graph can be decomposed as a nontrivial join if and only if the graph group decomposes as a nontrivial direct product. In FKK19 is described an algorithm (probably known previously) which decomposes any graph as a join of graphs which in turn cannot be further decomposed. This algorithm stops in polynomial time, and this proves that decomposing a group as a direct product of indecomposable subgroups can be also solved in polynomial time, provided we have an standard presentation of the group.

Hamiltonicity. Flores, Kahrobaei, and Koberda defined in FKK21b the concept of Hamiltonian vector space. Consider a triple where and are vector spaces over a field , an (anti-)symmetric bilinear pairing on . It is said that is a Hamiltonian vector space if whenever is a basis for then there is a permutation of elements such that for all , we have , . Given a graph group , the Hamiltonicity of the triple , where denotes the -th homology group of with coefficents in and denotes the cup product, is an invariant of the isomorphism type of the group. Then it is proved in the aforementioned paper that the fact that this vector space is Hamiltonian is equivalent to the Hamiltonicity (in the classical sense) of . Then, given a graph group , the problem of determining if is Hamiltonian is NP-complete. Observe that the definition of Hamiltonian vector space models algebraically the property of possessing a Hamiltonian cycle; an analogous result is valid, mutatis mutandis, when considering Hamiltonian paths instead of cycles.

2.2.3. Cryptographic applications

In this section we review several cryptographic applications of graph groups and protocols that have been developed out of them.

Secret sharing schemes. Based on previous work by Habeeb, Kahrobaei and Shpilrain and Shamir, Flores and Kahrobaei proposed in 2016 secret sharing schemes using graph groups, which rely on the fact that the word problem in these groups is solvable in linear time. To illustrate the ideas that are used, we describe one scheme of each type. We start with a sharing scheme, which uses decisively that the word problem can be solved in linear time in graph groups. The idea of the scheme is that the dealer distributes a -vector of 0’s and 1’s among participants, making sure that the vector can only be totally reconstructed if all participants share their information.

So let us describe the scheme. First, a set of public generators is selected.

Each participant receives secretly from the dealer a set of commutators of the generators in (and their inverses), so the participant possesses the graph group

The vector is written by the dealer as a 2 sum of <