Check: BoolElt                      Default: true

Example GrpBrd_Homomorphisms (H80E10)

(1)

The symmetric group on n letters is an epimorphic image of the braid group on n strings, where for 0 < i < n the image of the Artin generator a_i is given by the transposition (i, i + 1).

We construct this homomorphism for the case n = 10.

> Bn := BraidGroup(10);
> Sn := Sym(10);
> f := hom< Bn->Sn | [ Sn!(i,i+1) : i in [1..Ngens(Bn)] ] >;

Of course, the image of f is the full symmetric group.

> Image(f) eq Sn;
true

Now we compute the image of a pseudo-random element of Bn under f.

> f(Random(Bn));
(1, 5, 8)(2, 4, 9, 7, 6, 3)

(2)

(Key exchange as proposed in [KLC+00])

Consider a collection of l + r strings t₁, ..., t_{l + r} and the braid group B acting on t₁, ..., t_{l + r} with Artin generators s₁, ..., s_{l + r - 1} . The subgroups of B fixing the strings t_{l + 1}, ..., t_{l + r} and t₁, ..., t_l may be identified with braid groups L on l strings and R on r strings, respectively, with the Artin generators of L and R corresponding to s₁, ..., s_{l - 1} and s_{l + 1}, ..., s_{l + r - 1}, respectively.

We set up these groups for l = 6 and r = 7 using the BKL presentations.

> l := 6;
> r := 7;
> B := BraidGroup(l+r : Presentation := "BKL");
> L := BraidGroup(l : Presentation := "BKL");
> R := BraidGroup(r : Presentation := "BKL");

We now construct the embeddings f : L -> B and g : R -> B.

> f := hom< L-> B | [ L.i -> B.i : i in [1..Ngens(L)] ] >;
> g := hom< R-> B | [ R.i -> B.(l+i) : i in [1..Ngens(R)] ] >;

To complete the preparatory steps, we choose a random element of B which is not too short.

> x := Random(B, 15, 25);

The data constructed so far is assumed to be publicly available. Each time two users A and B require a shared key, the following steps are performed.

(a)

A chooses a random secret element a∈L and sends the normal form of y₁ := x^a to B.

(b)

B chooses a random secret element b∈R and sends the normal form of y₂ := x^b to A.

(c)

A receives y₂ and computes the normal form of y₂^a.

(d)

B receives y₁ and computes the normal form of y₁^b.

Note the following.

Transmitting y₁ and y₂ in normal form disguises their structure as products a ^{- 1}xa and b ^{- 1}xb, provided the words used are long enough and prevents simply reading off the conjugating elements a and b.

Since the subgroups L and R of B commute, we have ab = ba, which implies y₂^a = x^ba = x^ab = y₁^b. Thus, the normal forms computed by A and B in steps (c) and (d), respectively, must be identical and can be used to extract a secret shared key.

We illustrate this, using the groups set up above. For step (a):

> a := Random(L, 15, 25);
> y1 := NormalForm(x^f(a));

Now for step (b):

> b := Random(R, 15, 25);
> y2 := NormalForm(x^g(b));

We now verify that A and B arrive at the same information in steps (c) and (d).

> K_A := NormalForm(y2^f(a));
> K_B := NormalForm(y1^g(b));
> AreIdentical(K_A, K_B);
true

We see that the information computed by A and B in steps (c) and (d) is indeed identical and hence can be used (in suitable form) as a common secret. Note, however, that the number of strings and the lengths of the elements used in the example above are much smaller than the values suggested for real cryptographic purposes.

(3)

(Attack on key exchange)

We now show an attack on the key exchange outlined above using conjugacy search based on ultra summit sets.

An eavesdropper can try to compute an element c conjugating x to y₁. While this is not guaranteed to reproduce the braid a, the chances for a successful key recovery are quite good.

We decide to change to the Artin presentation of B and use the function MyIsConjugate from Example H80E8 for computing a conjugating element c as above.

> SetPresentation(~B, "Artin");
> time _, c := MyIsConjugate(x, y1);
42 elements computed
Time: 0.020

Finding a conjugating element is no problem at all. Using the conjugating element, we can try to recover the shared secret. In this example we are lucky.

> NormalForm(y2^c) eq K_A;
true

In the conjugacy search above, a conjugating element was found after computing 42 ultra summit elements. The ultra summit set itself is larger, but can still be computed very easily.

> time Ux := UltraSummitSet(x);
Time: 3.150
> #Ux;
1584

The super summit set is, even in this small example, too large to be computed; conjugacy search based on super summit sets would quite likely fail.

> time Sx := SuperSummitSet(x);
Current total memory usage: 4055.1MB
System error: Out of memory.

Finally, we show that the attack using conjugacy search based on ultra summit sets is also applicable to larger examples. We try to recover a key, which is generated using elements with canonical lengths between 500 and 1000 in a braid group on 100 strings.

> l := 50;
> r := 50;
> B := BraidGroup(l+r);
> L := BraidGroup(l);
> R := BraidGroup(r);
>
> f := hom< L-> B | [ L.i -> B.i : i in [1..Ngens(L)] ] >;
> g := hom< R-> B | [ R.i -> B.(l+i) : i in [1..Ngens(R)] ] >;
>
> x := Random(B, 0, 1, 500, 1000);
>
> a := Random(L, 0, 1, 500, 1000);
> y1 := NormalForm(x^f(a));
>
> b := Random(R, 0, 1, 500, 1000);
> y2 := NormalForm(x^g(b));
>
> K_A := NormalForm(y2^f(a));
> K_B := NormalForm(y1^g(b));
> AreIdentical(K_A, K_B);
true

We again try to recover the key by computing an element conjugating x to y₁. This time, we use the built-in Magma function for efficiency reasons.

> time _, c := IsConjugate(x, y1);
Time: 18.350
> K_A eq NormalForm(y2^c);
false

Bad luck. -- We managed to compute a conjugating element, but this failed to recover the key.

We try with an element conjugating x to y₂.

> time _, c := IsConjugate(x, y2);
Time: 3.800
> K_B eq NormalForm(y1^c);
true

Success! -- Good that we didn't use this key to encrypt our credit card number!

Example GrpBrd_Representations (H80E11)

We construct the Burau representation of the braid group on 4 strings.

> B := BraidGroup(4);
> f := BurauRepresentation(B);

Its codomain is a matrix algebra of degree 4 over the rational function field over the integers.

> A := Codomain(f);
> A;
GL(4, FunctionField(IntegerRing()))
> F := BaseRing(A);
> F;
Univariate rational function field over Integer Ring
Variables: $.1

To obtain nicer printing, we assign the name t to the generator of the function field F.

> AssignNames(~F, ["t"]);

Now we can check easily whether we remembered the definition of the Burau representation correctly.

> f(B.1);
[-t + 1      t      0      0]
[     1      0      0      0]
[     0      0      1      0]
[     0      0      0      1]
> f(B.2);
[     1      0      0      0]
[     0 -t + 1      t      0]
[     0      1      0      0]
[     0      0      0      1]
> f(B.3);
[     1      0      0      0]
[     0      1      0      0]
[     0      0 -t + 1      t]
[     0      0      1      0]