BRAID GROUPS, ARTIN GROUPS A N D THEIR IN C R Y P T O G R A P H Y APPLICATIONS by CATHERINE WEBSTER B.Sc.(Hons) University of Leeds, 1997 A THESIS SUBMITTED IN PARTIAL 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 ED E G R E E O F MASTER OF SCIENCE in T H E F A C U L T Y O F G R A D U A T E STUDIES Department of Mathematics We accept this thesis as conforming ^to the\^e|[uire9) standard T H E UNIVERSITY O F BRITISH 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 protocols for asymmetric key exchange based on the braid groups. The braid groups are an example of a larger set of groups, namely, the A r t i n groups. This raises the question as to whether the other A r t i n 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 A r t i n groups and Coxeter groups, and discusses possible cryptosystems using other A r t i n 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 A r t i n 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 K e y Cryptosystems ... 1 1.1 What is a Public K e y 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 K e y 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 W h y Does This Cryptosystem Work? ... 20 3.4.1 How Fast is the Cryptosystem? ... 20 3.4.2 How Secure is the Cryptosystem? ... 20 iii 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 A r t i n Groups ... 30 5.1 What are A r t i n Groups and Coxeter Groups ... 30 5.2 The Word Problem ... 31 5.2.1 Constructing the Normal Form ... 34 5.3 J (m) ... 35 5.3.1 The Normal Form ... 36 5.4 The Other A r t i n Groups of Finite Type ... 37 5.4.1 A n Alternative Solution for Solving the Word Problem in A r t i n Groups of Finite Type ... 38 2 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 - aoT 1 ... 7 Figure 4 - Standard Inclusion ... 8 Figure 5 - Braid Projection ... 8 Figure 6 - cr and a~ x 4 ... 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~^ <j\o~^ (j\(j~^ oz ••• 24 v V Figure 12 - UjO"j = o^Oi ... 25 Figure 13 - Braids (i) and (ii) ... 26 v Acknowledgements I would like to thank D r . Dale Rolfsen, my thesis supervisor, for his guidance, encouragement and generous financial support throughout my work on this thesis. I would also like to thank D r . 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 l Cryptosystems Chapter 1 Introduction - Public Key Cryptosystems 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 — {E : e E K} is a family of functions E : M —> C. A n element of e is called an encryption function. 5) D = {D : d e K} is a family of functions Dd : C —> M. A n element of D is called a decryption function. e e d Chapter 1. Introduction - Public Key 2 Cryptosystems 6) For each e e K, there exists d G K such that D (E (m)) d e = 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 E l G a m a l [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 3 Cryptosystems 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 ) SB = ( &i, K ). Step 1 m Alice chooses a secret element (private key) a £ SA, say a = a^a^ and computes, rewrites, and transmits the collection of elements 1 1 n to Bob. Bob then does the same: chooses b € SB, say b = b^b^ 6 a i & , b~ a,2b, _1 k , a~ b a a~ b\a, a~ b2a, l at bj, and sends , b~ a b, 1 1 m 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~ a-i ....a,i b = l 1 k (b- a b) b ab. l ik _1 Likewise, Bob can compute a~ ba. l Step 3 Alice knows both a and b~ ab so she can compute the key l K = a^b-i-ab. Bob knows b and a~ ba, so he can compute 1 K = a- b- ab=(a- ba)- b 1 1 1 1 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~ bx. l 5 Chapter 2. The Braid Group Chapter 2 The Braid Group The braid group was first defined by E m i l A r t i n in [3]. 2.1 Geometric definition of a braid Imagine a cube with n points labelled Qi, .... Q on the top and n points labelled Q[, Q' on the base. For neatness we express these points in specific coordinates: n n *3l ( 2' n+T' •" * 5 ( 2> n+T> Qi = ( i ^TT> 0), ... Q' = ( I , 0). = n = n Therefore, is directly underneath Q j . 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 F i g . 1). Two braids in a cube, whose endpoints we keep fixed, are said to be equivalent 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 Q I \/ / \ / J1 Qi Q Qi 3 / \ \ / / / \ Q 2 Qi Qz 2 Qs f / \ 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 B , 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) n Qi Q2 Q 3 a Qi Q2 Figure 2 : a(3 Q3 7 Chapter 2. The Braid Group Similarly, we can define the product /3a. Note, in general a/3 is not equivalent to f3a. This product makes B 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) n Qi Q2 Qz Q'x Q'2 Q'3 Figure 3 : cta~ l There is a standard inclusion from B to B i obtained by adding points Qn+i and Q' and connecting these points with a vertical line (see F i g . 4). Hence we get a directed system of groups B C B2 C .... C B^ where B^ denotes the direct limit of the B . n n+ n+1 x n Chapter 2. The Braid Group / Q2-. Ql (> > Qn-lQn > < > / / Ql Q2-- <» 4 > Qn-lQn Qn+1 ( > <> ( > <> p / < > Qi / / <» ( » Q -- Q U Q ; Qi 2 Q i - . Q U l Q ; Figure 4: Standard inclusion 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 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" , where string i crosses behind i + 1 inCTjand string i crosses in front of string i + 1 in o"" . (See F i g . 6) i+ 1 1 Q'n+1 Chapter 2. The Braid Group 9 i + 1 i i+1 i Figure 6: <Ti and <r i 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 formCTjor o ^ . B y definition of the product of braids we can decompose /3 into the product of the ctj's and c r ^ ' s . Hence B is generated by the elements U\, , Cn-i1 n 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~ 0-iOi+1 OiOj = OjGi i+1 Figure 7: Braid relations If we add the relations of = e, for all i, then we get a presentation for the symmetric group S . Hence S is a quotient group of B . The natural projection from B to £ „ fits in a short exact sequence 1 •P > B > S 1 n n n n > n n n Chapter 2. The Braid Group 10 where P 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. n Chapter 3. Method 1 : Canonical Forms 11 Chapter 3 Method 1: Canononical Forms If there exists a feasible algorithm to put every element of the braid group B 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. n 3.1 Garside's Normal Form Let B n 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= B P 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 o o \02<Jz2 Chapter 3. Method 1 : Canonical Forms 12 The Fundamental W o r d A Suppose l < r < s < n — 1 and let the word o o \ o , where all the generators from o to o inclusive occur in ascending sequence, be denoted by K c )Let I I be the word [p\ o ). Let r be the mapping of B onto itself given by r r r+ s s s S s n r(o-i) = cr„_j. B y inspection of the relations r extends to an automorphism of B , and we will call this automorphism reflection in B . We also define a reversing antiautomorphism rev: B —> B , defined by rev{ui) = Oi. This has the effect of reading the reverse word i n the braid generators. Let A be the word defined as A = IL.IL._x III. In B , let A denote the fundamental word n n n n r r n A = A n _ i = (0x02 CT _i)(-in (^10" ) (-1). CTn-2) 2 2 Theorem 3.3 (Garside, [15]) In B , every word W can be expressed uniquely in the form A A , where m is a maximal integer (possibly negative) and A is a positive word. n m In order to prove the theorem, we need the following lemma and theorem. Lemma 3.4 In B there exist positive words X ,Y n r such that r Proof B y definition A = (ai02....o- -i)(oi02....0n-2)----(o-io )(oi). Therefore, A = Y\0\ where Y\ = ] ! „ _ ! . . . . n . Now consider II <T _i, where s < t. Then n 2 2 t s II (T _i = t (0i02....0 )0 -\ s t s = (o-iO-2- — O~s-2)0s-10s{<7s+l~~0t)o~s-l =p (CiCT2----0's-2)l7'«-lC CT _i(CT i....O-t) s s s+ — (o a ....o - )o o _io (o i....o ) =p 0- (oiO2....O -2)0- - O (o i....O ) = o (oi....o ) = o U. Now, if / ( o - j , O j ) is any word involving the generators Oi, a i , . . . , Oj only, then, by the above n /(<7l,0- , . . . , 0 - _ i ) = f(02,0 , ...,O )Uf Let o be any of the generators o , 03, a -\. Then denoting n _ n _ . . . . i i i = (o o ....o -. )(oio- ....o-t- )--{o-i) by f{oi,02,--,o -{) we have P 1 2 s s s 2 s s s s 1 s s+ t s s+ t t s t i + t 2 t t 3 2 t 1 t 2 1 t n 2 t 1 2 2 t A = n _i....ll illt/(ai,c72, n = p = p ,at-i) f + n _ ....n i/(<T ,(T3,....,(7 )n J1 1 2 t+ t t n _i....n i/(o- ,a ,....,CTt)(CTiCT ....a-t_i)cr n t+ 2 3 2 t Chapter 3. Method 1 : Canonical Forms 13 Therefore, there exists a word Y such that r Y = n _ i . . . I I i / ( o - 2 , ( J 3 , ...,CT .)(CTiCr2—0 r-l),r = 1, —™ ~ 1, with the property A = Y o . Now set X = rev Y . Then o~ X — o revY = rev(Y^.oy) = reuA. I claim that rev A = A : Clearly, revAi = A i . B y induction, assume true for the case A = revA . Then revA +i = rev((o~io~2----o~t+i)At ) = revA rev{a o- :..at+i) = A {a ...a Oi) = (CTl...CT )cr i(c7i...Cr _i)CT (...)((TiCT2)CT3(c7i)cr2(cri) Therefore rev A = A and the proof is complete. • r r p n r+ T p r r r r r r r r p p t t 1 p 2 t p t t p t+ t t t+1 2 t p Theorem 3.5 In B , for any integer m, (i) PA = A P, PA = A T(P) for all positive words P, (ii) QA = A Q, QA = A r(Q) for all words Q, where T is the mapping from B onto itself given by r(ai) = a -in 2m 2m 2m+1 2M+1 p p 2m 2m 2m+1 2m+1 n n Proof Firstly, consider o-\A . We have o-\A = a i n n _ i . . . . i i i = er n (cr er ....oy_i)(cri....ov_2)....0-i = CTin ((Ti(T2----0" -l)A _2 Now, I claim o H = II (7 _i for 1 < r < t < n — l since a Il = a (aia ....o- ) r r r 1 r r 1 2 r r t p t r r r r t r 2 t = 0- {p\0-<i----0- -2)0~r-\Or{Pr+\-~-at) =p (0-i0-2....O- -2)0- -l0- O-r-l{o~r+lO~ +2----O~t) =p (CTiCT2....CT _2)Cr-lCTr(CTr+l Y+2-"-< «)°y-l = n (T _i r r r r r r 0 J r t r as required. Therefore, eriII .(<7i<72....ay_ ) A _ 2 = <7i((72....<7 .)n .A _2 =p n I I _ i ( T A _ 2 —p Y\. T\. —\Ar—20~r —p A 0~ . Therefore, a A = (TiA„_i = A„_iCT _i = A r ( c ) . Now consider when r = 2 , 3 , n — 1. ayA = c r n _ i n _ 2 . . . . n i = O- .(CT (T2....(T _i)(criO'2....0r„_2)....(CTlCr2)(o-i) = cr ii _in _2....n _ -+i(ri _j.n _ _in _ _2....ni) = (T .Il _iIIn-2"--n _r-(-l A „ _ = n _ i . . . . n „ _ i O " i A _ (by repeated application of the claim) ~p - f f n — 1 — A n — r ® ~ n —r • Aa i.e., cr A = AT(a ), proving part (i). Now (i) a' A = AT(CT .)- , (ii) oy A = A T(CT .), and (iii) o ^ A " = A - r ( < r . ) - , all follow from the above and the definition of r , proving (ii). T r 1 r r r p ± p n r T n p 1 T 7 1 1 T n n n n _1 1 n r + r 1 r r r n n n - r n 1 r 1 7 1 n 7 p 7 r r r r r n n r r n r r 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 = Wx = A A 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^..., Oj aj ...., 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 N . Then the corresponding word, which is uniquely defined, is called the base of A, denoted A'. For example, consider the braid (3 = O1O2O1O3 = 020\0iGz = 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 f p p 1 2 s p p aiO20~iO . 3 Then, by setting W = A A', we have a unique expression for W. Now let W be any word i n B . We can write W as W EE W o- W o- ....a- W where each Wj is a positive word (possibly empty) and Oi is a generator. For each o we have, from Lemma 1, that there exists a positive word X such that X — A therefore a' = X A~i So we can write W as W = WiX A~ W Xi A~ ....W X A~ W i Moving the factors of A to the left using Theorem 3.5, we have W = A~ P where P is a positive word. From above, we can write P as P = A A. Therefore, W = A ~ A = A A. 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 A A = A B. Let q < p and let p — q = t, where t > 0. Then, since A A = A B we have that A A = B. l p n 1 l 1 1 2 s+1 k ik ik s ik p 1 lk 1 il - 1 2 2 1 S t t p s P q P q 1 1 s i3 s+ Chapter 3. Method 1 : Canonical Forms 15 From Garside ([15] Theorem 4), we have that in B if two positive words are equal, then they are positively equal. Therefore A A = 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 = B. n 1 p p 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 S via the canonical map B —> S . n n n Permutatation Braids Denote a permutation 7r in S , 7r(i) = hi, by ir = bxb ...b . 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 f3 , with pemutation ir = 321, are shown below. n 2 n 2 Figure 8: Permutation Braids Clearly, if two braids, /?i and f3 , 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 P induce the same permutation on S 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. 2 : 2 n Chapter 3. Method 1 : Canonical Forms 16 The fundamental braid, defined earlier, is the permutation braid corresponding to the permutation ir (i) = n + 1 — i. n Definition 3.6 For o positive word P, we define the starting set, 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 }. S(P), 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 /?. B y 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 - ( i + l ) }. 1 Theorem 3.9 (Thurston [14], Elrifai-Morton [13]) For any W £ B , there is a unique representation called the left greedy canonical form, as W = A AiA ....A , where k is an integer, A\, A e 5+ \ { e, A }, where AiA 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. n k 2 p p i+ 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 = A o - _ j n Therefore, given a word W £ B we can replace any occurrence of o~ by o~ = A~ Wi (property (i)), and then collect all occurrences of A to the left using property (ii). Therefore, we can write W = A P, where P £ B + . We want to write P as a product of positive permutation braids. x n l 1 - 1 k 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\ [(iii) OiOjOi if \i-j\ = Lemma 3.11 (Garside's Lemma) [15] Let P=aiP\ P non empty. Then there exists P such that P = omitted) 2 3 > 2 l. = o-jP with Pi and (a * aj)P •. (Proof 2 t 3 Lemma 3.12 Let A G S+. Then a A G 5+ */ and only if i S(A). t 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 = A P, 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~ B. Set A\ = Aoi (G by the remark following Lemma 3.12). Then P = AoiO^B = A\B . 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 = A B and S(B ) C F(A ). 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(B ) 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 = CoiB 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". q l X m m m m m 1 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(a *a )B"'. B y 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\. i i 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 Ao £ 5+ and so i <£ F(A). However, B — QP so i £ S(B) and so the factorization P = AB cannot be left weighted. Therefore, A\ = A and B = P . Now let P = A t 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 = A A A ...A so that W = A A ...A , where k = q + r. • t X x r k 1 2 p 1 p The Algorithm Suppose we have a braid word W £ B written in the form W = AW which we have computed by replacing all o~ s with A~ Wi. Below is an algorithm which puts the word W into its left weighted canonical form. n S x, l Input: A list of elements of S with a table of products of each 7r £ S 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). n A braid word W = BiB -:B , 2 p n where B € 5+. t Initialization: k = 1. Step 1: If k = p then S T O P Step 2: If 5 ( ^ + 1 ) C F{B ) then G O T O S T E P 8 Step 3: If S(B +i) £ F{B ) then G O T O S T E P 4 Step 4: Select j € S{B ) with j £ F(B ). Let OjB' = Step 5: B : = B Oj Step 6: B : = 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. k k k k+1 k k+1 k k B . k+1 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 B , of Bi (= B ). The subgroup Bi is generated by <7i, .... ,CT;_i, and B is generated by 07+1, .... , c r ; _ . The key point of these two subgroups is that for a £ Bi, b £ B , ab = ba. Now consider the function /: Bi x Bi —» S ; x B ; + given by f(a,x) = (area , x), where a £ Bi, x £ Bi . This is a one way function since we can easily compute axa^ given a and x, but given the pair (axa" , x) there is no known algorithm to find a. In fact a may not even be unique. r +r n r +r 1 r +r + r r -1 +r 1 1 The K e y Agreement Choose integers / and r and a braid x £ Bi . These are published. Now A(lice) chooses a word a £ Bi and computes y\ — axaT . A then sends y\ to B(ob). B chooses a word b £ B and computes y = bxb" . B then sends y to A. Alice receives y and computes K = ay a~ = abxb~ a~ . Bob receives y\ and computes K = by\b~ = baxa^b" . We use this key agreement to construct a new Public K e y Cryptosystem. +r 1 1 r 2 2 l 2 x l 2 x 1 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 space. +r —> {0, l } fc be a hash function from the braid group to the message 1) K e y Generation Alice chooses a £ Bi at random and computes y = axa~ . Alice then sends the public key (x, y) to Bob. x 2) Encryption Let m be a message in {0, l} . Bob chooses b £ B at random. Bob then computes c = 6 x 6 and d = H(byb~ ) 0 m, where 0 denotes pointwise vector addition (mod 2). Bob then sends the ciphertext (c, d) to Alice. k r _ 1 1 3) Decryption Alice computes # ( a c a ) 0 d = H^ca' ) H(baxa^b- ) 0 m = m. So the original message is retrieved. - 1 0 1 1 0 H[byb' ) 0 m = 1 H(abxb- al 1 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 £ B . (i) For a positive word W of length I, the left canonical form of W can be computed in time 0(l n log n) (ii) Let U have left canonical form A a\...a and V have left canonical form A bi...b . Then the left canonical form of UV can be computed in time 0(pqn log n) (Hi) Let U have left canonical form A Ai...A . Then the left canonical form of can be computed in time 0(pn). n 2 u p v q u p 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- ,H(baxa- b- )® m) they could compute a from axa~ or b from bxb~ . However, if we are given a pair, (x,y), of braids in B[ such that y = axa 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~ does not have a unique solution a £ Bi , 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 = A Ai...A and check whether y — axaT . However, this brute force attack is of no use since: l l 1 l l -1 +r x +r u 1 p Theorem 3.15 ([18]) The number of n-braids of canonical length p is at least (l^\\) . p Proof Since L ^ ] = 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+: 2 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 S —» S and S —> T. Since these functions are not necessarily surjective, | 5 | > r! and | T | > H . r r Chapter 3. Method 1 : Canonical Forms 21 Consider a permutation n G S - Let a canonical factor A G S be constructed by defining the corresponding permutation n' G S = 5 2 r + i by r n r 27r(i) + 1 for 1 < i < r 7c'(i) = < 1 /or i = r + 1 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. I 2(i - 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' (2i) > r + 1 and 7 r ' ( 2 i + 1) < r we have that 2i G F(A). Therefore, F(A) D {2,4,....,2r} Now, for a permutation n G S , 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. _1 _1 r 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*~ {i) > -K*~ (i + 1) for 1 < i < r since = 2r-2i + 3 and T T * - ^ + 1) = 2r - 2i + 1. Therefore {1,2,...,r} C F ( A ) . We have constructed injective functions S —> 5 and 5 —» T and so | 5 | > r! and \T\ > r\. B y 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 ) n-braids of canonical length p. • l l 1 r r 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 m , and the corresponding ciphertexts are (ci, d-i) and (c , d ), then m can be deciphered from ( m i , di, d ) since di = H(byb- ) 0 m i d = H(byb' ) © m . Therefore, Hibyb' ) = m 0 d = m © d and so m 0 rf © rf = m 0 d 0 d = m . 2 2 2 2 2 1 1 2 2 1 x x a 2 x 2 2 2 2 2 2 Another way an adversary may try to decipher a message is by using a mathematical solution to the conjugator problem. Garside, Thurston, Elrifai-Morton and Birman-Ko-Lee have all published solutions to the congugacy problem i n the braid group. However, their solutions do not find the word that conjugates two words. Chapter 4. Method 2: Group Actions 23 Chapter 4 Method 2: Group Actions We now discuss another method in which braids can be used in a Public K e y 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 £ B by *i, t , t by putting, at the bottom, a label tj on the string which ends at the point Q'j. n 2 n For example, let f3 = o~\o~ o~\o G\0~ O~Z- (See F i g . 11). l 2 l 2 L 2 Chapter 4. Method 2: Group Actions t\ t 2 24 t$ £4 Figure 11 - /3 = (TicrJ oio^ oiovT 03 1 1 1 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 undercrossing string. This gives, B (ti,t , ...,t ) = n U i C ^ r K ) ) * where a is the label of the undercrossing string at crossing r, counted from the top of the braid. 6 0 r 2 n - Chapter 4. Method 2: Group Actions 25 So for example, when ft = 0\0 oio aia o- , the labels ai,..., a are ti, *4, *2, t\i t$, t , *4 respectively and Bp is the 3 x 3 matrix product l 1 2 1 2 2 3 r 2 4.1.2 The Coloured Burau Matrix satisfies the braid relations In B we knowCTjCTj= OJCTJ for — > 2 and OiOjOi = OjCJiOj for Consider the relation CTJIX, = o^o* (see F i g . 12). = 1. n Figure 12: aiOj — a^Gi The corresponding Coloured Burau matrix forCTiCr,is / 1 0 ... o ... o 0 0 0 0 1 if 0 1 1 0 0 Ci(t )Cj(t ) — r p (I 0 0 1 \ 0 ••• 0 •••0 ••• 0 0 0 0 tip 0 0 0 0 0 0 0 t 0 0 p 0 0 0 \ 0 0 0 0 0 1 / 0 \ 0 0 ••• ••• 0 0 0 0 0 0 -tp 1 0 0 1 / / 1 0 0 1 •••0 ••• 0 0 1 0 0 0 0 0 tp 0 0 — Cj(tp)Ci(t ), r 0 0 tp 0 0 0 0 0 0 0 \ 0 0 0 0 1 1 0 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 F i g . 13). Figure 13: Braids (i) and (ii) Consider (i). We get Bp = C3(t5)C4(t )C (t4)Ci(t2) 5 1 0 0 1 0 0 0 5 -h 0 1 1/ \ 0 5 5 0 1 0 0 >0 0 0 0 1 1 0 1 0 0 2 0 0 0 0 / = C (t4)C (t5)Ci(t2)C4(t5) 0 0 "*2 1 0 0 1 -t 0 0 ts 3 'I u -uJ -t J A 4 0 E -h —t t (ii) Now consider Bp 1 \ SI 0 0 0 h t^ti 0 0 0 1 0 0 0 1 0 0 t - i 0 0 \0 0 1 1 0 fl °\ 0 0 i 3 5 0 \0 ts 0 0 0 0 -ts £5^4 —£5*4 0 1/ 0 0 0 1/ z 1 0 0 \0 0 1 0 0 0 0 0 1 0 *5 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. 0 \ 1 Chapter 4. Method 2: Group Actions 27 Firstly, consider the permutation n £ S 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. A s 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- CT CTICT S (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. n w 4 3 e e t 4 4.1.3 The Coloured Burau Group Suppose we are in B , so we have generators o~i, o -\. 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, y -i generate a group CB , the Coloured Burau group. A n element of CB is of the form (M,cr) where M is an (n — 1) x (n — 1) matrix whose entries are polynomials in £1,..., t , and o is a permutation in the symmetric group S Multiplication of two ordered pairs (M,cr), (M',o') in CB 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, t appearing in M' by the permutation o v i a o(ti) — t (iy There is a natural 1-1 correspondence between elements /3 of B and CB which yields the coloured Burau matrix of /3. n n n n n n n n n a n n Example Let w — O4O3O1O4. 0 0 0 0 0 0 1 0 u \0 0 1 % tt 3 4 ,(45) 4 °\ 0 0 -ts 1 -t t4 0/ 0 0 0 1 0 °\ 0 *3 0 0 1 1/ 1 \0 -t J 0 3 f ,(354) 0 ,(34) Chapter 4. Method 2: Group Actions 1 1 0 0 0 o 0 h -is —i i *3*4 3 i 4 28 ,(12) (354) o/ 0 0 0 0 1 0 1 0 ,(12) (35) (4) 2/42/32/12/4 o t -is V o —i i4 0 tt Note, the matrix is almost the same as the one obtained earlier apart from the change of variables. However, if we permute the variables i n the matrix according to the permutation u, then t\ — i > i , i3 f-> i , i H-> i , and so the matrix becomes 1 0 0 0 0 1 0 0 is -is 0 t^4 -isi4 0 which is the same as Morton's presentation. -*1 3 z 3 A 2 5 4 4 \ 4.2 The Cryptosystem based on the Coloured Burau M a trix F i x an integer n > 4 and a prime p. We define the keyspace K „ to be the set of pairs (M,a), where M is an (n — 1) x (n — 1) matrix with coefficients i n F , 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 . Associated to w there is a unique element (M,a) S C B where M = M(ii, i „ ) is a matrix and a is a permutation. Definition 4.1 The key extractor E: B —• K , is defined by E(w) := £ ( ( M f i . . . , i J > j - ( M ( T . . . , r ) (modp),a) where reduction (mod p) means reduction of every entry in the matrix. i P p N N N 1 ) r u N P n T h e Algorithm Input: A braid word w = g\g2---9i of length I, a prime p, and {TI, T , distinct invertible integers (mod p). 2 r }, n Initialization: M = (n — 1) x (n — 1) identity matrix, k = 0, n = identity permutation. Step Step Step Step 1: 2: 3: 4: If k = I then S T O P k := k + 1 If 5 = ^ then G O T O S T E P 5 If g = a' then G O T O S T E P 8 fc 1 k Step 5: M := M-C^T^)(mod Step 6: 7r : = 7r(i i + 1) p) Chapter 4. Method 2: Group Actions Step Step Step Step 7: G O T O S T E P 1 8: M := M- ((Cifa )(mod 9: 7r : = n(i i + 1) 10: G O T O S T E P 1 29 p))~ l (i) Output: (M,7r) The Cryptosystem Public information: A n integer N > 6 and a prime p > N, Distinct and invertible integers T , T 2 , ...,TN (mod p) 1 K e y Generation 1 Suppose Bob wishes to send a message to Alice. Let publicly known subgroups SA and SB be denned as before, SA — ( a i , . . . , a ) , SB = (bi,---,b ). a) Alice chooses a braid a S SA, say a=af a^...a** where e* = ± 1. b) Public key is m n 1 1 a &ia, a - 1 _ 1 &2a,a~ b a l n Encryption Given a message m € {0, l } and Alice's public key a) Bob chooses a braid b € S , b) Bob then computes c = (& di&, b~ a2b,...,b~ a b) and a" 6a = ( a - 6 a ) ( a - 6 ^ a ) . . . . ( a - ^ ' a ) Bob then sends the pair (c, d) to Alice where d = H((a~ ba)~ b) © 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- a? &)(&-X &)-»(&~ <*&) = b^ab. Then, Alice computes a~ b~ ab, and, to retrieve the initial message m, she computes H^b^nb)® d = if(a- (6- o6))©if((a- 6a)- 6)© m = ( a - ^ ^ ) © i f (a- *;- ^) © m = m. f c B -1 1 l m 1 1 e 1 I 1 1 i 1 1 1 a 1 a 1 1 1 - 1 1 1 1 1 1 1 Chapter 5. Coxeter groups and Artin Groups 30 Chapter 5 Coxeter G r o u p s and 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 indexed by I, with edges labelled connecting vertices i and j precisely when mij > 3. B y 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: G M = ( <7i,ff2,-,CT : (o-jCrj) « = of = 1 ). m n Given a Coxeter group, GM, the associated A r t i n group, A M , is the group with the presentation A M = ( 0-1,0-2, ...,cr : OiOj.... n = OjOi.... , i ^ j ). We say an A r t i n 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 A n (n > 1) Coxeter G r a p h 'I '2 *3 4 B n (n > 2) \ '2 % Chapter 5. Coxeter groups and Artin Groups 31 .2 D n (n > 4) 1 3 X "' n-1 n .2 (n = 6,7,8) 1 3 "4 n — 1 n 4 F 1 4 ^ ^ *4 6 G 2 #3 h(m) The braid group with n + 1 strings is the A r t i n group whose associated Coxeter group, GM, is type A . ( N o t e , the Coxeter group B is not equal to the braid group.) Having considered the braid groups application to public key cryptosystems, we now consider whether the other A r t i n groups of finite type can also be applied to cryptography. There are a number of reasons for believing that other A r t i n groups of finite type may be useful: The word problem is solvable by computing a canonical form. Ko-Lee indicate in [18] that automatic groups may be good candidates for cryptography. In [6] Charney proved that A r t i n groups of finite type have an automatic structure. Also, as with the braid group, the conjugation problem is presumably hard. N n 5.2 The Word Problem In 1972, Brieskorn-Saito generalized Garside's work and solved the word problem for finite type A r t i n groups. Their solution puts a word W into the form W = AP where P is a word in the A r t i n generators (ie, P is a positive word), and A is the fundamental word described in Lemma 5.2. k 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 generalized Thurston's normal form for A r t i n 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 I ) 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: 1; n' = P I U °u n " = p n 2 a*, n = i r n " . i e / 2 This set is well defined since the factors commute. Coxeter groups are examples of finite reflection groups, ie, they can be generated 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 . Then the product si • • • s is called the Coxeter element, and the Coxeter number, h, is the order of the Coxeter element. For example, the symmetric group, S , (= 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 A has Coxeter number n + 1. n n n n 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 = U. / h 2 p A = A 2 if h is even, u^-^W p = U h p = ff'tf*- '/ 1 p ifh is odd, 2 always. • (Proof omitted) The Coxeter numbers for the finite type Coxeter groups are given below: A B B E E E F G H H J (m) n n + 1 n 2n n 2(n-l) 6 12 7 8 18 4 30 3 2 12 6 10 A 30 Let AM be an A r t i n group of finite type with presentation AM = ( o-i,....,a : aiOjOi.... = OjOiO-j...., i ^ j •) n * s, ' rriij terms =(S:R) Let S V ' rriij terms 2 m. Chapter 5. Coxeter groups and Artin Groups 33 G = { o- ...,o : (oiOj) i = 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 mi M lv n + + + = (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-r 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 i n 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. 1 + + + + 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 > a } has a unique maximal element. Denote this element by max(a). Let max(a) = a\. Then a > a and a = ai?7i for some r/x £ A+. Let max(r]i) = a . Then rji > a and rji = a rj . So, a = airji = a\a i} . 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 = aia ....a is a left weighted decomposition of a. This decomposition is a normal form for a. + + + 1 x 2 2 2 2 2 2 2 k The following result is due to Charney [6]: Proposition 5.3 Let a = aia ...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\a ...ak is in normal form if and only if aiOj+i is in normal form for each i. • (Proof omitted) 2 + 2 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) A a = aA for all a£ A+, (iii) The involution o n a = A 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) = A a where a £ A+. Therefore, w = A aia2....afc is the normal form for w. + + 2 2 _ 1 + + p p 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 = ca for some c £ A }. Now, suppose w £ A has been written in the form w — A a 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 containing 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' . Then is a minimal since it is square free, as is a' . This gives another decomposition a ^ . + + + t p + + + + i+l i+1 + 1 Chapter 5. Coxeter groups and Artin Groups Continuing in this way until S(a i) written in its normal form. • 35 C F ( a , ) for all i, we get the word a i+ So we can generalize Thurston's normal form for all A r t i n groups of finite type. Can we then apply this normal form to the finite type A r t i n groups to construct a public key cryptosystem that works as well as the braid group? Since each finite type A r t i n group has a different presentation and different fundamental word we should consider each group seperately. 5.3 7 (m) 2 Let A = ( 01,02 '• o\020\.... = o oio .... ). m 2 »- * 2 * m terms - m terms Let (Ii, I ) be the decomposition Ii = {1} and 7 = {2}. Let II' = o\, I I " = cr and II = 0i0 . We know that the Coxeter number for this group is m , therefore we have that the fundamental word, A , is A = IT™/ if m is even = n t " - ) / ] } ' if m is odd. Therefore A = o\020\...02 if m is even 2 2 2 2 2 p 1 1 2 p * v m ' terms or A — o\o o-\...o\ if m is odd. 2 m terms Lemma 5.6 (i) o"iA = A02, o"2A = A c i ifm is odd, CTIA — Aoi, o A = Ao if m is even. (ii)CT~ A= A C T " if m is even, o^ A = A c r J , <TJ A = A f f ^ if m is odd, (Hi) < j j A = A~ Oi ifm is even, CTIA = A C T , < r A = A~ o\ ifm is odd, (iv) o~ A~ = A~ o~ ifm is even, erf A = A ^ , c ^ A = A ^ ifm is odd. p p p 2 1 p 1 1 -1 -1 X 1 x _ 1 _ 1 2 l 1 2 1 x - 1 - Proof (i) <7iA = 1 p 1 2 1 1 1 - 1 - oi(oi020i...oi) = 1 0\{p20\02-• -o~2) —p &°~2 if m p m terms o~iA = p 2 = p m terms o\[o\020\...02) — G\(u oiO'2...CFi) = p m terms oA 1 p terms p m terms 02{p\020\...o\) = m 2 Aoi if m is odd Ao\ i f m is even. is ° d d . Chapter 5. Coxeter groups and Artin Groups 02A = p 36 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 A . Let the starting set and finishing set be defined as before. We want to write a as a = A a a2-..ak where a is a minimal for all i. The minimal elements of v4+ are precisely the elements of the form o\oio~\— or m p 1 t k terms <72<7i<72... where k < m. k terms 5.3.1 The Normal Form Let P be a word in A . We can write P as P = W a- W o-- W ....W cr- W where each W* is a positive word. Since A = cri( o" o"i...<7i) if m is odd m 1 1 l 2 1 3 k l 2 m—1 terms G \ = A(a']~ C7'^" (7{" ...(T2~ ). V 1 1 m—1 1 1 ' terms Therefore, if m is odd, af = (Q- O"IO'2---O'I)A~ . 1 :L 2 m—1 terms Similarly, Co" — (<TiCr2(Ti...(T2)A~ . 1 1 v N m—1 ' terms Now, if m is even, erf = ((T2(Tig2---C )A~ 1 1 2 m—1 terms and o-jf = (cricr2CTi-ffi)A . 1 _1 m—1 terms So, we can replace any occurrence of a negative generator by X A where X is a positive word. B y the lemma, we can move all occurrences of A to the left so that P is written as P = A B, 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 = W\ AW 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: k p 2 _ 1 - 1 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\o 0\...Oi), where i = 1 or 2 depending on whether m is 2 m terms even or odd. Therefore B is of the form B = WiOjOjW^OkOkWz.... , j, k = 1 or 2 where Wi = 0\0 0\.... or Wi — 020\0 .... where n is less than m — 1. p p 2 p 2 n terms n terms Let a i = WitTj and a = ffjYi where W = YiY . Then F ( a i ) = a, and 5 ( a ) = o-j. Therefore, 5 ( a ) C F ( a i ) . In the same way let a = 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. p 2 2 p 2 p 2 2 3 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 G . This group is just 7 (6), and so we have already studied this group. Now consider the other A r t i n groups of finite type. Given a word W £ A, we know that W can be written in the form A B, 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 A r t i n 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 = A } and Min ={fi: W = pX,W £6,X £ A+}. If x is an element of Min, then x is a minimal. The group A 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. 2 2 P p p m 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 . (p*)r}a. So A > (p*)n. So p*n is minimal. + Now A = (p*)p = 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 . following are equivalent: (i) a Lb (ii) pLn (iii) p*n is in normal form (iv) fj*p is in normal form. + Let p = max(a), 77 = max(b). Then the 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 equivalence 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 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,ifi ---^k where the p^ are minimals. Consider A a~ G A. Claim A a^ lies in the image of A in A. In fact A ^ a - = A (n p ...n )-^ = A p^ V f c l i - A ' J V ^ For k even: _ 1 + 2 k 1 k 1 + 1 k k 1 2 k A^" - A/x^ A...A/J - A/xf 1 1 f c 1 1 2 = AAAt- A- A^ A...AA^ " A- AMr 1 1 1 Since a A = A a we move all factors of A 2 1 2 1 to the left and get 2 For k odd: A/i- A// --i~ A...A|T - A^i~ = AMfe AAMfci: A- A...AA/J " AA-Vr A^fc V f c - i - ^ V r = A^a" . Also, for fc even: Afi ~ A/x^iA...Afi ~ Ap,^ = ^ */x "_i*.../x */Ii*1 1 1 f c 1 1 1 2 l fc odd: A^l = 1 2 1 l k 1 1 1 1 = 1 2 1 2 Ap^- fc A.-.Afc- 1 A^ 1 1 fc 2 = /J */i _i*...^2*A«i* fe fe 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/u .../Xfc)* — /xfc*.../t * where p-i = pi if i is odd, or pi if i is even. 2 TO Lemma 5.10 / / pip2---L k is the normal form for a G A , is the normal form for A a . L f c then (p\...pk) * + _ 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~ a and a ±b. + x Proof We know that g can be written as g = A~ p 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 a and A " = cob. Then a l b and g = A~ p — b~ c^ coa — b~ a. This proves existence. Now suppose g G A . lfg = b~ a then bg = a and so a > b. This contradicts orthogonality unless 6 = 1 . n + + + n 0 + 1 1 1 x 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 a = d~ c with a ± b,c ± d and a,b,c,d non trivial. Let a = aia ...a , 6 = 6 6 ...b , _ 1 2 n C = CiC2...Cp 1 2 l m d=d\d2...d . q Since we have orthogonality there are no factors of A in these products. Suppose m > q. Then A g = A b~ a = {b ...b )*a ...a and A g = A d~ c = A -i(d ...d )*c ...c . The right hand sides of both of these equations are i n normal form. B y uniqueness of normal forms they must have the same minimal decomposition. The first term of (bi...b )* is b * which cannot be A (since this would mean b = 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 A r t i n groups efficiently, and, the conjugacy decision problem is hard to solve. The group A ( 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. m m 1 m 1 m 1 m 1 q m 1 p m m 2 m 1 n 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~ xy) < l(x). The length attack is based on these reducing strings. Let a £ SA = ( a i , • •••,a ) be the private key. Let a 6 , - a and bj, j = 1, . . . , n be publicly given. Assume the generators of SA have lengths large relative to a. Let 7j = a b , a . The idea is to compute l(af 7 j a ? ) , i = 1, . . . , m repeatedly. If ^ is a reducing string with respect to jj then l -1 m _ 1 1 1 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,i ai ...a,i and each of the generators of the subgroup SA is used i n 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) factors to try. If we repeat this process n times on each public conjugate a~ bja, j = 1, ...,n, then combining all these steps brings us to n(2m) 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) . 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 l 2 d k l fc fc SA = (ai, a , a 2 2 0 ),S B = {h,b , 2 ho) where each a; and bj is the product of 5 to 10 A r t i n generators. Each set of public generators SA,SB should involve all of the A r t i n generators of B . Given that a length function can also be applied to words in any finite type A r t i n group, such an attack is also feasible on a cryptosystem which uses another A r t i n group of finite type. This means that we can eliminate the use of most of the other A r t i n groups of finite type. There are only three A r t i n groups of finite type with more than 80 generators: the braid group, and the groups whose associated Coxeter groups are B and D . n n n 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 CB is a pair ( M , a), where M is a matrix with entries in F , the finite field of p elements, and o is the induced permutation. Let M and o correspond to the coloured Burau matrix and permutation associated to the word x. Then (M ,o )(Mb,Ob) = (M • o Mb,cf Ob) and n p x x a a a a a ( M a . a . J - ^ ^ M - , ^ ) In [2], the following parameter recommendations were suggested: 1 1 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. A s 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 A r t i n 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, i n [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,...,b ),(a' b a,a~ b a,...,a~ b a) 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: 1 1 m 1 1 2 m Theorem 6.1 If the induced permutations of a and b are known then we can construct four lists of matrix equations in GL -\{F ) such that computing the matrix part of the shared key is reduced to solving each of these lists. n p Proof Let y denote the element in CB corresponding to the braid word x. Recall the shared key, K, is a~ b~ ab. Then, Va-ib-iab = ( M , 0 - ) - ( M , C r ) - ( M , ( T ) ( M , ( T ) . = ((a- M- )(aJ a - M - )(ajV - M )(ff-V^V M ),or- er - a a ). So the matrix part of the shared key is the product of the four matrices evaluated at (ti,...,t ) = (rj, . . . , r ) : ( a A f a j ) , ((J- c r - M " ) , fc^Ma), (a" O M ). Consider (cr a M )(r ...,r„). Assume that the permutations a and are known. 1) Choose x i n SB such that x is a pure braid. 2) Compute c = a~ xa. Then c is also a pure braid. 3) Since xa = ac and x n 1 1 1 a 1 1 a 6 1 1 6 a 1 6 b b 1 6 n CT a 1 6 0 6 0 6 n 1 1 1 1 1 A fe 1 1 1 6 0 B 1 a b a u a x = (M • M ,a ),y y X xa a a ac = (M • (a M ),a ) A A c a then {a-^M ){azWM ) =( ^ V ^ X ^ S " " ^ - ^ ) . 4) Let X = (a a M )(T ,...,T ) and C = {a~ a a M )(T , ...,T„). 5) Repeat this process for N pure braids x. Then we get a system of equations XjA = ACj for j = 1 , N . Then ( c r ~ ( T M ) ( T i , ...,T„) is a solution in GL -i(F ) to XjA — ACj,l < 3<N. Similarly, we can generate a system of equations for the three other matrices in the matrix product. • x a 1 a 1 l 1 b x 1 71 I A b _1 b a n p C 1 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 = v 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~ xy 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 o 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 i n [19]. Therefore, the difficulty in this attack lies only in the number of solutions. B y [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 S or GL -\(F ) is not known, but the authors of [19] conject it is not large. q l a n n p 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]. A t this point the authors of [16] are statistically testing the length attack on several groups including the braid group and A r t i n 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 protocols 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 . Artin, 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. A n n . 292 (1992), 671-683. [7] R . Charney, Geodesic Automation and Growth Functions for Artin Groups of Finite Type, Math. A n n . 301 (1995), 307-324. [8] R. Corran, On monoids related to braids, Thesis, The University of Sydney, M a y 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) 469472. [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 Applications, 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 . K o , S. J . Lee, J . H . Cheon, J . W . Chan, J . K a n g 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 agreement 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 digital 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. |
IsShownAt | 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