12 Further Applications Using Group Theory

12.1 Finitely Presented Groups and Cryptography

In the previous several chapters we have seen how group theory, specifically the combinatorial group theory of finitely presented groups, can be utilized in a cryptographic setting. The basic idea is that a finitely presented group can be described by a finite amount of data. This provides techniques to enormously compress and hide information. The body of knowledge, learned in more than 150 years of intense study of finitely presented groups, provides a far reaching tool when applied to cryptology.

Numbers and words are often used as a means of identification, authorization, access to information, record keeping, the control of devices and so on. They are translated into bit strings without any structure. The replacement of these numbers and words by group-theoretic objects, such as finitely presented groups, their subgroups, their elements and the maps between them, can play a role in computer science. These algebraic objects have well-defined structures, and a huge body of knowledge exists, which makes it possible to easily design all manner of objects to fit a variety of purposes, not easily done solely with bit strings.

In the case of a group defined by finitely many relations, a few symbols and a few equations can be used to encode in many very different ways an infinite amount of information (see Chapter 9 for a discussion of finitely presented groups). Indeed, finite presentations provide a concrete way of defining infinite sets with many properties, the presence or absence of which can be used to allow for the passage or otherwise of information, in a manner analogous to gates in networks. These sets inherit a group structure, and as a consequence, such gates can be controlled dynamically, and opening or closing them, can be realized by answers to an infinite number of questions which can be arranged in such a way as to be arbitrarily difficult to answer. Thus the use of finite group presentations have the potential to allow secure access and control of devices and to provide new approaches to cryptography, to authentication, to identification and authorization and to record-keeping.

This entire chapter is somewhat speculative. The objective is to suggest additional uses of group theory, some complicated and some simple, with most of the details omitted. Whether implementation of the suggestions that follow will lead to secure group-theoretic alternatives to some existing protocols is unclear. For example, we will describe a far-reaching extension of the permission mechanisms in the Unix operating system for controlling access to files and devices partly based on what we term the entry control group, which we will discuss next.

12.2 Group Theory for Access Control

In data base management, changing access to files can be time consuming and difficult. Here we suggest a novel approach to this by using a single finitely presented group that we call an entry control group to control and effect such access. This can be done in a reasonably secure manner. The discussion that follows is a very special instance of a general entry control group, and can readily be adjusted, and be used, in a number of different ways which take into account limiting access in any manner deemed useful. We note that in earlier writings on these ideas the entry control group was called an access control group. However,the terms access control group has an older, and more established, meaning in secret sharing (see Chapter 4), so the terminology entry control group was substituted.

Wreath Products

Our first example of an entry control group depends on a group theoretic construction called a wreath product of two groups A and B. This is a specialized product of two groups, based on a semidirect product and has been extensively studied. Theoretically, wreath products provide a method to construct many interesting examples of groups.

Given two groups A and B, there exist two variations of the wreath product: the unrestricted wreath product and the restricted wreath product. To begin we briefly describe this construction. First we define a semidirect product. If G is a group and A and B are subgroups of G, then G is the semidirect product of A by B if A is a normal subgroup and every element of G can be written in a unique way as a product ab, with a € A and b € B.

Definition 12.2.1. Let A and B be groups and we suppose that B acts on A, that is, each element of B acts as a homomorphism on A.

Let K be the direct product of copies of A indexed by B. The elements of K are then arbitrary sequences (a_b) of elements of A indexed by B with component wise multiplication. Then the action of B on A extends in a natural way to an action of B on the group K by b^)) = (ab-−b).

Then the unrestricted wreath product, A i B,of A by B, is the semidirect product of K by B. The subgroup K of A i B is called the base of the wreath product.

The restricted wreath product, A i B, is constructed in the same way as the unrestricted wreath product except that the direct sum of copies of A indexed by B is used as the base of the wreath product. In this case the elements of K are sequences of elements in A, indexed by B, of which all but finitely many are the identity element of A.

The wreath product construction plays an important role in the structure theory of permutation groups. The structure of the wreath product A i B depends on the action of B on A and on whether it is the restricted or unrestricted wreath product. Further the restricted wreath product is always a subgroup of the unrestricted wreath product.

There is a universal embedding theorem which states that if a group G is an extension of A by B, that is, A is a normal subgroup of G with G/A isomorphic to B then there exists a subgroup of the unrestricted wreath product of A by B which is isomorphic to G.

Access Control to Files

We now exhibit how the wreath product construction can be utilized to define an entry control group. For more material on the basic combinatorial group theory see Chapter 9.

