B R A I D G R O U P S , A R T I N G R O U P S A N D T H E I R A P P L I C A T I O N S I N C R Y P T O G R A P H Y by C A T H E R I N E W E B S T E R B.Sc.(Hons) University of Leeds, 1997 A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F M A S T E R O F S C I E N C E in T H E F A C U L T Y O F G R A D U A T E S T U D I E S Department of Mathematics We accept this thesis as conforming t^o the\^e|[uire9) standard T H E U N I V E R S I T Y O F B R I T I S H C O L U M B I A May 2003 © Catherine Webster 2003 i. In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of 'MAJ H£Mf\1 \CS The University of British Columbia Vancouver, Canada Date DE-6 (2/88) Abstract The aim of this article is to show how the braid groups can serve as a good platform to enrich cryptography. Braid groups are useful to cryptography for a number of reasons: (i) the word problem is solved via a fast algorithm which computes the canonical form which can be efficiently handled by computers, (ii) an algorithm which computes an unfaithful matrix representation for a braid exists, which is also efficiently handled by computers. Introduced are two pro-tocols for asymmetric key exchange based on the braid groups. The braid groups are an example of a larger set of groups, namely, the Ar t in groups. This raises the question as to whether the other Ar t in groups are useful in public key cryptography, or whether the braid group is unique. Outline Below is an introduction to public key cryptography and the key agreement protocol proposed in [1]. Chapter 2 is an introduction to the braid group. Chapter 3 discusses the canonical form for words in the braid group, and how this form can be used for key exchange as in [18]. In Chapter 4, the braid cryptosystem based on the coloured Burau matrix, as in [2], is discussed. Chapter 5 gives an introduction to Ar t in groups and Coxeter groups, and dis-cusses possible cryptosystems using other Ar t in groups of finite type. Finally, in Chapter 6, I will discuss various attacks to the proposed systems and draw some general conclusions on the braid and Ar t in groups applications to public key cryptograhy. ii Table of Contents Abstract ... ii Table of Contents ... iii List of Figures ... v Acknowledgements ... vi Chapter 1. Introduction - Public Key Cryptosystems ... 1 1.1 What is a Public Key Cryptosystem ... 1 1.1.1 Symmetric ... 2 1.1.2 Asymmetric ... 2 1.2 How can Group Theory be applied to Cryptography? ... 3 1.2.1 Arithmetica's Group Theoretic Protocol for Key Exchange Chapter 2. The Braid Group ... 5 2.1 Geometric Definition of a Braid ... 5 2.2 Definition by Group Presentation ... 8 Chapter 3. Method 1: Canonical Forms ... 11 3.1 Garside's Normal Form ... 11 3.2 Thurston's Normal Form ... 15 3.3 The Cryptosystem Based on the Canonical Form ... 19 3.4 Why Does This Cryptosystem Work? ... 20 3.4.1 How Fast is the Cryptosystem? ... 20 3.4.2 How Secure is the Cryptosystem? ... 20 i i i Chapter 4. Method 2: Group Actions ... 23 4.1 The Coloured Burau Matrix ... 23 4.1.1 A Coloured Burau Matrix for /3 ... 23 4.1.2 The Coloured Burau Matrix Satisfies the Braid Relations ... 25 4.1.3 The Coloured Burau Group ... 27 4.2 The Cryptosystem Based on the Coloured Burau Matrix ... 28 Chapter 5. Coxeter Groups and Art in Groups ... 30 5.1 What are Ar t in Groups and Coxeter Groups ... 30 5.2 The Word Problem ... 31 5.2.1 Constructing the Normal Form ... 34 5.3 J 2 (m) ... 35 5.3.1 The Normal Form ... 36 5.4 The Other Ar t in Groups of Finite Type ... 37 5.4.1 A n Alternative Solution for Solving the Word Problem in Ar t in Groups of Finite Type ... 38 Chapter 6. Analyzing the Cryptosystems - Possible Attacks ... 41 6.1 The Length Attack ... 41 6.2 Linear Algebraic Attack ... 42 6.3 Conclusion ... 44 Bibliography ... 45 iv List of Figures Figure 1 - A n example of a 3-braid and a non-braid ... 6 Figure 2 - a(3 ... 6 Figure 3 - aoT1 ... 7 Figure 4 - Standard Inclusion ... 8 Figure 5 - Braid Projection ... 8 Figure 6 - cr4 and a~x ... 9 Figure 7 - Braid Relations ... 9 Figure 8 - Permutation Braids ... 15 Figure 9 - Constructing elements of S ... 21 Figure 10 - Constructing elements of T ... 22 Figure 11 - /3 = 0\o~^v<j\o~^V(j\(j~^voz ••• 24 Figure 12 - UjO"j = o^Oi ... 25 Figure 13 - Braids (i) and (ii) ... 26 Acknowledgements I would like to thank Dr. Dale Rolfsen, my thesis supervisor, for his guid-ance, encouragement and generous financial support throughout my work on this thesis. I would also like to thank Dr. Stephanie van Willigenburg for reading through the draft of this thesis. Finally, I wish to thank my family and Peter for their love, support and encouragement. vi Chapter 1. Introduction - Public Key Cryptosystems Chapter 1 Introduction - Public Key Cryptosystems l Recently, a new approach to public key encryption based on the difficulty of solving the word and conjugacy problems for finitely presented, non-abelian groups was proposed by Anschel, Anschel and Goldfeld in [1]. The method is based on having a canonical form for words in the given group, which is computed rapidly, and in which there is no known fast solution to the conjugacy problem. A key example of such a group is the braid group. 1.1 What is a Public Key Cryptosystem Whenever we communicate over an insecure channel, for example, via e-mail or the internet, the messages we send are vulnerable in the sense that at any time they can be intercepted by an adversary, a third party wishing to read the sent messages. A cryptosystem is a method of sending messages over an insecure channel so that, should an adversary intercept a message, it is not decipherable to anyone other than the intended receiver. A cryptosystem, or an encryption scheme, is a tuple (M, C, K, e, D) such that: 1) M is a set called the message space. A n element of M is called a plain text. 2) C is a set called the ciphertext space. A n element of C is called a ciphertext. 3) K is a set called the key space. A n element of K is a key. 4) e — {Ee : e E K} is a family of functions Ee : M —> C. A n element of e is called an encryption function. 5) D = {Dd : d e K} is a family of functions Dd : C —> M. A n element of D is called a decryption function. Chapter 1. Introduction - Public Key Cryptosystems 2 6) For each e e K, there exists d G K such that Dd(Ee(m)) = m for all m £ M. There are two main types of cryptosystems: symmetric and asymmetric. 1.1.1 Symmetric Alice wishes to send an encrypted message to Bob. Alice uses an encryption key, e, and Bob uses the corresponding decryption key, d. A cryptosystem is called symmetric if the encryption key, e, is always equal to d, or if d can be computed from e easily. Suppose Alice and Bob wish to share a secret message using a symmetric cryptosystem. Let e be the secret key. This must be exchanged before communication and kept secret since the corresponding decryption key, d, can be determined from e. 1.1.2 Asymmetric Systems In an asymmetric system, the keys e and d are distinct. The security of the cryptosystem is based on the difficulty of computing d given e. Each user in the system chooses two keys, a public, and private key. Each user publishes their public key. If Alice wishes to send a message to Bob she does so by encrypting the message using Bob's public key. Bob then decrypts the message using his private key. Asymmetric systems are called Public Key Cryptosystems. Public key cryptosystems were first presented in the 1970's by Diffie and Hellman [11]. Since then many public key cryptosystems have been proposed and broken. As with the Diffie - Hellman method of key exchange, the most successful public key cryptosystems are based on difficult problems in number theory. One of the most well known methods is R S A (Rivest, Shamir, Adleman) [22], which is based on the difficulty of factoring integers with large prime factors. Schemes such as Diffie - Hellman [11] and ElGamal [12] are based on the difficulty of the discrete logarithm problem. In recent years there have been several attempts to develop alternative public key cryptosystems that are not based on number theory. One approach is to use hard problems in combinatorial group theory, such as the word problem. Chapter 1. Introduction - Pubhc Key Cryptosystems 3 1.2 How can Group Theory be applied to cryptography? When constructing a public key cryptosystem, it is important for the running time to be fast, and for the system to be secure. In this paper, we study protocols for asymmetric key exchange whose security is based on the difficulty of solving systems of simultaneous equations in finitely generated, infinite, non-abelian groups. 1.2.1 Arithmetical Group Theoretic Protocol for Key Exchange The following is Anshel, Anshel, and Goldfeld's [1,2] four step protocol for exchanging a secret key over a public channel. Let G be a finitely generated, non-abelian group (publicly known). Two subscribers, Alice and Bob, are each assigned publicly known subgroups SA = { 0,1, o m ) SB = ( &i, K ). Step 1 Alice chooses a secret element (private key) a £ SA, say a = a^a^ atk and computes, rewrites, and transmits the collection of elements a~lb\a, a~1b2a, , a~1bna to Bob. Bob then does the same: chooses b € SB, say b = b^b^ bj, and sends 6 _ 1 a i&, b~1a,2b, , b~1amb, to Alice. We want these conjugates to be rewritten in such a way that an adversary observing these transmissions will be unable to determine a or 6. Step 2 Alice then computes (b-^b) (b^ai.b) .... (b-laikb) = b~la-i1 ....a,ikb = b_1ab. Likewise, Bob can compute a~lba. Step 3 Alice knows both a and b~lab so she can compute the key K = a^b-i-ab. Bob knows b and a~1ba, so he can compute K = a-1b-1ab=(a-1ba)-1b So each subscriber has obtained the same key K. K will be in a (usually different) rewritten form. Chapter 1. Introduction - Public Key Cryptosystems 4 Step 4 Each subscriber must extract an identical element from the common key K. This is the shared secret. There are two main methods for doing this: 1) Canonical forms, 2) Group actions. The braid group can be used for both of these methods. The hardness of discovering this shared secret is based on the following problem. The Conjugator Problem: Given elements a and & of a group G such that a and b are conjugate, find x in G such that a = x~lbx. Chapter 2. The Braid Group 5 Chapter 2 The Braid Group The braid group was first defined by Emi l Ar t in in [3]. 2.1 Geometric definition of a braid Imagine a cube with n points labelled Qi, .... Qn on the top and n points labelled Q[, Q'n on the base. For neatness we express these points in specific coordinates: *3l = ( 2' n+T' •" * 5 n = ( 2> n+T> Qi = ( i ^TT> 0), ... Q'n = ( I , 0). Therefore, is directly underneath Qj. We join Qj to by means of n arcs in such a way as to not intersect each other. Suppose we intersect the cube with an arbitrary plane, P , parallel to the base of the cube. If P intersects each of the n-arcs at one, and only one, point, then we say these n-arcs are an n — braid. (See Fig. 1). Two braids in a cube, whose endpoints we keep fixed, are said to be equiva-lent if we can continuously deform one to the other, through n-braids, without causing any of the arcs to intersect each other. Chapter 2. The Braid Group Qi Q 2 Q3 I / \/ / \ \ / / J 1 / \ Q i Q 2 Qz Qi Q 2 Qs f / / \ / \ i \ Q i Q' 2 Qs Figure 1: A n example of a 3-braid and a non-braid Let B„ denote the set of all equivalence classes of n-braids. For two elements of Bn, a and ft, we obtain their product a/3 by glueing the base of the cube a to the top of the cube /?. (See Fig . 2) Q i Q2 Q 3 a Q i Q2 Q3 Figure 2 : a(3 Chapter 2. The Braid Group 7 Similarly, we can define the product /3a. Note, in general a/3 is not equivalent to f3a. This product makes Bn a group. The identity is the braid where all arcs are just vertical lines connecting Qi to Q\. The inverse of a braid j3 is obtained by reflecting the braid in a horizontal mirror at the base of the cube. (See Fig . 3) Qi Q2 Qz Q'x Q'2 Q'3 Figure 3 : cta~l There is a standard inclusion from Bn to Bn+i obtained by adding points Qn+i and Q'n+1 and connecting these points with a vertical line (see Fig . 4). Hence we get a directed system of groups Bx C B2 C .... C B^ where B^ denotes the direct limit of the Bn. Chapter 2. The Braid Group Q l Q 2 - . Qn-lQn Q l Q2-- Qn-lQn Qn+1 / ( > > > < > / / < > / / < » 4 > ( > < > p / < » ( » ( > < > Q i Q 2 - - Q U Q ; Figure 4: Standard inclusion Q i Q i - . Q U l Q ; Q'n+1 2.2 Definition by Group Presentation Let /3 be a braid, and p : C x [0,1] —> i i x [0,1] be the projection onto the yz plane. We can arrange /3 in such a way that all double points of lie in different horizontal planes. (See Fig . 5.) Figure 5: Braid projection Among the n-braids we can create specific braids by connecting Q , to Q'i+i and Q i + i to Q J , and then connecting the rest of the Qj to Q ^ (j i,i + 1) by line segments. We denote this type of braid <7;, or er"1, where string i crosses behind i + 1 in CTj and string i crosses in front of string i + 1 in o""1. (See Fig . 6) Chapter 2. The Braid Group i i + 1 i i+1 9 Figure 6: <Ti and <ri We use these elements to describe any element in the braid group. First divide the regular diagram of a braid by lines parallel to the base so that in each rectangle we have only one crossing and so each of these rectangles is a braid of the form CTj or o ^ 1 . By definition of the product of braids we can decompose /3 into the product of the ctj's and cr^ 's . Hence Bn is generated by the elements U\, , C n - i -Definition 2.1 The braid group on n strands is the group generated by cr,, i = 1 , n — 1, with the relations: 1) OiGj = OjOi if \i - j\ > 2 2) OiO-jOi = o-jCTiCFj if \i - j\ = 1. i i+1i+2 i i+1 i+2 i j i OiOi+iGi = 0~i+10-iO-i+1 OiOj = OjGi Figure 7: Braid relations If we add the relations of = e, for all i, then we get a presentation for the symmetric group Sn. Hence Sn is a quotient group of Bn. The natural projection from Bn to £„ fits in a short exact sequence 1 • Pn > Bn > Sn > 1 Chapter 2. The Braid Group 10 where Pn is the pure braid group on n-strands which consists of all braids such that Qi is connected to Q\ for all i, and so the associated permutation of the initial points { 1 , . . . , n} is the identity. Chapter 3. Method 1 : Canonical Forms Chapter 3 Method 1: Canononical Forms 11 If there exists a feasible algorithm to put every element of the braid group Bn into a unique canonical form then Alice and Bob simply put their obtained key K into that canonical form. We start by describing Garside's solution for the word problem in the braid group (1969) and then describe how Garside's method was improved by Thurston, who introduced his left and right greedy normal form. Thurston's normal form has the added advantage of being computed in quadratic time. 3.1 Garside's Normal Form Let Bn be the braid group with presentation as denned in Definition 2.1. Definition 3.1 A word consisting of an ordered sequence of the generators only, in which no inverse of any generator occurs, is called a positive word. Definition 3.2 Two positive words A and B are said to be positively equal, written A=PB if 1) A = B, ie A and B are the same letter for letter, or 2) A is transformable into B (and vice versa) through a finite sequence of positive words, such that each word of the sequence is obtained from the preceding word by a single application of the defining relations. For example o~\o~20~zo~\ =p o2o \02<Jz-Chapter 3. Method 1 : Canonical Forms 12 The Fundamental Word A Suppose l < r < s < n — 1 and let the word oror+\ os, where all the generators from or to os inclusive occur in ascending sequence, be denoted by K c s ) -Let I I S be the word [p\ os). Let r be the mapping of Bn onto itself given by r(o-i) = cr„_j. By inspection of the relations r extends to an automorphism of Bn, and we will call this automorphism reflection in Bn. We also define a reversing antiautomorphism rev: Bn —> Bn, defined by rev{ui) = Oi. This has the effect of reading the reverse word in the braid generators. Let A r be the word defined as A r = IL.IL._x III. In Bn, let A denote the fundamental word A = A n _ i = (0x02 CTn_i)(-i-2 CTn-2) (^10"2) (-1). Theorem 3.3 (Garside, [15]) In Bn, every word W can be expressed uniquely in the form A m A , where m is a maximal integer (possibly negative) and A is a positive word. In order to prove the theorem, we need the following lemma and theorem. Lemma 3.4 In Bn there exist positive words Xr,Yr such that Proof By definition A = (ai02....o-n-i)(oi02....0n-2)----(o-io2)(oi). Therefore, A = Y\0\ where Y\ = ] !„_! . . . . n 2 . Now consider II t <T s _i , where s < t. Then I I t (T s _ i = (0i02....0t)0s-\ = (o-iO-2- — O~s-2)0s-10s{<7s+l~~0t)o~s-l =p (CiCT2----0's-2)l7'«-lC sCT s_i(CT s +i . . . .O-t) —P (o1a2....os-2)osos_ios(os+i....ot) =p 0-s(oiO2....Os-2)0-s-1Os(os+i....Ot) = os(oi....ot) = osUt. Now, if / ( o - j , O j ) is any word involving the generators Oi, a i + i , . . . , Oj only, then, by the above n t /(<7l,0- 2 , . . . ,0 - t _i ) = f(02,03, ...,Ot)Uf Let ot be any of the generators o2, 03, an-\. Then denoting n t _ 1 n t _ 2 . . . . i i i = (o1o2....ot-.1)(oio-2....o-t-2)--{o-i) by f{oi,02,--,ot-{) we have A = n n _ i . . . . l l f + i l l t / ( a i , c 7 2 , , a t - i ) = p n J 1 _ 1 . . . .n t + i / (<T 2 , (T3 , . . . . , (7 t )n t = p n n _ i . . . . n t + i / ( o - 2 , a 3 , . . . . ,CTt ) (CTiCT 2 . . . . a - t_ i ) cr t Chapter 3. Method 1 : Canonical Forms 13 Therefore, there exists a word Yr such that Yr = p n n _i . . . I I r + i / (o-2 , (J3 , ...,CTT.)(CTiCr2—0rr-l),r = 1, —™ ~ 1, with the property A =p Yror. Now set Xr = rev Yr. Then o~rXr — orrevYr = rev(Y^.oy) = p reuA. I claim that rev A =p A : Clearly, revAi =p A i . By induction, assume true for the case At =p revAt. Then revAt+i = rev((o~io~2----o~t+i)At ) = revAtrev{a1o-2:..at+i) =p At{at+1...a2Oi) = (CTl...CTt)crt+i(c7i...Crt_i)CTt(...)((TiCT2)CT3(c7i)cr2(cri) Therefore rev A = p A and the proof is complete. • Theorem 3.5 In Bn, for any integer m, (i) PA2m =p A2mP, PA2m+1 =p A2M+1T(P) for all positive words P, (ii) QA2m = A2mQ, QA2m+1 = A2m+1r(Q) for all words Q, where T is the mapping from Bn onto itself given by r(ai) = an-i-Proof Firstly, consider o-\Ar. We have o-\Ar = a i n r n r _ i . . . . i i i = er 1n r(cr 1er 2 . . . .oy_i)(cri . . . .ov_2)... .0-i = CTinr((Ti(T2----0"r-l)Ar_2 Now, I claim orHt =p II t(7 r_i for 1 < r < t < n — l since arIlt = ar(aia2....o-t) = 0-r{p\0-<i----0-r-2)0~r-\Or{Pr+\-~-at) =p (0-i0-2....O-r-2)0-r-l0-rO-r-l{o~r+lO~r+2----O~t) =p (CTiCT2....CT r_2)Cr-lCTr(CTr+l 0Y+2-"-< J«)°y-l = n t ( T r _ i as required. Therefore, eriIIT.(<7i<72....ay_1) A r _ 2 = p <7i((72....<77.)n7.Ar_2 =p n r I I r _ i ( T r A r _ 2 —p Y\.rT\.r—\Ar—20~r —p Ar0~r. Therefore, a±A = (TiA„_i = p A„_iCT n_i = A r ( c 1 ) . Now consider when r = 2 , 3 , n — 1. ayA = c r r n n _ i n n _ 2 . . . . n i = O-7.(CT1(T2....(Tn_i)(criO'2....0r„_2)....(CTlCr2)(o-i) = c r r i i n _ i n n _ 2 . . . . n n _ r - + i ( r i n _ j . n n _ r _ i n n _ r _ 2 . . . . n i ) = (TT.Iln_iIIn-2"--nn_r-(-l A „ _ r = p n n _ i . . . . n „ _ r + i O " i A n _ r (by repeated application of the claim) ~p - f f n — 1 — A n — r ® ~ n —r • Aan-r i.e., crrA =p AT(ar), proving part (i). Now (i) a'1 A = AT(CT T . ) - 1 , (ii) oy A - 1 = A _ 1 T ( C T 7 . ) , and (iii) o ^ A " 1 = A- 1 r (<r T . ) - 1 , all follow from the above and the definition of r , proving (ii). Chapter 3. Method 1 : Canonical Forms 14 Proof of Garside's Theorem Let W be a positive word. Using the defining relations, construct the set P(W) of all words positively equal to W. This set is clearly finite, since any application of the defining relations introduces no new generators or alters the length of the word. Select any word, W±, say, from P(W) starting with as many occurrences of A as possible. (This can be done using the division algorithm of [15].) So suppose W =p Wx =p AfA where t is a maximal integer. Now, A cannot be a divisor of A since otherwise there would be a word in P(W) starting with more than t occurrences of A . We must now find a unique expression for A. Suppose A has word length I. Construct the set P(A) of all words positively equal to A. Each word in this set is of the form o^o^..., Oj1aj2...., etc Now write the set of sequences N\ = i\i<i , N2 = jiJ2----, where 1 < ik,jk,---- < n — 1 and each Nk consists of I terms. These sequences Nk are all distinct and can be ordered lexicographically. Suppose the smallest of these sequences is Ns. Then the corresponding word, which is uniquely de-fined, is called the base of A, denoted A'. For example, consider the braid (3 = O1O2O1O3 = p 020\0iGz = p 0"i<72<73<Ji. Then Ni — 1213, N2 = 2123 and JV3 = 1231. The smallest of these sequences is N\ and so the base of f3 is the word aiO20~iO3. Then, by setting W =p AlA', we have a unique expression for W. Now let W be any word in Bn. We can write W as W E E W1o-1W2o-l....a-1Ws+1 where each Wj is a positive word (possibly empty) and Oik is a generator. For each oik we have, from Lemma 1, that there exists a positive word Xik such that therefore sXik —p A a'1 = XlkA~i So we can write W as W = WiXilA~1W2Xi2A~1 ....WsXi3A~1Ws+i Moving the factors of A - 1 to the left using Theorem 3.5, we have W = A~SP where P is a positive word. From above, we can write P as P = AtA. Therefore, W = At~sA = APA. Now we can express A as before by putting A = A', where A' is the base of A. A l l that is left to prove is that this representation is unique: Suppose ApA = AqB. Let q < p and let p — q = t, where t > 0. Then, since APA = AqB we have that A1 A = B. Chapter 3. Method 1 : Canonical Forms 15 From Garside ([15] Theorem 4), we have that in Bn if two positive words are equal, then they are positively equal. Therefore A1 A =p B and so B contains an occurrence of A , contradicting the maximality of A . Therefore q is not less than p. Similarly, p is not less than q. So p = q and therefore A = B, so A =p B. 3.2 Thurston's Normal Form In 1992 Thurston improved on Garside's solution by introducing the left and right greedy normal form. In 1994, Elrifai and Morton published an algorithm for putting a braid word into its left greedy canonical form. The method of this canonical form is based on the study of braids in terms of the set of positive permutation braids. These braids are in one-to-one corresondence with the permutations in the symmetric group Sn via the canonical map Bn —> Sn. Permutatation Braids Denote a permutation 7r in Sn, 7r(i) = hi, by ir = bxb2...bn. To n we associate an n-braid j3 that is obtained by connecting the upper i-th point to the lower 6j-th point by a straight line and then making each crossing positive. The braid (3 constructed as above is called a positive permutation braid. Let the set of positive permutation braids be denoted by S+. Two such braids, /3i, with permutation IT = 2413 , and f32, with pemutation ir = 321, are shown below. Figure 8: Permutation Braids Clearly, if two braids, /?i and f32, in 5+ induce the same permutation then A = /?2 : number the strings of each braid 1, . . ,n according to the top point of each string. Then string i and string j have at most one crossing point, with, if i < j, string j passing in front of string i. Each braid can then be constructed in a cube in which string 1 lies on a vertical plane at the back level, and the other strings in a succession of vertical planes lying further forward. Since f3\ and P2 induce the same permutation on Sn the i-th string in each braid runs to the same point at the bottom of the braid and one braid can be moved to the other by isotopy keeping each string in its vertical plane. Chapter 3. Method 1 : Canonical Forms 16 The fundamental braid, defined earlier, is the permutation braid correspond-ing to the permutation irn(i) = n + 1 — i. Definition 3.6 For o positive word P, we define the starting set, S(P), and the finishing set, F(P), to be S(P) = { i : P = OiPi, for some positive word Pi } F(P) = { i : P = PiOi, for some positive word Pi }. Definition 3.7 A decomposition of a positive word P = AB is said to be a left weighted decomposition if S(B) C F(A) Theorem 3.8 For j3 £ S£, the following are equivalent: (i) i £ S(@), (ii) strings i and i + 1 cross in (3, (Hi) ir(i + 1) < 7r(i). Proof If i £ S(/3) then (3 = OiP for some positive braid P. It follows that since strings i and i + 1 cross in CTj (ii) must hold. Also, since P is a positive braid, the two strings cannot uncross since this would involve a negative generator. Since /3 £ 5+, if (ii) holds then strings i and i + 1 cross only once, therefore 7r(i + l ) < n(i). If (iii) holds then strings i and i + 1 cross in /?. By the construction of permutation braids described above, in which each string lies in a different vertical plane, we can move strings i and i + 1 so that the crossing Oi appears at the very top of the braid. Hence i £ S(f3). Remark From Theorem 3.8 we can define the starting set of a permutation braid as: S(P) = {%: 7r(i) > TT(» + 1) }. Similarly, by an application of revP we can define the finishing set of a permutation braid as: F(P) = {i: T r - ^ i ) > 7 T - 1 ( i + l ) }. Theorem 3.9 (Thurston [14], Elrifai-Morton [13]) For any W £ Bn, there is a unique representation called the left greedy canonical form, as W = AkAiA2....Ap , where k is an integer, A\, Ap e 5+ \ { e, A }, where AiAi+i is left weighted for 1 < i < p — 1. We say that p is the canonical length, which we will denote by len(W), of W. For the fundamental braid A we have (Thurston [13], Elrifai - Morton [12]) that i) A = o^i t = l , . . . . , n - l , Pi £ S+ A = QiOi i= l , . . . . , n - 1, Qi g S+ ii) (TjA = Ao - n _j Therefore, given a word W £ Bn we can replace any occurrence of o~x by o~l = A~1Wi (property (i)), and then collect all occurrences of A - 1 to the left using property (ii). Therefore, we can write W = AkP, where P £ B+ . We want to write P as a product of positive permutation braids. Lemma 3.10 A £ 5+ has S(A) = {l,...,n} if and only if A = A. Chapter 3. Method 1 : Canonical Forms 17 Proof Let A have permutation nr. Since S(A) = {l,...,n} we have that ir(i) > n(i + 1) for all i. Therefore, TT = n n — 1 ... 1, and so 7r(i) = n + 1 — i for all i. Therefore, A = A. Since this argument is reversible the result follows. • Before we prove Theorem 3.9, we need to define some notation and results. r (i) o~i if i = j Notation: Let CTJ * o~j = < (ii) OiOj if \i — j\ > 2 [(iii) OiOjOi if \i-j\ = l. Lemma 3.11 (Garside's Lemma) [15] Let P=aiP\ = o-jP2 with Pi and P2 non empty. Then there exists P 3 such that P = (at * aj)P3 •. (Proof omitted) Lemma 3.12 Let A G S+. Then atA G 5+ */ and only if i S(A). Proof Strings i and i +1 in a^A cross once if and only if i £ S(A) and twice otherwise, while all other pairs cross at most once. Remark A n extension of this shows that i,j £ S(A) if and only if (cr* * o~j)A G S+, while application of Lemma 3.12 to rev A shows that a similar result holds for the finishing set. Proof of Theorem 3.9 Suppose we have written W as W = AqP, where P is a positive word (by Garside). Firstly, we show there is a left weighted decomposition of P as AiP^. Consider all decompositions of P as a product P = AB where A G 5+. Choose one in which the word length of A is maximal. Construct S(B) and F(A). If S(B) <£ F(A) then we have some i G S(B) such that i ^ F(A), ie B = OiB\ for some B\ and so B\ = a~lB. Set A\ = Aoi (G by the remark following Lemma 3.12). Then P = AoiO^B = A\BX. In the same way, construct S(B\) and F(Ai). If S(Bi) <£ F(Ai) do as above. Continue in this way until we reach some point, m, such that P = AmBm and S(Bm) C F(Am). This procedure is clearly finite since at each step the finishing set of the Ai gets larger, whilst the starting set of the Bi gets smaller (in fact S(Bm) could be empty). Call this factorization P = A\P\. (Note that A\ is not necessarily the same word as before.) We now show that every other positive factorization of P as P — AB, with A G S+, is a subfactorization, in other words, A\ = AQ for some Q: Suppose not, i.e. suppose there exists a word Ccfi G 5+ such that P = CoiB1 and C G is a left subfactor of Ai but Co* is not. Choose such a factorization of P with largest possible length C. Write Ai = CQ for some non empty Q. Construct S(Q). For j 6 S(Q) we have that A\ = Co-jQ' for some (possible empty) Q'. Since A\ G 5+, we have Ccr, G 5+. Write the resulting factorization as P = Co-jB". Now P = CuiB' = COJB" so OiB' = OjB"'. Applying Garside's Lemma we have that o^' = o^B" = (a^a^B'" for some B'" and so P = C(ai*ai)B"'. By the remark following Lemma 3.12, C(<Tj * O~J) G S^, which gives a factorization of P with a larger subfactor (at least containing Co~j) in common with A\ while G(o~i * Oj) is not itself a subfactor of A\. Chapter 3. Method 1 : Canonical Forms 18 This left weighted factorization, P = AiPi, is unique: If P = AB is another left weighted factorization then we can write A = AQ for some Q. Either, Q is empty and A = A , B = Pi and we are done, or we have i £ S(Q). Then A = AoiQ' and so Aot £ 5+ and so i <£ F(A). However, B — QPX so i £ S(B) and so the factorization P = AB cannot be left weighted. Therefore, A\ = A and B = P x . Now let P = At P i , where A £ 5+ and P i is a positive braid. In the same way as for P we can write P i as a left weighted decomposition A 2 P 2 , where A2 € 5 + , P 2 is a positive braid. Continuing in this way we have that P = A P i = A1A2P2 = AA2A3P3.... This factorization is finite since the length of P is finite and any word positively equivalent to P must have the same length. Therefore, we can write P as P = AA2...A- Since the factorization is left weighted, any occurrences of A must be at the beginning and we have that P = ArA1A2...Ap so that W = AkA1...Ap, where k = q + r. • The Algorithm Suppose we have a braid word W £ Bn written in the form W = ASW which we have computed by replacing all o~x,s with A~lWi. Below is an algorithm which puts the word W into its left weighted canonical form. Input: A list of elements of Sn with a table of products of each 7r £ Sn with the elementary transpositions Tj = (i i + 1), on the left and on the right, and a means of checking whether ir(i) is greater than + 1). (This enables us to find immediately the sets S(A) and F(A) for each positive permutation braid). A braid word W = BiB2-:Bp, where Bt € 5+. Initialization: k = 1. Step 1: If k = p then S T O P Step 2: If 5 (^+1) C F{Bk) then G O T O S T E P 8 Step 3: If S(Bk+i) £ F{Bk) then G O T O S T E P 4 Step 4: Select j € S{Bk+1) with j £ F(Bk). Let OjB' = Bk+1. Step 5: Bk: = BkOj Step 6: Bk+1: = B' Step 7: Go to S T E P 2 Step 8: k: = k + 1 Step 9: Go to S T E P 1 Output: A left weighted decomposition for W. Chapter 3. Method 1 : Canonical Forms 19 3.3 The Cryptosystem Based on the Canonical Form The key agreement proposed here is slightly different from the one proposed by Anshel-Anshel-Goldfeld. Choose two subgroups, Bi and Br, of Bi+r (= Bn). The subgroup Bi is generated by <7i, .... ,CT;_i, and Br is generated by 07+1, .... , c r ; + r _ 1 . The key point of these two subgroups is that for a £ Bi, b £ Br, ab = ba. Now consider the function /: Bi x Bi+r —» S ; + r x B ;+ r given by f(a,x) = (area - 1 , x), where a £ Bi, x £ Bi+r. This is a one way function since we can easily compute axa^1 given a and x, but given the pair (axa"1, x) there is no known algorithm to find a. In fact a may not even be unique. The Key Agreement Choose integers / and r and a braid x £ Bi+r. These are published. Now A(lice) chooses a word a £ Bi and computes y\ — axaT1. A then sends y\ to B(ob). B chooses a word b £ Br and computes y2 = bxb"1. B then sends y2 to A . Alice receives y2 and computes K = ay2a~l = abxb~xa~l. Bob receives y\ and computes K = by\b~x = baxa^b"1. We use this key agreement to construct a new Public Key Cryptosystem. Definition 3.13 A hash function, H, is a transformation that takes a variable-size input, m, and returns a fixed-size string which is called the hash value h (h = H(m)). Let H:Bi+r —> {0, l } f c be a hash function from the braid group to the message space. 1) Key Generation Alice chooses a £ Bi at random and computes y = axa~x. Alice then sends the public key (x, y) to Bob. 2) Encryption Let m be a message in {0, l}k. Bob chooses b £ Br at random. Bob then computes c = 6 x 6 _ 1 and d = H(byb~1) 0 m, where 0 denotes pointwise vector addition (mod 2). Bob then sends the ciphertext (c, d) to Alice. 3) Decryption Alice computes # ( a c a - 1 ) 0 d = H^ca'1) 0 H[byb'1) 0 m = H(abxb-la-1 0 H(baxa^b-1) 0 m = m. So the original message is retrieved. Chapter 3. Method 1 : Canonical Forms 20 3.4 Why does this cryptosystem work? 3.4.1 How fast is the cryptosystem? To analyse the cryptosystem we need to consider its speed. Theorem 3.14 Let U, V, W £ Bn. (i) For a positive word W of length I, the left canonical form of W can be computed in time 0(l2 n log n) (ii) Let U have left canonical form Aua\...ap and V have left canonical form Avbi...bq. Then the left canonical form of UV can be computed in time 0(pqn log n) (Hi) Let U have left canonical form AuAi...Ap. Then the left canonical form of can be computed in time 0(pn). Proof The proofs of (i) and (ii) are in [14], whilst the proof of (iii) is in [18]. 3.4.2 How secure is the cryptosystem? In order for an adversary to decrypt the ciphertext (c,d) = (bxb-l,H(baxa-lb-1)® m) they could compute a from axa~l or b from bxb~l. However, if we are given a pair, (x,y), of braids in B[+r such that y = axa-1 for some a £ Bi then a can be chosen from an infinite group in theory. Also, if xz = zx then a can be replaced by az. Thus y = axa~x does not have a unique solution a £ Bi+r, but the requirement a £ Bi may determine a uniquely. A more practical way for the adversary to decipher the message is to generate all braids of the form a = AuAi...Ap and check whether y — axaT1. However, this brute force attack is of no use since: Theorem 3.15 ([18]) The number of n-braids of canonical length p is at least (l^\\)p. Proof Since L 2 ^ ] = r for n = 2r +1 and n = 2r + 2, and clearly there are more (2r + 2)-braids than (2r + l)-braids of a fixed canonical length, we may assume that n = 2r + 1. Consider two subsets of 5+: S = { A £ S+ : S(A) C {l,2,...,r} and F(A) D {2,4,....,2r} } T = { A £ S+ : S(A) C {2,4,...,2r} and F(A) D {l,2,....,r} }. I want to show that there are injective functions from Sr —» S and Sr —> T. Since these functions are not necessarily surjective, |5 | > r! and |T | > H . Chapter 3. Method 1 : Canonical Forms 21 Consider a permutation n G Sr- Let a canonical factor A G S be constructed by defining the corresponding permutation n' G Sn = 52r+i by r 27r(i) + 1 for 1 < i < r 7c'(i) = < 1 / o r i = r + 1 I 2(i - r - 1) for r + 2 < i < 2r + 1. For example, let r = 3. Then in £3 we have six permutations: e, (123), (132), (12)(3), (13)(2), (23)(1). Clearly, for i = 1,2,3, TT'(I) = 3,5 or 7. The diagram below shows an illustration for r = 3. 7T Figure 9: Constructing elements of S Now for r + 1 < i < 2r + 1, we have 7r'(i) < n'(i + 1). Therefore, i ^ 5 ( A ) and so S{A) C {1,2,...,r}. Also, since 7r' _ 1(2i) > r + 1 and 7r ' _ 1 (2i + 1) < r we have that 2i G F(A). Therefore, F(A) D {2,4,....,2r} Now, for a permutation n G Sr, we construct a canonical factor A G T by defining the corresponding permutation 7r* G 5 „ by ir*(2i - 1) = (r + 2) - i for 1 < i < r + 1 7r*(2i) = (r + 1) + 7r(i) for 1 < i < r Figure 9 below shows an illustration for r = 3. Chapter 3. Method 1 : Canonical Forms 22 7T Figure 10: Constructing elements of T Now, since ir*(2i - 1) = (r + 2) - i we have that 7r*(2i - 1) < r + 1, and since 7r*(2i) = (r + 1) + 7r(i) we have that 7r*(2i) > r + 1. So (2i - 1) £ Therefore S(4) C {2,4,...,2r}. Similarly, Tr*~l{i) > -K*~l(i + 1) for 1 < i < r since = 2r-2i + 3 and T T * - 1 ^ + 1) = 2r - 2i + 1. Therefore {1,2,...,r} C F ( A ) . We have constructed injective functions Sr —> 5 and 5 r —» T and so |5 | > r! and \T\ > r\. By the construction of the subsets S and T, we have that for A £ S and B e T, AB and BA are left weighted. Since S C 5+ and T C 5+ there are at least ( H ) p n-braids of canonical length p. • As with other public key cryptosystems, a different private key b must be used each time a message is sent: Suppose the same key b is used to encrypt two messages, m i and m2, and the corresponding ciphertexts are (ci , d-i) and (c2, d2), then m2 can be deciphered from (mi , di, d2) since di = H(byb-1) 0 m i d2 = H(byb'1) © m 2 . Therefore, Hibyb'1) = mx 0 d x = m 2 © d 2 and so m x 0 rfa © rf2 = m2 0 d 2 0 d2 = m2. Another way an adversary may try to decipher a message is by using a math-ematical solution to the conjugator problem. Garside, Thurston, Elrifai-Morton and Birman-Ko-Lee have all published solutions to the congugacy problem in the braid group. However, their solutions do not find the word that conjugates two words. Chapter 4. Method 2: Group Actions Chapter 4 Method 2: Group Actions 23 We now discuss another method in which braids can be used in a Public Key Cryptosystem. This time the method is based on group actions. 4.1 The Coloured Burau Matrix It is known that the Alexander polynomial of a closed braid /3 can be found from the Burau matrix (what the Burau matrix is, and how it arises, I will not discuss). The Coloured Burau matrix was defined by Hugh Morton in [20],and is used to find a multivariable polynomial of a link L, formed by closing the braid P-4.1.1 A Coloured Burau Matrix for (3 Label the strings of f3 £ Bn by *i , t2, tn by putting, at the bottom, a label tj on the string which ends at the point Q'j. For example, let f3 = o~\o~2lo~\o2lG\0~2LO~Z- (See Fig. 11). Chapter 4. Method 2: Group Actions 24 t\ t2 t$ £4 Figure 11 - /3 = (TicrJ 1oio^ 1oiovT 1 03 Write Cj(a) for the (n— 1) x (n— 1) matrix which differs from the unit matrix only in three places on the i-th row, 1 < i < n — 1, ie, / 1 0 0 Ci(o) = —a 0 0 0 0 1 / When i— 1 or i = n — 1 the matrix is truncated appropriately to give only two non-zero entries on row i. Now construct the Coloured Reduced Burau matrix, Bp, of the general braid as a product of matrices Cj(a), in which a is the label of the current undercross-ing string. This gives, B0(ti,t2, ...,tn) = n U i C ^ r K ) ) 6 * -where ar is the label of the undercrossing string at crossing r, counted from the top of the braid. Chapter 4. Method 2: Group Actions 25 So for example, when ft = 0\02 loio2 1aia21o-3, the labels ai , . . . , ar are ti, *4, *2, t\i t$, t2, *4 respectively and Bp is the 3 x 3 matrix product 4.1.2 The Coloured Burau Matrix satisfies the braid relations In Bn we know CTjCTj = OJCTJ for — > 2 and OiOjOi = OjCJiOj for = 1. Consider the relation CTJIX, = o^o* (see Fig . 12). Figure 12: aiOj — a^Gi The corresponding Coloured Burau matrix for CTiCr, is / 1 0 Ci(tr)Cj(tp) — \ (I 0 0 0 1 ••• 0 0 ... o ... o 1 0 if tip 0 0 0 0 0 \ 0 0 0 1 0 1 0 • • • 0 0 0 0 1 / ••• 0 0 0 0 0 \ 0 0 0 0 0 0 0 0 0 ••• 0 0 ••• 0 0 0 0 tp -tp 1 / 1 0 • • • 0 0 0 0 0 \ 0 1 ••• 0 0 0 0 0 0 1 0 0 0 tp tp 0 0 0 0 0 0 — Cj(tp)Ci(tr), 0 0 0 0 1 / 0 0 0 1 0 ••• 1 0 0 0 0 1 / Chapter 4. Method 2: Group Actions 26 which is the coloured Burau matrix of OjCTj. Verification of the second relation is left to the reader. Here is a more complex example. Example (i) ozo±o%o\ = (ii) o^o^oxo^ (see Fig . 13). Figure 13: Braids (i) and (ii) Consider (i). We get Bp = C3(t5)C4(t 5)C 3(t4)Ci(t2) 1 0 0 1 0 i 5 0 0 0 \ 0 0 0 -h 0 1 1 h t^ti °\ 0 1 1/ 0 0 0 —t5tA \ J (ii) Now consider Bp fl 0 0 0 0 1 0 0 0 0 1 0 \ 0 0 t5 - i E SI -h 0 / = C 4(t4)C 3(t5)Ci(t2)C4(t5) 1 0 0 1 0 0 >0 0 -t2 0 0 0 0 0 1 u 1 1 ts £5^4 0 0 0 -uJ 0 0 0 — £ 5 * 4 ' I 0 \ 0 0 1 ts 0 0 0 -t5 1 1/ "*2 0 0 0 0 0 1/ z 1 0 0 \ 0 0 1 0 0 0 0 1 *5 \ 0 0 0 1 0 0 -ts 0 In each case we get the same matrix. So far we have just constructed the Coloured Burau matrix when we have a pictorial representation of the braid f3. If we don't have a braid diagram, how can we tell which string is going to be the undercrossing? How do we construct the Coloured Burau matrix? We need an algorithm to determine the reduced matrix. Chapter 4. Method 2: Group Actions 27 Firstly, consider the permutation n £ Sn determined by /3 in which a string connects position j on the bottom to position 7r(j) at the top. So, in this example, we have 7r(l) — 2, 7r(2) = 1, 7r(3) = 5, 7r(4) = 4, 7r(5) = 3 which corresponds to the product of disjoint cycles (12)(35)(4). We know that any two equivalent braids have the same permutation. We can construct this permutation without the braid diagram. Firstly, consider 03040301. The generator 03 corresponds to the transposition (34) sending string 3 to string 4 and vice versa. As we come down to 04 we get the transposition (45), the 4th string is sent to string 5 and vice versa. The product of these transpositions is (34) (45) = (345). Carrying on we get (345) (34) = (35) (4) and finally (35)(4)(12) = (12)(35)(4). Likewise, for O-4CT3CTICT4 w e S e t (45) (34) = (354), (354)(12) = (354)(12), (354)(12)(45) = (12)(35)(4). So we can build up the permutation by transpositions. We are going to use these transpositions by letting them act on the Coloured Burau matrix, permuting the variables in the matrix. 4.1.3 The Coloured Burau Group Suppose we are in Bn, so we have generators o~i, on-\. For i = 1,2, ...,n — 1, let yi = (Cj(ij), (i i + 1)) where (i i + 1) denotes the transposition, Ci(ti) is defined as before. The elements 3/1, yn-i generate a group CBn, the Coloured Burau group. A n element of CBn is of the form (M,cr) where M is an (n — 1) x (n — 1) matrix whose entries are polynomials in £1,..., tn, and o is a permutation in the symmetric group Sn-Multiplication of two ordered pairs (M,cr), (M',o') in CBn is given by (M,CT)(MV) = (M-o-(M'), 00'), where M, M' are matrices, and o(M') denotes the matrix obtained from M' by permuting the variables ti, tn appearing in M' by the permutation o via o(ti) — ta(iy There is a natural 1-1 correspondence between elements /3 of Bn and CBn which yields the coloured Burau matrix of /3. Example Let w — O4O3O1O4. 0 0 \ 0 0 1 % t3t4 0 0 1 u 0 0 - t s -t3t4 0 0 0 -t4J °\ 0 1 0 / ,(45) f 1 0 0 °\ 0 1 0 0 0 *3 1 \ 0 0 0 1/ ,(34) ,(354) Chapter 4. Method 2: Group Actions 28 2/42/32/12/4 0 0 0 V 1 1 h *3*4 -*1 1 0 1 o t3 o tztA o 0 - i s — i 3 i 4 0 0 0 — i 3 i 4 i o / ,(12) (354) 0 0 - i s 0 ,(12) (35) (4) Note, the matrix is almost the same as the one obtained earlier apart from the change of variables. However, if we permute the variables in the matrix according to the permutation u, then t\ i—> i 2 , i3 f-> i 5 , i 4 H-> i 4 , and so the matrix becomes 0 0 0 0 1 1 is t^4 0 0 0 - i s i 4 \ - i s 0 which is the same as Morton's presentation. 4.2 The Cryptosystem based on the Coloured Burau Ma-trix Fix an integer n > 4 and a prime p. We define the keyspace K „ i P to be the set of pairs (M,a), where M is an (n — 1) x (n — 1) matrix with coefficients in Fp, the finite field of p elements. The key extractor depends on a choice, T\, r „ , of distinct and invertible integers (mod p) and is defined as follows: Let w S B N . Associated to w there is a unique element (M,a) S C B N where M = M ( i i , i„) is a matrix and a is a permutation. Definition 4.1 The key extractor E: BN —• K N , P is defined by E(w) := £ ( ( M f i 1 ) . . . , i r J > j - ( M ( T u . . . , rn) (modp),a) where reduction (mod p) means reduction of every entry in the matrix. The Algorithm Input: A braid word w = g\g2---9i of length I, a prime p, and {TI, T 2 , rn}, distinct invertible integers (mod p). Initialization: M = (n — 1) x (n — 1) identity matrix, k = 0, n = identity permutation. Step 1: If k = I then S T O P Step 2: k := k + 1 Step 3: If 5 f c= ^ then G O T O S T E P 5 Step 4: If gk= a'1 then G O T O S T E P 8 Step 5: M := M-C^T^)(mod p) Step 6: 7r : = 7r(i i + 1) Chapter 4. Method 2: Group Actions 29 Step 7: G O T O S T E P 1 Step 8: M := M- ((Cifa(i))(mod p))~l Step 9: 7r : = n(i i + 1) Step 10: G O T O S T E P 1 Output: (M ,7r) The Cryptosystem Public information: A n integer N > 6 and a prime p > N, Distinct and invertible integers T 1 , T 2 , ...,TN (mod p) 1 Key Generation Suppose Bob wishes to send a message to Alice. Let publicly known sub-groups SA and SB be denned as before, SA — ( a i , . . . , a m ) , SB = (bi,---,bn). a) Alice chooses a braid a S SA, say a=af 1a^...a** 1 where e* = ± 1. b) Public key is a - 1 & i a , a _ 1 & 2 a , a ~ l b n a Encryption Given a message m € {0, l } f c and Alice's public key a) Bob chooses a braid b € S B , b) Bob then computes c = (& - 1 di&, b~1a2b,...,b~lamb) and a" 16a = (a- 1 6 I e i 1 a)(a- 1 6^a). . . . (a- 1 ^'a) Bob then sends the pair (c, d) to Alice where d = H((a~1ba)~1b) © m where i f is a hash function defined before. Decryption Alice receives the ciphertext (c, d) and knows her secret key a. She computes (6- 1a? 1&)(&-X a a&)-»(&~ 1<*&) = b^ab. Then, Alice computes a~1b~1ab, and, to retrieve the initial message m, she computes H^b^nb)® d = i f ( a - 1 ( 6 - 1 o 6 ) ) © i f ( ( a - 1 6 a ) - 1 6 ) © m = ( a - ^ - 1 ^ ) © i f ( a - 1 *; - 1 ^) © m = m. Chapter 5. Coxeter groups and Artin Groups 30 Chapter 5 C o x e t e r G r o u p s a n d A r t i n G r o u p s 5.1 What are Artin Groups and Coxeter Groups? Let / be a finite set. A Coxeter matrix over I is a symmetric \I\ x \I\ matrix M = (rriij) where ma = 1 for all i & I, and m^ = {2,3,....,00} for i j. The Coxeter graph, TM, associated with M is the graph with vertices in-dexed by I, with edges labelled connecting vertices i and j precisely when mij > 3. By convention, we only explicitly show this label when m,j > 4, so that an unlabelled edge means = 3. The Coxeter group of type M , denoted GM, is defined to be the group: GM = ( <7i,ff2,-,CT n : (o-jCrj)m« = of = 1 ). Given a Coxeter group, GM, the associated Art in group, A M , is the group with the presentation AM = ( 0-1,0-2, ...,crn : OiOj.... = OjOi.... , i ^ j ). We say an Ar t in group is of finite type if the associated Coxeter group is finite. Note that the map AM —> GM taking Cj S AM to cr, € GM is a surjective homomorphism. Below are the Coxeter groups of finite type along with their graphs. Type Coxeter Graph An (n > 1) 'I '2 *3 4 Bn (n > 2) \ '2 % Chapter 5. Coxeter groups and Artin Groups .2 31 Dn (n > 4) 1 3 X "' n-1 n .2 (n = 6,7,8) 1 3 "4 4 F 4 1 ^ ^ *4 n — 1 n 6 G 2 #3 h(m) The braid group with n + 1 strings is the Ar t in group whose associated Coxeter group, GM, is type A n . (Note , the Coxeter group B N is not equal to the braid group.) Having considered the braid groups application to public key cryptosystems, we now consider whether the other Ar t in groups of finite type can also be applied to cryptography. There are a number of reasons for believing that other Ar t in groups of finite type may be useful: The word problem is solvable by computing a canonical form. Ko-Lee indi-cate in [18] that automatic groups may be good candidates for cryptography. In [6] Charney proved that Ar t in groups of finite type have an automatic structure. Also, as with the braid group, the conjugation problem is presumably hard. 5.2 The Word Problem In 1972, Brieskorn-Saito generalized Garside's work and solved the word problem for finite type Art in groups. Their solution puts a word W into the form W = AkP where P is a word in the Ar t in generators (ie, P is a positive word), and A is the fundamental word described in Lemma 5.2. Chapter 5. Coxeter groups and Artin Groups 32 However, as with Garside's solution to the word problem, Brieskorn and Saito's solution is computed in exponential time. In [6] and [7] Charney gener-alized Thurston's normal form for Ar t in groups of finite type to show the word problem could be solved in quadratic time. Definition 5.1 Let M be a Coxeter matrix of finite type over I, and let FM be the associated graph. Let I = ( 7 1 ; I2) be a unique decomposition of the set I = {1, ...,n} into two sets such that no two elements of I\ and no two elements of I2 are joined by an edge. This is unique by inspection of the graphs if we require o\ S I\. The following products of generators in GM are associated to the decomposition: n ' = P I U °u n " =p n i e / 2 a*, n = i r n " . This set is well defined since the factors commute. Coxeter groups are examples of finite reflection groups, ie, they can be gen-erated by reflections. (See [17] for the precise definition and more information on finite reflection groups.) Suppose the Coxeter group can be generated by the reflections s ± , s n . Then the product si • • • sn is called the Coxeter element, and the Coxeter number, h, is the order of the Coxeter element. For example, the symmetric group, Sn, (= A i - i ) , can be generated by the transpositions (i i + 1) 1 < i < n — 1. So we take the Coxeter element to be (1 2)(2 3)...(n — 1 n) which has order n. Hence, the Coxeter group of type An has Coxeter number n + 1. Lemma 5.2 (Brieskorn-Saito [5]) Let M be a Coxeter matrix of finite type over I. Let U', H" and Ii be defined as above, and let h be the Coxeter number. Then the fundamental word A is : A =p U.h/2 if h is even, A = p u^-^W = p ff'tf*-1'/2 ifh is odd, A 2 =p Uh always. • (Proof omitted) The Coxeter numbers for the finite type Coxeter groups are given below: An Bn Bn E6 E7 E8 F4 G2 H3 HA J2(m) n + 1 2n 2 ( n - l ) 12 18 30 12 6 10 30 m. Let AM be an Ar t in group of finite type with presentation AM = ( o-i,....,an : aiOjOi.... = OjOiO-j...., i ^ j •) * s, ' S V ' rriij terms rriij terms =(S:R) Let Chapter 5. Coxeter groups and Artin Groups 33 GM = { o-lv...,on : (oiOj)mii = of = 1 ) be the associated Coxeter group. Let F(S) = the free group on S, F(S)+ = the free monoid on S, A+ = the monoid F(5) + /equivalence relation generated by R = (S : R)monoid' Deligne proved in [10] that A+ injects into A, and left and right cancellation laws hold in A+. Now, we have that (Tj = o-r1 in GM and so the natural map F(S)+ —• GM is surjective. The Cayley graph for G with respect to 5 is a directed labelled graph with vertex set G and edges labelled s from g to gs for each s £ S,g £ G. If we identify each edge with the unit interval, and declare the distance between two points x, y £ G to be the length of the shortest path between them, then any path p from x to y of minimal length and parameterized by arc length, is called a geodesic segment from x to y. A non empty word w £ F(S)+ is called minimal if it is a minimal length representative for its image in GM J or equivalently, if it represents a geodesic in the Cayley graph for G with respect to S. (The Cayley graph for G with respect to S is a directed labelled graph with vertex set G and edges labelled s from g to gs for each s £ S,g inG. If we identify each edge with the unit interval, and declare the distance between two points x,y £ G to be the length of the shortest path between them, then any path p from x to y of minimal length and parameterized by arc length, is called a geodesic segment from x to y. A n element a of A+ is minimal if it is an equivalence class of minimal words in F(S)+. For example, in the braid group, the minimal words are the permutation braids. We say that, for a minimal a, a > b if a = be for some b, c £ A+. Then, for any a £ A+ we have that the set {a' £ A+ : a' is minimal and a > a1 } has a unique maximal element. Denote this element by max(a). Let max(a) = a\. Then a > ax and a = ai?7i for some r/x £ A+. Let max(r]i) = a2. Then rji > a2 and rji = a2rj2. So, a = airji = a\a2i}2. Continue in this way. Clearly the word length of a^i is greater than the word length of r)i and so the process is finite. Therefore a = aia2....ak is a left weighted decomposition of a. This decomposition is a normal form for a. The following result is due to Charney [6]: Proposition 5.3 Let a = aia2...ak be a decompostion of a into rninimals, where a £ A+. Then this decomposition is in normal form if and only if a; = max(a{ai+i) for i = 1 , k — 1, ie, a\a2...ak is in normal form if and only if aiOj+i is in normal form for each i. • (Proof omitted) Chapter 5. Coxeter groups and Artin Groups 34 The fundamental word, A £ A+, is the minimal corresponding to the unique longest element of GM- From Charney, we have the following: (i) a £ A+ is a minimal if and only if A > a, ie, A = ab for some b £ A+, (ii) A2 a = aA2 for all a£ A+, (iii) The involution o n a = A _ 1 a A on A preserves A+ and takes minimals to minimals, (iv) Let a £ A+ such that a ^ A . Then there exists a minimal a* such that A = aa* = a*a — a*a and (a*)* — a. From this we have that for any word w £ A, we can write it) = Apa where a £ A+. Therefore, w = Apaia2....afc is the normal form for w. Definition 5.4 Let W be a word in F(S)+. Suppose W is of the form W = UoiOiV where U and V e F(S)+. Then we say that W has a quadratic factor. A word with no quadratic factors is called square free. Lemma 5.5 (Brieskorn-Saito [5]) (i) A is square free, (ii) U £ F(S)+ is square free if and only if it a divisor of A. (Proof omitted) a 5.2.1 Constructing the Normal Form Let a be a minimal in A+. Then we define the starting set, S(a), and the finishing set, F(a), of a to be the subsets of the generating set S defined by S(a) = {ai € S : a = crfi for some b £ A+ } F(a) = {at £ S : a = cat for some c £ A+ }. Now, suppose w £ A has been written in the form w — Apa and that a = aia2...ak where aj is a minimal. Construct the starting and finishing sets for each aj. If 5 ( a ; + i ) c F(ai) for all i, then we are done since: Suppose 5(OJ+I) C F(a.i). Then, all generators that start the word Oj+i also end the word a». So, for aj £ 5(aj+i), aj e F(a,) suppose aj = fejCj and oij+i = <x,Cj. Clearly, aj = max (ai a;+i) since otherwise there would exist a minimal con-taining a square. Since minimal words are the divisors of A and A does not contain a square this cannot happen. Therefore, ajaj+i is in normal form. Now suppose there exists i such that 5 (a j + i ) F(ai). Then there exists aj £ S(ai+i) such that aj ^ F(ai). Set a'i = aiOj and Oj+i = Gja'i+l. Then is a minimal since it is square free, as is a'i+1. This gives another decomposition a ^ + 1 . Chapter 5. Coxeter groups and Artin Groups 35 Continuing in this way until S(ai+i) C F(a,) for all i, we get the word a written in its normal form. • So we can generalize Thurston's normal form for all Ar t in groups of finite type. Can we then apply this normal form to the finite type Art in groups to construct a public key cryptosystem that works as well as the braid group? Since each finite type Art in group has a different presentation and different fundamental word we should consider each group seperately. 5.3 72(m) Let Am = ( 01,02 '• o\020\.... = o2oio2.... ). »- * * -m terms m terms Let (Ii, I2) be the decomposition Ii = {1} and 7 2 = {2}. Let II' = o\, II" = cr2 and II = 0i02. We know that the Coxeter number for this group is m, therefore we have that the fundamental word, A , is A = p IT™/2 if m is even = p n t " 1 - 1 ) / 2 ]} ' if m is odd. Therefore A = o\020\...02 if m is even * v ' m terms or A — o\o2o-\...o\ if m is odd. m terms Lemma 5.6 (i) o"iA =p A02, o"2A = p A c i ifm is odd, CTIA —p Aoi, o2A =p Ao2 if m is even. (ii) CT~1A = A C T " 1 if m is even, o^1A = A c r J 1 , <TJXA = A f f ^ 1 if m is odd, (Hi) < j jA - 1 = A~xOi ifm is even, CTIA-1 = A _ 1 C T 2 , < r 2 A _ 1 = A~1o\ ifm is odd, (iv) o~lA~x = A~1o~1 ifm is even, erf1 A - 1 = A - 1 ^ 1 , c ^ A - 1 = A - 1 ^ 1 ifm is odd. Proof (i) <7iA = p oi(oi020i...oi) =p 0\{p20\02-• -o~2) —p &°~2 if m is °dd. m terms m terms o~iA =p o\[o\020\...02) —p G\(u2oiO'2...CFi) =p Ao\ i f m is even. m terms m terms o2A =p 02{p\020\...o\) =p Aoi if m is odd m terms Chapter 5. Coxeter groups and Artin Groups 36 02A =p o~i(?\0'20~\---o~'2) =p Ao"2 if m is odd. m terms Parts (ii), (iii) and (iv) all follow from the above. • Let a be a word in Am. Let the starting set and finishing set be defined as before. We want to write a as a = Apa1a2-..ak where at is a minimal for all i. The minimal elements of v4+ are precisely the elements of the form o\oio~\— or k terms <72<7i<72... where k < m. k terms 5.3.1 The Normal Form Let P be a word in Am. We can write P as P = Wla-1W2o--1W3....Wkcr-1Wl where each W* is a positive word. Since A = cri( o"2o"i...<7i) if m is odd m—1 terms G \ = A(a']~1C7'^ "1(7{"1...(T2~1). V ' m—1 terms Therefore, if m is odd, a f 1 = (Q-2O"IO'2---O'I)A~:L. m—1 terms Similarly, Co"1 — (<TiCr2(Ti...(T2)A~1. N v ' m—1 terms Now, if m is even, erf1 = ((T2(Tig2---C2)A~1 m—1 terms and o-jf1 = (cricr2CTi-ffi)A _ 1 . m—1 terms So, we can replace any occurrence of a negative generator by X A _ 1 where X is a positive word. By the lemma, we can move all occurrences of A - 1 to the left so that P is written as P = AkB, where k is an integer and B S A^. We want to write B as a product of minimals. If B is of the form B =p W\ AW2 AW3 then by Lemma 5.6 all occurrences of A can be moved to the left. If B contains no occurrence of A then I claim that B is in normal form: Chapter 5. Coxeter groups and Artin Groups 37 Proof of claim If B contains no occurrence of A then nowhere in B do we have a sequence of (o\o20\...Oi), where i = 1 or 2 depending on whether m is m terms even or odd. Therefore B is of the form B =p WiOjOjW^OkOkWz.... , j, k = 1 or 2 where Wi =p 0\020\.... or Wi —p 020\02.... where n is less than m — 1. n terms n terms Let a i = p WitTj and a 2 = p ffjYi where W2 =p YiY2. Then F (a i ) = a, and 5(a 2 ) = o-j. Therefore, 5(a 2 ) C F ( a i ) . In the same way let a 3 = Y^er^ etc. Then B is a product of minimals such that 5(aj+i) C F(aj) and so B is in normal form. It is known that the conjugacy problem for this group is solved in quadratic time. ([10]). However the security of the cryptosystem is not based on the speed of solving the conjugacy problem. We already know that the published words are conjugate to each other. The security is based on being able to determine the word, a, that conjugates the published word. This problem is presumably much more difficult to solve. 5.4 The Other Artin Groups of Finite Type Firstly, consider the Coxeter group G2. This group is just 7 2(6), and so we have already studied this group. Now consider the other Ar t in groups of finite type. Given a word W £ A, we know that W can be written in the form APB, where p is an integer and B is a positive word. We then need to determine an algorithm which puts B into a product of minimals, jj.\...fik. How do we determine whether or not a positive word a; is a minimal? We know that minimals are divisors of the fundamental word, A . If we construct A for each of the other Ar t in groups of finite type, we see that there are many words which are positively equivalent to A . This means that given a word x, in order to determine whether x is a minimal, we need to construct the following sets: 6 = {W : W = p A } and Min ={fi: W =p pX,W £6,X £ A+}. If x is an element of Min, then x is a minimal. The group Am defined in section 5.3 and the braid group are exceptions: For the braid group we know that minimals are just the permutation braids and we can easily construct the starting and finishing sets for a permutation braid by looking at its product of transpositions. Chapter 5. Coxeter groups and Artin Groups 38 In general, once the set Min has been constructed, we then still need to determine the sets S(P) and F(P) for each P £ Min. To avoid having to do this, we could use an alternative solution to the word problem. This proposed algorithm has quadratic running time. 5.4.1 A n alternative solution for solving the word problem in Artin groups of finite type The following solution the the word problem was proposed by Charney in [7]. This solution has the advantage of being computed in quadratic time. Lemma 5.7 Suppose p,n £ A+ are minimal and let p* be as defined in section 5.2. Then a > n if and only if p*r\ is minimal. Proof Assume p, > 77. Then p = na for some a £ A+. Now A = (p*)p = (p*)r}a. So A > (p*)n. So p*n is minimal. Now suppose that a = p*n is minimal. Then [p*)p = A = aa* = p*na*. So (p*)p = (p*)na*. Cancelling p* gives p = na*. So p > n. • Definition 5.8 Suppose a,b £ A+. We say a is orthogonal to b, written a Lb, if the only element c satisfying a > c and b > c is the identity. Lemma 5.9 Suppose a,b £ A+. Let p = max(a), 77 = max(b). Then the following are equivalent: (i) a Lb (ii) pLn (iii) p*n is in normal form (iv) fj*p is in normal form. Proof (i) (ii) is obvious. (ii) => (i): Suppose p _L 77. Let a = ca\, b = cb\. Let p = max(c). Then a > c > p and b > c > p. Since p = max(a) and n = max(b) p > c, so p > p and rj > c so 77 > p. But p _L n so p = 1. Therefore c = 1. (ii) => (iii): Suppose max(p*n) = p ^ p*. So p*rj = pd and p = p*c for some non trivial c. Now p is minimal and so p*c is minimal (by the previous lemma) and so p > c. Alternatively, p*rj = pd= p*cd for some d £ A+. Cancelling p* we have 77 = cd so n > c. So / i is not orthogonal to 77. Therefore, if p, _L 77 we must have that max(p*r]) = p,* and so p*n is in normal form. (iii) =^ (ii): Assume p* = max(p*rj). Suppose p > c and 77 > c. Then p*rj > p*c and by the Lemma 5.7 p*c is minimal. Therefore we have that p* — max(p*r)) > p*c and so c is the identity. (ii) (iv): Since the relation ± is symmetric, this follows from the equiva-lence of (ii) and (iii). Chapter 5. Coxeter groups and Artin Groups 39 Remark If we set o = p* we have that o* = (p.*)* = p. So the above lemma states that the following are equivalent: (i) o* ± 77, (ii) or] is in normal form, (iii) fj*o* is in normal form. Now, the involution a = A _ 1 a A preserves ordering and so preserves normal forms. Therefore the conditions above are also equivalent to (iv) ofj is in normal form, (v) fj*o* is in normal form. Let a G A+ with normal form p,ifi2---^k where the p^ are minimals. Consider Aka~1 G A. Claim Aka^1 lies in the image of A+ in A. In fact A ^ a - 1 = Ak(n1p2...nk)-^ = Akp^ V f c l i - A ' J V ^ -For k even: A ^ " f c - 1 A / x ^ 1 A . . . A / J 2 - 1 A / x f 1 = A A A t - 1 A - 1 A ^ 1 A . . . A A ^ 2 " 1 A - 1 A M r 1 = Since a A 2 = A 2 a we move all factors of A 2 to the left and get For k odd: A / i - 1 A / / f c - - i ~ 1 A . . . A | T 2 - 1 A ^ i ~ 1 = A M f e 1 A A M f c i : 1 A - 1 A . . . A A / J 2 " 1 A A - V r 1 = A ^ f c V f c - i - ^ V r 1 = A ^ a " 1 . Also, for fc even: Afik~lA/x^iA...Afi2~lAp,^1 = ^ f c*/x f c"_i*.. . /x 2*/Ii*-fc odd: A^l1 Ap^-1 A.-.Afc-1 A^1 = /J f e*/i f e_i*...^2*A«i* Now ii pi = A then /ii* = /Zj* = 1, so there may be some trivial terms in this product. Now, when a is written in normal form, all A ' s occur at the beginning and so all trivial pi* appear at the end of the product. Say pi = A , i = 1 , m — 1 and pi =fi A for i = m, ...k. Let (/xi/u2.../Xfc)* — /xfc*.../tTO* where p-i = pi if i is odd, or pi if i is even. Lemma 5.10 / / pip2---LLk is the normal form for a G A+, then (p\...pk) * is the normal form for A f c a _ 1 . Proof We know that pi...p,k is the normal form for a if and only if pi = max(piPi+i). Therefore we must show that if fiiPi+i is in normal form then Pijii+i* is in normal form. This follows from the remark. Theorem 5.11 Let g G A. Then there exists a unique pair of elements a,b G A+ such that g = b~xa and a ±b. Proof We know that g can be written as g = A~np where p G A+. Let Co be any maximal element of the set { c G A+ : p > c and A™ > c }. This set is finite since the length of c as a word in F(S)+ is bounded by that of p. Let p = c 0 a and A " = cob. Then a l b and g = A~np — b~1c^1coa — b~xa. This proves existence. Now suppose g G A+. lfg = b~1a then bg = a and so a > b. This contradicts orthogonality unless 6 = 1 . Chapter 5. Coxeter groups and Artin Groups 40 A similar argument holds for strictly negative g (as then b > a =>• a = 1). Now suppose g s A and let g = 6 _ 1 a = d~lc with a ± b,c ± d and a,b,c,d non trivial. Let a = aia2...an, 6 = 6 1 6 2 . . .b m , C = CiC2...Cp d=d\d2...dq. Since we have orthogonality there are no factors of A in these products. Suppose m > q. Then Amg = Amb~1a = {b1...bm)*a1...an and Amg = Amd~1c = Am-i(d1...dq)*c1...cp. The right hand sides of both of these equations are in normal form. B y uniqueness of normal forms they must have the same minimal decomposition. The first term of (bi...bm)* is bm* which cannot be A (since this would mean bm = 1) so we must have that rn = q. Therefore n = p,bi = di and Oj = Cj. This proves uniqueness. • A n algorithm exists which puts a word into this normal form in quadratic time (see [10]). So, like the braid group, we have an algorithm which solves the word problem for all finite type Ar t in groups efficiently, and, the conjugacy decision problem is hard to solve. The group A 2 ( m ) appears to be the group in which the word problem is solved the fastest, however, the security of a cryptosystem using this group may be compromised. The next chapter looks at possible attacks to a group theoretic cryptosystem, which enables us to determine exactly which of these groups are suitable. Chapter 6. Ananlyzing the Cryptosystems - Possible Attacks 41 Chapter 6 Analyzing the Cryptosystems - Possible Attacks Since the proposal of a group theoretic protocol for key exchange, work has been carried out on the security of the system and any possible attacks. As yet, the cryptosystem of Chapter 3 has not been analyzed completely in terms of security. However, research has been carried out on possible attacks to the cryptosystem proposed in [2] and Chapter 4. It is thought that such an attack could also be used against the protocol in Chapter 3. 6.1 The Length Attack This attack was described by Hughes and Tannenbaum in [16]. The attack is based on having a canonical representative of each string relative to which a length function may be computed. Let x be an element in some finitely generated, non-abelian group G. The length of x, l(x), is defined to be the length of the shortest word expressing x. Given x in G, we say that y is reducing with respect to x if l(y~lxy) < l(x). The length attack is based on these reducing strings. Let a £ SA = (ai , • •••,am) be the private key. Let a - 1 6,-a and bj, j = 1, . . . ,n be publicly given. Assume the generators of SA have lengths large relative to a. Let 7j = a _ 1 b , a . The idea is to compute l(af 1 7 j a ? 1 ) , i = 1, . . . ,m repeatedly. If ^ is a reducing string with respect to jj then and one has found a correct factor of a with a certain probability which will depend on the lengths l{a,i),i = l , . . . . , m Chapter 6. Ananlyzing the Cryptosystems - Possible Attacks 42 If the lengths of the a; are large then there is the greatest probability of a reducing string being formed which can be used to gain information about a. In order to analyze the speed of the attack, we need to calculate an upper bound for the difficulty. Let a be made up of m factors combined in d ways, say a = a,ilai2...a,id and each of the generators of the subgroup SA is used in a. Assuming Z(OJ) is large, then a substantial reducing string can be formed by joining a small number of these factors together. We should consider the inverse of each factor, hence we should consider 2m factors. Suppose we need k factors to create a reducing string. Then we have (2m) k factors to try. If we repeat this process n times on each public conjugate a~lbja, j = 1, . . . ,n, then combining all these steps brings us to n(2m) f c operations. The authors of [15] conjecture that this will be sufficiently reliable to removing a given aj. We can now do this d times, bringing the total number of operations to dn(2m) f c. This attack is polynomial in n and linear in d. However, if we set k = 1 then, if the individual factors are not significant, this attack will not work. On the basis of this evidence, Anschel, Anschel and Goldfeld modified their key agreement protocol to include the following parameter recommendation: The braid index, n, should be at least 80, and the subgroups, SA,SB, should be generated by 20 elements, ie SA = (ai, a 2 , a 2 0 ) , S B = {h,b2, ho) where each a; and bj is the product of 5 to 10 Art in generators. Each set of public generators SA,SB should involve all of the Ar t in generators of Bn. Given that a length function can also be applied to words in any finite type Ar t in group, such an attack is also feasible on a cryptosystem which uses another Ar t in group of finite type. This means that we can eliminate the use of most of the other Ar t in groups of finite type. There are only three Art in groups of finite type with more than 80 generators: the braid group, and the groups whose associated Coxeter groups are Bn and Dn. 6.2 Linear Algebraic Attack Recall from Chapter 4 that the exchanged key, K, can be put into its coloured Burau matrix form. Recently, S.J. Lee and E . Lee proposed a possible linear algebraic attack to this cryptosysytem. Recall, an element of CBn is a pair ( M , a), where M is a matrix with entries in Fp, the finite field of p elements, and o is the induced permutation. Let Mx and ox correspond to the coloured Burau matrix and permutation associated to the word x. Then (Ma,oa)(Mb,Ob) = (Ma • oaMb,cfaOb) and ( M a . a . J - ^ ^ M - 1 , ^ 1 ) -In [2], the following parameter recommendations were suggested: Chapter 6. Ananlyzing the Cryptosystems - Possible Attacks 43 In order to choose distinct and invertible elements T\, . . . ,T„ one must choose p > n. One can take p < 1000. As mentioned before, the two publicly known subgroups should be generated by 20 elements and each of the aj,6j should be the product of 5 to 10 Art in generators. The private keys a and 6 should be products of 100 public generators. It is also suggested in [2] that the induced permutations of a and b should be sufficiently complex since if pure braids are used, one can attack the key extractor, E, using linear algebraic methods. However, in [19], it is shown that linear algebraic methods can be used to attack the key agreement even for more complicated braids. Suppose Alice chooses a private key a. Then the pair of m-tuples of elements of the braid group SB = {bi,b2,...,bm),(a'1b1a,a~1b2a,...,a~1bma) are made public. Can we find a in polynolmial time (in the input length)? Using linear algebraic methods, Lee and Lee propose an attack that finds a list of all such solutions, a, in polynomial time. In fact: Theorem 6.1 If the induced permutations of a and b are known then we can construct four lists of matrix equations in GLn-\{Fp) such that computing the matrix part of the shared key is reduced to solving each of these lists. Proof Let yx denote the element in CBn corresponding to the braid word x. Recall the shared key, K, is a~1b~1ab. Then, Va-ib-iab = ( M a , 0 - a ) - 1 ( M 6 , C r 6 ) - 1 ( M a , ( T a ) ( M b , ( T b ) . = ( ( a - 1 M - 1 ) ( a J 1 a 6 - 1 M 6 - 1 ) ( a j V 6 - 1 M 0 ) ( f f - V ^ V 0 M 6 ) , o r - 1 e r 6 - 1 a 0 a 6 ) . So the matrix part of the shared key is the product of the four matrices evaluated at (ti,...,tn) = (rj, . . . , r n ) : (CTa 1 Afa j ) , ((J- 1 c r - 1 M f e " 1 ) , fc^Ma), ( a " 1 O A M B ) . Consider (cra 1ab 1Ma)(ru . . . , r„ ) . Assume that the permutations aa and are known. 1) Choose x in SB such that x is a pure braid. 2) Compute c = a~xxa. Then c is also a pure braid. 3) Since xa = ac and yxa = (MX • Ma,aa),yac = (MA • (aAMc),aa) then {a-^Mx){azWMa) = ( ^ V ^ X ^ S " " ^ - ^ ) . 4) Let X = (aa1ab 1Mx)(T1,...,T71) and C = {a~lab IaAMC)(T1, . . . , T „ ) . 5) Repeat this process for N pure braids x. Then we get a system of equa-tions XjA = ACj for j = 1 , N . Then ( c r ~ 1 ( T b _ 1 M a ) ( T i , . . . ,T„) is a solution in GLn-i(Fp) to XjA — ACj,l < 3<N. Similarly, we can generate a system of equations for the three other matrices in the matrix product. • Chapter 6. Ananlyzing the Cryptosystems - Possible Attacks 44 We can generate the pure braid x by choosing a word v at random and letting x = vq where q is the order of the induced permutation of v. However, we do not want this order to be too large so by choosing v to be a product of three 6;'s, the corresponding induced permutation will be a product of 15 to 30 transpositions and so its order is small. If y is any other word, then y~lxy is also a pure braid, so x can be used to generate other pure braids. How hard will it be to generate and solve these lists? It is easy to determine oa and o^ since two permutations are conjugate if and only if they have the same cycle decomposition. The system of equations XA = AC can be considered as a system of homogenous linear equations in the entries of A. To solve this system we can use the polynomial time deterministic algorithm of Christov, Ivanyos and Karpinski, as mentioned in [19]. Therefore, the difficulty in this attack lies only in the number of solutions. By [19], the number of solutions is exactly the cardinality of the subgroup H f c i Cent(bi), where Cent(bi) = { j £ G\gbi = b^g} is the centralizer of bi. The average cardinality of this subgroup when G is either Sn or GLn-\(Fp) is not known, but the authors of [19] conject it is not large. 6.3 Conclusion Whilst evidence is by no means conclusive, it does appear that the braid group cryptosystem is not as secure as originally thought. Without solving the hard problems that the security of the cryptosystem was based on, we can see that the cryptosystem is vulnerable to attacks using different methods. Whilst the length attack is only probabalistic, research is being carried out to improve such an attack. It seems reasonable to assume that such an attack can be applied to the cryptosystem of [18]. At this point the authors of [16] are statistically testing the length attack on several groups including the braid group and Ar t in groups. Further study is also required to determine the cardinality of Cent(bi). If, as the authors of [19] suggest, this is not large, then the braid group cryptosystem based on the coloured Burau matrix is certainly not very secure. Bibliography 45 Bibliography [I] I.Anshel, M . Anshel and D. Goldfeld, An algebraic method for public-key cryptograhy, Mathematical Research Letters 6 (1999) 287-291. [2] I. Anshel, M . Anshel, B . Fisher, D. Goldfeld, New key agreement pro-tocols in braid group cryptography, Topics in cryptology—CT-RSA 2001 (San Francisco, C A ) , Lecture Notes in Comput. Sci., 2020, Springer, Berlin, (2001) 13-27. [3] E . Art in , Theory of Braids, Annals of Math., 48 (1947), 101-126. [4] J . S. Birman, K . H . K o and S. J . Lee, A new approach to the word and conjugacy problems in the braid groups, Advances in Math. 139 (1998), 322-353 [5] E . Brieskorn, K . Saito, Artin-Gruppen und Coxeter-Gruppen. (German) Invent. Math. 17 (1972), 245-271. [6] R. Charney, Artin Groups of Finite Type are Biautomatic, Math. Ann. 292 (1992), 671-683. [7] R. Charney, Geodesic Automation and Growth Functions for Artin Groups of Finite Type, Math. Ann. 301 (1995), 307-324. [8] R. Corran, On monoids related to braids, Thesis, The University of Syd-ney, May 2000. [9] P. Dehornoy and L . Paris, Gaussian groups and Garside groups, two generalizations of Artin groups, Proc. London Mathematical Soc. 79 (1999), 569-604. [10] P. Deligne, Les immeubles des groupes de tresses generalises, Inventiones Math. 17 (1972), 273-302. [II] W . Dime and M . E . Hellman, New directions in cryptography, I E E E Transactions on Information Theory, 22 (1976), 644-654. [12] T. ElGamal, A public key cryptosystem and signature scheme based on discrete logarithms, I E E E Transactions on Information Theory, 31 (1985) 469-472. [13] E . A . Elrifai and H . R. Morton, Algorithms for positive braids, Quart. J . Math. Oxford 45 (1994), no. 2, 479-497. [14] D . Epstein, J . Cannon, D. Holt, S. Levy, M . Paterson and W . Thurston, Word processing in groups, Jones and Bartlett, 1992. [15] F . A . Garside, The braid group and other groups, Quart. J . Math. Oxford 20(1969), no. 78, 235-254. [16] J . Hughes and A . Tannenbaum, Length-based attacks for certain group based encryption rewriting systems, Institute for Mathematics and Its Applica-tions, Minneapolis, M N , Preprint number 1696, (2000). [17] Humphreys, J . E . , Reflection groups and Coxeter groups, Cambridge University Press, 1992, cl990. Bibliography 46 [18] K . H . Ko , S. J . Lee, J . H . Cheon, J . W . Chan, J . Kang and C. Park, New Public-Key Cryptosystems Using Braid Groups, Crypto 2000. [19] S. J . Lee and E . Lee, Potential weaknesses of the commutator key agree-ment protocol based on braid groups, E U R O C R Y P T 2002. [20] H.Morton, The Multivariable Alexander Polynomial of a Closed Braid, Contemporary Mathematics 233, Amer. Math. Soc, (1999), 167-172. [21] K . Murasugi and B.I . Kurpita, A study of braids, Kluwer Academic Publishers 484, (1999). [22] R. L . Rivest, A . Shamir and L . Adleman, A method for obtaining dig-ital signatures and public key cryptosystems, Communications of the A C M , 21 (1978), 120-126.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Braid groups, Artin groups and their applications in...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Braid groups, Artin groups and their applications in cryptography Webster, Catherine 2003
pdf
Page Metadata
Item Metadata
Title | Braid groups, Artin groups and their applications in cryptography |
Creator |
Webster, Catherine |
Date Issued | 2003 |
Description | The aim of this article is to show how the braid groups can serve as a good platform to enrich cryptography. Braid groups are useful to cryptography for a number of reasons: (i) the word problem is solved via a fast algorithm which computes the canonical form which can be efficiently handled by computers, (ii) an algorithm which computes an unfaithful matrix representation for a braid exists, which is also efficiently handled by computers. Introduced are two protocols for asymmetric key exchange based on the braid groups. The braid groups are an example of a larger set of groups, namely, the Artin groups. This raises the question as to whether the other Artin groups are useful in public key cryptography, or whether the braid group is unique. Outline: Below is an introduction to public key cryptography and the key agreement protocol proposed in [1]. Chapter 2 is an introduction to the braid group. Chapter 3 discusses the canonical form for words in the braid group, and how this form can be used for key exchange as in [18]. In Chapter 4, the braid cryptosystem based on the coloured Burau matrix, as in [2], is discussed. Chapter 5 gives an introduction to Artin groups and Coxeter groups, and discusses possible cryptosystems using other Artin groups of finite type. Finally, in Chapter 6, I will discuss various attacks to the proposed systems and draw some general conclusions on the braid and Artin groups applications to public key cryptograhy. |
Extent | 1982228 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-10-28 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0080070 |
URI | http://hdl.handle.net/2429/14279 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2003-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2003-0321.pdf [ 1.89MB ]
- Metadata
- JSON: 831-1.0080070.json
- JSON-LD: 831-1.0080070-ld.json
- RDF/XML (Pretty): 831-1.0080070-rdf.xml
- RDF/JSON: 831-1.0080070-rdf.json
- Turtle: 831-1.0080070-turtle.txt
- N-Triples: 831-1.0080070-rdf-ntriples.txt
- Original Record: 831-1.0080070-source.json
- Full Text
- 831-1.0080070-fulltext.txt
- Citation
- 831-1.0080070.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080070/manifest