To start, let F be the free group on a, x, y, let S be the infinite cyclic group on s and let

W = F ≀ S

be the wreath product of F and the infinite cyclic group S. Furthermore, let

V₁ = (F, F^s, s²), V₂ = (F, F^s, s³).

Put

Form the HNN extension H of W with stable letter t and

Then H can be presented on the generators

a, x, y, s, t

and defining relations

The reader can take this as the definition of the group H which is to be our entry control group.

Suppose now that we have data consisting of a number of files labelled by the positive integers i = 1,… where the i-th file is named E_i. The contents of E_i is recorded in the free group F_i, generated by the elements

Each file E_i then defines a free subgroup of the ambient free group.

The users of the database are arranged in order of the times at which they subscribe to the database, as

U₁…, Ui,….

Each user U_i is assigned an element u(i) € H. U_i is to be permitted access to the files in

E_t,…,E_im,

if and only if u(i) does not commute with any one of the subgroups E, ,…, E, . In order to effect this we set u(i) = 1 if U, is not to have access to any of the files in the database. Otherwise we put

u_i = a_i1 … a_im

which ensures that u(i) has access to the files in E, ,…, E, . This scheme allows then for easy changes of permission to access the files in the database being set up. This is a particularly important aspect of the design of the entry control group.

The Entry Control Group Security

Later in this chapter we introduce what we term social security groups. These are complicated finitely presented groups. They are chosen in such a way to ensure that it is difficult to answer questions about them without additional information, which is kept private unless needed. If the free group F in the description above of the entry control group is replaced by such a social security group, say X, then access to any of files which are now residing in one of the conjugates w^-1Xw of X is controlled by requiring that various questions about w have to have the right answers. This ensures that access to the database is secure. This follows the security provisions set out for the group theoretic password security described in Section 10.6.

Entry Permissions in Operating Systems

In many operating systems and in particular in the Unix operating system, it is usually the case to assign so-called permissions to various files to the users of the system which allow the files to be read, written to and executed as appropriate, labelled simply as rwx. Our Access Control Group is enormously flexible allowing for us to designate files not only with all manner of access, but also degrees of access for various users. For example, if a user wants to use a 3D printer, which is very expensive to operate, that user must be given permission to do so and the limitations of such use both partial and total can also be controlled by an appropriate entry control group.

Access Control for Websites

The idea here is to show how the entry control group can enable Alice with the ability to access any of the websites that she is interested in without having to remember passwords. We again use the entry control group H.

List the websites that Alice is interested in as W₁,…, W_m together with the passwords as required. Install the information about W,, its URL and the password that Alice wants to use to gain access. W_{ is in a non-trivial subgroup E, of F, generated by a,. For each of these websites, say W^,…, W_t , assign what we might term the website locator acceptor

W_A = a_i1 …a_im.

Notice that w_A does not commute with Ej only if j € {1₁,…, i_m} which then provides Alice access to any one of the web sites she is interested in. Moreover if we want to ensure that Alice does not want to access any particular site say W_i for any reason she changes her website locator by omitting ij. Of course this idea can be varied to accommodate any given set of conditions. Computations can be carried out quickly inside groups like H.

12.3 Public Key Control Groups

In this section we show how to use the complexity of a finitely presented group as the basis for a new public key protocol. In the next section we do the same using the insolvability of Hilbert’s Tenth Problem.

We describe first a complicated finitely presented group H which we use as the basis for a new public key cryptosystem. Such groups are plentiful and we will give an additional example later to justify this claim.

In order to define H we repeat for ease of understanding, the usual notation for commutators and conjugation:

The group H is an amalgamated product of two finitely presented groups A and B given by:

The subgroups U and V to be amalgamated are free and given by:

H then is defined as follows:

It follows that H is a 5-generator, 6 relator group.

Now let H₀ and H₁ be copies of H, with the elements in H₀ corresponding to a and h denoted by a₀, h₀ and so on. Let D be the direct product of H₀ and H₁:

D = H₀ × H₁.

We now use von Dyck’s Lemma (see [MKS]) to show that D is a quotient of H. With this in mind we define a map $ from the generators of H into D as follows:

It is clear that the relations not involving h are preserved. We have to check that the remaining equations are also preserved, and this is straightforward. It remains to prove that the subgroup E generated by images of the generators under $ is all of D. To this end, observe first that s₀ € E:

It follows then also that t₁ € E. Consequently

Additionally

Again it follows that a₁ € E as usual. Finally hjh € E because a € E which implies that

and so also h₁ € E. This ensures that E = D and so D is a quotient of H,which completes the claim.

We show how the construction of H enables us to use this group as the basis of a public key cryptosystem. Suppose that F is a free group, freely generated by 2 elements. It follows that F then contains a free subgroup freely generated by 256 generators. If we put these generators in a one-to-one correspondence with the 256 ascii characters, then every message can be represented by the appropriate a product of these generators, that is, as an element of F. It follows that if a given group contains a non-abelian free subgroup, then we can encode messages as elements in that group.

In order to take advantage of the properties of the group H we make use of the vertices of a rooted binary tree T. We denote the root of the tree by 0. There are two edges emanating out of a vertex v. We denote the terminus of one of these edges by 0v and the terminus of the other vertex by 1v. Now we put a copy H_v of H on each vertex v. Then there is a homomorphism $_v of H_v onto the direct product H_0v x H_1v of H_0v and H_1v. Let n_0v be the projection of H_v onto H_0v and n_1v be the projection of H_v onto H_1v. The composition y_0v = $_vn_0v maps H_v onto H_0v and the composition y_1v = $_vn_1v maps H_v onto H_1v. We now attach to the two edges 0v and 1v the respective homomorphisms y_0v and y_1v. For each pathp emanating out of 0 and ending up at the vertex v we can compose the homomorphisms attached to these edges which results in a homomorphism A_v from H₀ to H_v.

Now if p_v is a path in the binary tree from the root vertex 0 to the vertex v, choose a free subgroup F_v of H_v of rank 256. Choose for each of the generators of F_v a pre-image under A_v in H₀. So if Bob wants to send a message to Alice, he encodes it as a product P of these pre-images. Alice then applies A_v to P and is able to decode P in H_v. The point here is that decoding a message from Bob requires knowledge of the path p_v which is known only to Alice. This is a public key protocol.

The discussion above has many variations. Each such variation gives rise to a new public key protocol. The interested reader can supply those variations as desired. It suffices here to roughly describe the bare bones of such a variation. To this end, in place of the group H above we can choose a non-hopfian group H, that is, a group that is isomorphic to one of its proper quotients, for example, H = (a, b; a^-1b²a = b³).

Let T be a rooted binary tree with initial vertex or root v₀. Assign to each vertex in T a vertex group which is a copy of H and at each edge e an epimorphism of the copy of H at the origin of e to the copy of H at terminus of e with a non-trivial kernel. Let ^ be a random walk in T starting at v₀ and ending say at v’. Let p^ be the composition of the epimorphisms on the edges that comprise the paths constituting ^ .So ^ is a homomorphism of the copy of H at v₀ to the copy of H at v’. Let be the kernel of this homomorphism. Choose a pair of generators, say x’, y’ of a free subgroup of N^ and let x, y be respectively pre-images of x’, y’. Now suppose that Alice wants Bob to send her a message. So she sends Bob the elements x and y and Bob sends her a message, that is, a word w in x and y in the given generators of the copy of H at v₀. Alice then computes the image w’ of w under the homomorphism p^ and rewrites it as a word in x’, y’. This then is a public key protocol - only Alice is in possession of the random walk ^ which ensures the security of this protocol.

12.4 Diophantine Control Security groups

We discuss next some matrix groups which we will refer to as Diophantine Security Control Groups. They can be used to give rise to some additional public key cryptosystems. They are based on the complexity of finding integral solutions of Diophantine equations.

Diophantine equations

Y. Matiyasevich proved that there is no algorithm which determines whether any Diophantine equation has a zero. The objective of this section is to take advantage of this theorem of Matiyasevich to concoct some public key cryptosystems. These crypto systems make use of some of the properties of the group GL(2, R) of invertible 2 x 2 matrices over suitably chosen unitary rings. Each of the groups considered here contains a free subgroup F of rank two and therefore a free subgroup freely generated by 256 elements. If we put these elements in a one-to-one correspondence with the 256 ascii characters as usual, then this allows one to uniquely encrypt any message as a word in these generators and hence as a matrix over R. This will allows us to take advantage of two properties of r = PSL(2, Z), the group of 2 x 2 projective integral matrices of determinant 1.

The first is that r is finitely presented:

The elements s and t can be identified with the matrices

Using this description of r it is not hard to show, as is well known, that

freely generate a free subgroup H of r. Since a non-abelian free group contains subgroups of every finite rank, H contains a subgroup L of rank 256 which can be put into a one-to-one correspondence with the 256 ascii symbols. This allows us to represent any document or message uniquely as a word in the generators of L, and hence, on multiplying the matrices together, as an integral matrix of determinant 1.

The second observation needed here is that there is an algorithm to rewrite any T € PSL(2, Z) in terms of s and t. This shows that this protocol for encrypting messages by integral matrices is not secure as it stands. We shall discuss here some variations that make use of the negative solution of Hilbert’s tenth problem, as well as the existence of finitely presented groups whose word problems can be made arbitrarily complicated. These variations do appear to lead to protocols which are secure.

Augmented Rings and Specializations of Matrices

We begin this section with a definition.

Definition 12.4.1. An augmented ring is a unitary ring R together with a unitary homomorphism

So a ring R with a multiplicative identity 1 becomes an augmented ring if it contains an ideal I, the augmentation ideal, and R/I is isomorphic to . It follows that we can view as a subring of R and that

We shall need two such augmented rings, Z[x₁,…, x_n] the ring of polynomials in any number of variables and Z[G] the integral group ring of a group G.

The following lemma, and its corollaries, allow one to connect such augmented rings to free groups and then to an application of Hilbert’s tenth problem.

Lemma 12.4.2. Let R and S be unitary rings and let $ be a homomorphism from R to S. If GL(m, R) is the group of all invertible m x m matrices over R, then $ induces a homomorphism $ * of GL(m, R) into GL(m, S).

Corollary 12.4.3. If R is an augmented ring with augmentation e, then the augmentation e from Rto Z induces a homomorphism from GL(n, R) to GL(n, Z).

Corollary 12.4.4. Suppose that $ is a unitary homomorphism of the unitary ring R into the unitary ring S and that X is a subset of GL(m, R). If $ *(X) freely generates a free subgroup of GL(m, S), then X freely generates a free subgroup of GL(m, R).

Finally, we have the following key consequence of the corollary.

Lemma 12.4.5. Let R be an augmented ring and r₁, r₂, r₃, r₄, r₅, r₆, r₇, r₈ € R. Furthermore, let

If e(r1) = 1, e(r2) = 2, e^) = 0, e(r₄) = 1, e(^) = 1, efo) = 0, e^) = 2, efrs) = 1, and if X and Y are invertible, then they freely generate a free group.

Adapting Hilbert’s Tenth Problem to Cryptography

As already noted, Yuri Matiyasevich proved that there is no algorithm which determines whether or not an integral polynomial in any number of variables has a zero. It follows that there exist polynomials whose zeros are arbitrarily large in absolute value.

In order to make use of Matiyasevich’s theorem consider instead the matrices

and

Here the f, (i = 1,…, 8) are integral polynomials in the commuting variables x₁,…, x_n. Now suppose that there is an augmentation e from k = Z[x₁,…, x_n] onto Z such that

Notice that e induces a homomorphism e* from GL(2, k) into GL(2, Z) which maps A to a and B to b.So A and B freely generate a free group in GL(2, k). Now let H be a free subgroup of rank 256 of (a, b) freely generated by

h₁,…,h₂₅₆

and choose H, € GL(2, k) to be a pre-image of h, in GL(2, k). Then

K = (H₁,…,H₂₅₆)

is a free group of rank 256 and so any message M can be encrypted in H and send across as a matrix of polynomials. To decrypt M, compute its image e*(M) under e*. Now e*(M) is an integral matrix and is an element of H. So it can be decomposed as a product

p = p(h₁,…,h₂₅₆)

of the matrices h₁,…, h₂₅₆. Then the corresponding product

P = p(H₁,…,H₂₅₆)

translates into the original message M.

Public Key Cryptography and Polynomial Equations

The discussion above translates into a public key cryptographic protocol as follows. Bob encodes a message using X and Y. Alice then uses the secret substitution for the variables to convert the matrices X and Y into a and b respectively. Then she uses the algorithm mentioned previously to decomposes the resultant integral matrix into the unique word in a and b.Replacing a by X and b by Y allows Alice to obtain the message sent by Bob.

We make this precise in a system we call AMC1.

The Cryptosystem AMC1

The discussion above can be extended in several ways. We choose here to take an approach that makes use of the integral group ring Z[G] of a group G. Z[G] is an augmented ring with augmentation

defined by

where here a_i ∈ .,g_i ∈ G. The kernel I(G) of ..consists of the elements

with coefficient sum 0, that is,

The point is that, if G is any group, in particular one given by a finite presentation, then the same approach used in working with polynomials in many variables can be carried out using the elements of Z[G] instead, which appears to have some advantages due to the fact that most problems about groups given by a finite presentation are algorithmically undecidable. A basic observation then that comes out of this approach and which can be used to good effect to encode information in a seemingly secure manner, is the following

Lemma 12.4.6. Let G be a group and let

and

be elements in GL(2, Z[G]). Further suppose that

Notice that e induces a homomorphism e* from GL(2, Z[G]) into GL(2, Z) which maps A to a and B to b, where again

Then A and B freely generate a free group in GL(2, Z[G]).

The following corollary is an immediate consequence of this lemma.

Corollary 12.4.7. Letg and h be elements of the group G. Then the matrices

and

freely generate a free subgroup of GL(2, Z[Gj).

Let G be a torsion-free group given by a finite presentation on the finite set S. Let R = Z[y] be the group ring of the group G over the ring of integral polynomials in a single variable y. Then we have the following simple lemma:

Lemma 12.4.8. Letg € G. Then the element x = y(1 − g) is transcendental, that is, is not the root of an integral polynomial f (x) ifg = 1.

The subring A of R, generated by y and g, is simply a polynomial ring over Z, in the variables y and g. The assertion in the lemma follows from this observation.

Now let w be a word in the generators S of G. We now introduce two matrices A(w) and B(w) in GL(2, R), the group of 2 x 2 matrices over R:

Observe that A(w) and B(w) freely generate a free group if and only if w = 1. Now form 256 words W_{ in A(w) and B(w), for instance the conjugates of B(w) by A(w)’ with i ranging from 1 to 256. As usual a message M can be encoded as a word in the W, and thence as a matrix M(W) in GL(2, R). This matrix can be decoded in what is now the usual way since it can be viewed as a matrix over an augmented ring. Here the augmented ring is a polynomial ring in two variables over Z. Now decoding the message requires determining whether or not w = 1 in S. This leads to an array of protocols the decoding of which can be made arbitrarily hard and indeed if G is a group with a complicated word problem, decoding of the messages becomes arbitrarily complicated unless w =1.

12.5 The Social Security Control Groups

The Social Security Number (SSN) was introduced in 1936 to be used solely for Social Security programs. It is used for driver’s licences, credit cards, banking accounts, employee files, medical records and a host of electronic transactions. Seemingly little has been done to safeguard the SSN. One of the consequences is that identity theft has increased. Computer usage also carries with it problems, with the associated login procedures protected by user-selected passwords, which are poorly chosen such as names of pets or loved ones. Many commercial electronic transactions, such as credit card purchases, banking and so on are usually protected by powerful cryptographic protocols. These include algorithms such as RSA, DES and AES. The security of such algorithms often rests upon the difficulty involved in carrying out certain computations that involve finite collections of numbers whose choice is dictated by the existence of very large primes. These finite collections can be made into finite abelian groups. It is the complexity of these finite abelian groups that make such protocols secure, although this has never been proved. Recently Agrawal, Kayal and Saxena (see [AKS]) showed that it is possible to determine whether a number is prime in a relatively uncomplicated way (technically speaking, they obtained a polynomial-time algorithm to determine primality). This raises the possibility that protocols that rest on products of two very large primes, the basis for the thinking that the use of finite abelian groups leads to secure public key cryptosystems, may indeed not be the case. Quantum computers appear also to be a threat. This raises concerns on the reliance on, on the one hand, a single number, the SSN and on the other, the complexity of a finite structure, a finite abelian group, for identification, for the safekeeping of records and for secure electronic communication. As we have already seen, finite abelian groups are very special instances of finitely presented groups, which we have already discussed.

These finitely presented groups are usually infinite. They have been intensively studied for more than 150 years and many questions about them have been proved to be very difficult, indeed at times impossible, to answer. This suggests that finitely presented groups can be made the basis of challenge-response protocols which lead naturally to a new means of identification. This suggests the possibility of replacing the SSN by a finitely presented group, here termed a Social Security Control Group or SSCG. One can extend the use of such finitely presented groups to, for example, assigning Bank Security Control Groups (BSCGs) to banks, giving rise to an entire family of groups, collectively referred to as XSCGs. The extraordinary complexity of these groups leads to new methods of encryption and by using different aspects of them making their use more secure.

We have already discussed the possible uses of finitely presented groups. The possibility of such usage touches on almost every aspect of electronic communication and identification. Not only is there a possibility of the SSCGs providing a more secure means of identification which can help to prevent identity theft, they might be useful also as universal passwords in a variety of other ways. We will discuss this further in this chapter. They can also be used to help make various hand-held such as mobile phones more secure. In addition, the algebraic, mathematical nature of an XSCG makes it possible to encode information inside the group itself, resulting in a compartmentalization of information and a means of verifying that their use is legitimate. In this way different parties, such as credit card companies, banks, HMOs and merchants, will have access only to specific, small areas of each XSG, set aside for each of them. This will enhance security and help to prevent theft. Even if one part of an XSCG is compromised, the entire group remains outside the reach of an attacker because of this compartmentalization.

It must be pointed out that buffer overflows often make it possible for successful attacks on machines servicing the electronic highway. This problem has begun to be handled and will not be discussed here.

The Complexity of Finitely Presented Groups

As we have seen throughout this book, cryptographic protocols, especially public key protocols, are based on hard to solve problems. This becomes especially relevant in discussing finitely presented groups where even what might seem like straightforward questions in group theory frequently turn out to be algorithmically unsolvable.

We give some examples, some of which we have examined earlier.

(1)  There is no algorithm which decides whether or not any pair of finitely presented groups are isomorphic. We saw this as the isomorphism problem.

(2)  There is no algorithm that decides, for example, whether or not a finitely presented group is trivial, finite or abelian.

(3)  There is no algorithm that decides, for example, whether or not in a given finitely presented group two elements are conjugate. This is known as the conjugacy problem and was used in conjunction with the Ko-Lee encryption protocol.

(4)  There are finitely presented groups such that there is no algorithm that decides whether or not any word in the generators of the group is equal to the identity. This was known as the word problem.

(5)  There are finitely presented groups G such that there is no algorithm that can decide whether or not a given finite subset of G generates G (see Miller [Mil] for a discussion of the algorithmic unsolvability of many questions about groups and an explanation, if needed as to the terms used here).

Each finitely presented group G comes with a description which takes the form (see Chapter 9)

This notation is shorthand for expressing G as a factor group of the free group F on a₁,...,a_m by the smallest normal subgroup N of F containing the elements r₁ ,...,r_n. In other words G is given in terms of the isomorphism

G = F/N.

Notice that N consists of all products of the elements of R = {r₁,..., r_n}, their inverses and their conjugates. N is often denoted by writing N = ((R))_F and as such is referred to as the normal closure of R. As already noted finitely presented groups are described by a finite amount of data. This data then can hide an immense amount of information. It is this facet of finitely presented groups that will be taken advantage of here. To give one further illustration of how this comes into play, if a word w = x₁ … x_n is a product of the aj and their inverses in which consecutive terms are not inverses and if w € N, then it can be expressed as a product of conjugates f ^-1rf of the elements r € R and their inverses. If one now considers all such words w of length at most n in N, then the minimum number of conjugates required to express them gives rise to a function $ (n), termed the isoperimetric function of the group G = F/N. It provides, in a sense, a measure of the way in which N is contained in F. It is possible to show that these functions can be arbitrarily complicated (see Birget, Olshanskii, Rips and Sapir [BORS]). Indeed they need not even be computable. This property can be used to concoct some challenge responses which give rise to functions which can be used as the basis for various cryptographic protocols. However we will not develop this further. We note that the work of Kapovich, Myasnikov, Schupp and Shpilrain (see [MSU1]) on the average-case complexity of questions in group theory indicates that if we are to take advantage of the complexity of finitely presented groups by asking questions about their elements, their subgroups and the homomorphisms between them, care must be taken to choose such questions carefully.

Security Control Groups

Group theory lends itself to the design of secure web-based transactions. The general idea is to use group-theoretical objects, their properties, and questions about them, as the basis for a challenge response authentication protocol leading to secure electronic communication and transactions. The questions that must be answered before communication is allowed, generally need some group-theoretical software packages such as GAP, MAGMA or MAGNUS to provide answers to such questions. Here we return to the idea of using a finitely presented group, which we term in the case of a replacement of the Social Security Number, a Social Security Control Group. This can be used not only as a means of identification, but as a flexible storage facility. It can be used as a template for other security groups. The construction of the Access Control needs to be kept in mind as some its features can be taken advantage of here. This SSCG is typical of the security control groups that we are going to use in discussing one of the avenues to follow in applying group theory to cryptography.

A Social Security Control Group

Although it is not clear how to choose a SSCG, we will discuss a possible choice here and indicate how it has the potential of satisfying many of the criteria needed if it is to be used as a replacement for the Social Security Number.

To this end, let X be a person who already has a social security number. Further suppose that the social security number for X is v_X = n_x … n₉, where the digits n lie between 0 and 9. From this we will assign to X a SSCG a(X) = a(v_X) which we will define in the course of the discussion that follows. Such an SSCG can be adapted for use in a variety of other ways and we will discuss this later in this chapter. A key subgroup of this selection of an SSCG is a group constructed many years ago by Graham Higman and Bernhard Neumann and communicated to us by Chuck Miller.

A Finitely Presented Group Γ that Contains a Copy of Every Finite Group

The following construction gives an embedding of the group $ of finitary permutations on a countable set into a finitely presented group r. For group theoretical information in this section we refer to [Rot].

Let Q = Z u {to} and let t, = (i to) be the transposition which interchanges i and to. These t, in fact generate the group $ of all permutations of Q with finite support. Moreover $ can be presented on these generators by the defining relations:

for all i, j, k which are all pairwise different. Note that $ is locally finite and contains a copy of every finite group.

$ can be embedded in a finitely generated group which is the HNN-extension obtained by introducing a new generator s to $ together with the defining relations:

s^-−t-s = t₊1.

Viewing the elements t, as an infinite sequence

one can also consider the group generated by the subsequence of the t,’s obtained by leaving out every fourth generator:

This deleted sequence in fact generates a group isomorphic to that generated by the entire sequence.

The sequence of all t_i splits into 3 orbits under the action of s³ while the subsequence obtained by omitting every fourth t, splits into 3 orbits under s⁴. So form a further HNN-extension r obtained by introducing a further generator u together with the defining relations:

The resulting group r is generated by u, s, t₀, t₁, t₂, t₃ and, as will be shown below, can be presented using only finitely many of the relations involving the t_i because conjugation by the element u expands small indices to larger indices.

An explicit finite presentation of this group r on a convenient set of generators is as follows:

Generators:

u, s, t₀, t₁, t₂, t₃.

Defining relations:

The result we establish is the following:

Lemma 12.5.1. The map t, s^-it₀sⁱ embeds $ into the finitely presented group r.

In view of the above discussion it only remains to see that if we introduce the abbreviation t, = s~^lt₀s^l (which is compatible with the first set of defining of relations of r), then all of the previous relations follow from these.

First, the following calculation shows that the relations between u and the t,’s hold: u^-1t_3i+_eu = u^-1s^-3!t_es^3!u = s^-4,u^-1t_eus^4! = s^-4,t_es⁴’ = t_4i+_e for e = 1,2,3. Now t^f = 1 for all i since t^f = 1 so the first collection of t, relations hold.

In the calculations that follow it will be convenient to use the notation y ~_x z to mean that y is conjugate to z by the element x, that is x^-1yx = z.

Next we prove by induction that (t₀t_;)³ = 1 for all j > 1. For 1 < j < 3 these are among the given relations for G. So suppose inductively these relations have been deduced for indices smaller than j. If j = 4m + d where m > 1 and 0 < d < 2 then in G we have

where the last equality follows from the induction hypothesis. If j = 4m + 3 where m > 1 then in G

where the last equality follows from the induction hypothesis. By induction this establishes these relations for all j. But now by conjugating by a suitable power of s and taking a cyclic permutation if required it follows that (t,tj)³ = 1 for all i = j.

Lastly we must show (t_it_;t_it_k)² = 1 for all i, j, k all pairwise different. Consider the case i < j and i < k. For this case, after conjugating by s^-! and relabeling it suffices to show that (t₀t_;t₀t_k)² = 1 for all positive j = k. This we do by induction on the sum j + k. For 1 < j, k < 3 the desired relations are among the given relations for G. Inductively assume the desired relations have been established for indices with smaller sum. Now we may suppose that either j > 4or k > 4 and write j = 4m + d, k = 4n + e where

In case 0 < d, e < 3 we have the following computation in G :

by the induction hypothesis. Next consider the case e = 3. If d = 0 or d =1 then

by the induction hypothesis. If d = 2 or d =3 then

by the induction hypothesis.

The case d =3 and 0 < e < 3 follows by the analogous argument.

Finally, the cases in which j (respectively k) is the smallest of the three indices are dealt with by an entirely analogous argument.

A possible candidate for a Social Security Control Group

We now form the direct product

So (x, y; > is the free group on x and y and (u, v; v^-1u²v = u^v(X)> is the so-called group BS(2, v(X)) groups. The Social Security Administration has a copy of a(X) and the software needed to answer questions about a(X). When an entity attempts to impersonate X, the SSAA sends questions to the impersonator I to be answered. In addition previous communications with the person I are recorded in the file located in the subgroup F^a(I) and these answers have to be answered by I. This makes it impossible for I to access any records off X. If there is a break in of the system permissions are easily altered in accordance with the means provided by the Access Control Group. We shall not go in to the questions that may be asked by an imposter, but the very nature of the SSCG makes such questions easy to generate and easy to answer given enough information.

12.6 Further Extensions of Diffie-Hellman and RSA

An XSG-version of Diffie-Hellman

The XSGs that we have in mind all contain a variety of subgroups which lie partly in the infinitary symmetric group and partly outside. In particular they all contain a finitely generated non-trivial subgroup C and a second finitely generated abelian subgroup D, given by finite presentations generators s, t, u, v and a free abelian subgroup A of infinite rank. We will think of these subgroups as public. However the structure of the groups that they generate is hidden inside the XSG’s that contain them. Alice initiates contact with Bob with the aid of the challenge-response protocol discussed previously. She then selects a non-trivial word w = w(s, t) in s and t. Then she randomly chooses h₁, h₂, a € A and sends Bob h₁wh₂.

RSA in an appropriate ring

Let h be a large integer and let A be the quotient ring of the power series ring over the integers in the non-commuting variables x₁,...,x_m obtained on adding the relations x^h = 0 for j = 1,..., m. The power series ring, without any of these relations, is public like the product n = pq above, which defines the ring Z_n of integers, modulo n. The integer h is kept secret and can be viewed as the counterpart to the factorization of n in the description of RSA. The counterpart to e is an element of A chosen so that it has a multiplicative inverse in A. This inverse cannot be found without knowledge of h, which is chosen very large. Plaintext is encoded as a sum t of monomials in the xj and sent out as te. The recipient can decode the message by computing (te)e^-1 = t. The strength of RSA lies in the difficulty of finding inverses which in turn relies upon integer factorization. In these ring-theoretic settings, finding inverses is even more difficult particularly when non-commuting variables are involved.

12.7 Exercises

12.1  Let M be the modular group PSL(2, Z). This has a group presentation

where

Let

We show that there is an algorithm based on the Euclidean algorithm which given a projective integral matrix T can rewrite it in terms of the standard generators x, y. Let

be a matrix in M.

(a)  Show that

and

(b)  Show that the following algorithm then expresses the matrix T as word W(a, t). Then using that t = xy we get T expressed as a word W₁(x, y) in the standard generators x, y.
Multiplying on the left by a and then by an appropriate t^k we can make the lower left entry positive and smaller. Continuing we get eventually

where e = 1 or 0. Since = 1 this implies that the right hand side

12.2  Let T = ±( ). Use the algorithm from the previous problem to express T as a word in the generators x, y.

12.3  Use the presentation of the modular group M = (x, y;x² = y³ = 1) to show that any element of order 2 must be conjugate within M to x and any element of order 3 must be conjugate within M to either y or y².

12.4  Let A = ± (Cd) be an element of order 2 in the modular group PSL(2, Z). Show that

(a)  a + d =0,

(b)  A is conjugate in PSL(2, Z) to the element S = ±( -−0).

12.5  Let n €N. Show that n = x² + y² for some x, y € Z if -− is a quadratic residue modulo n. (Hint: Consider elements of order two and hence trace zero in the modular group.)

12.6  Let n €N. Show that if n = x² + y² for some x, y €Z then -− is a quadratic residue modulo n. (Hint: Again consider elements of order two and hence trace zero in the modular group.)

12.7  Show that the monoid SL(2, N) is freely generated by the two matrices

12.8  Let W = (^a1 C4 ) € SL(2, N). From the previous problem, W can be expressed as a word in T, U. Let I = l(w) be the length of W as a word in T and U. Show that a_t < f_e+₁ wheref_l+₁ is the I + 1^st Fibonacci number. As usual f₀ = 0, f₁ = 1 and fn+1 = ^fn + ^fn-− ^{for n} ^ ¹

12.9  The lamplighter group L is given by the presentation

where n €Z. Show that L is the restricted wreath product Z₂ i Z.

12.10  Prove Lemma 12.4.5.

12.11  Show that ±( 01) and ±( f 1) freely generate a free subgroup of PSL(2, Z).