Properties of braids
The following properties may be more difficult to understand than the basics of braids, but are essential in understanding the implementation of braid group cryptosystems.
To understand the protocols, it is not necessary to understand
the complete details on this page (and one can skip them on first reading), but
one should be aware that when talking about transmitting messages using braids,
one is really using braids that have been converted into the normal form
discussed below.
The half twist
(by 180 degrees) of the n stings in 
is denoted by 
. Figure 1 below shows the half-twist on 4 strings.
Figure 1: 
in 
.
This half twist is useful because it has interesting properties- for instance
one can slide any crossing through the half twist. This gives us the relation:
.
The lefthand side of Figure 2 below
shows the braid 
and the righthand side shows the braid 
, demonstrating the case when 
and 
. Notice how the crossing at the top of the lefthand braid (shown in red) passes through the rest of
the braid to end up as the crossing at the bottom of the righthand
braid.
Figure 2: 
.
On the Introduction to braids page, we saw that a braid can be expressed in many ways, but we can actually express them in a standard way (a unique normal form). When sending messages using the braid cryptosystems, we actually use braids in this normal form. This normal form enables us to encode a braid as a sequence of integers (explained below), which is rather useful for implementation purposes.
There is a canonical map, 
, from to 
(the permutation group
on n elements) which maps the braid
to the permutation induced by the ends of the strings. For example
,Figure 3 shows the braid 
maps to the
permutation 
. This can be read off from the numbers at the top and bottom
of the braid; for example the first string (shown in blue) takes the 1 at the
top to the 3 at the bottom, thus giving the first column of the permutation
matrix.
Figure 3: 
Many braids induce the same permutation of their endpoints. For example,
take the above braid and concatenate with the braid 
we obtain 
which maps to the same
permutation
Figure 4: 
We call a braid which only has positive crossings and every pair of strings
crosses at most once a permutation braid.
One can write any braid 
as 
, where u is an
integer and the 
are permutation braids. Enforcing an extra condition (which
basically means that the ’s to the left are as large as possible) makes this
representation unique (and is called left-weighted
normal form). The number p is
called the canonical length of the
braid.
We can now store this braid as the tuple 
. There are only n! elements of , and so we can encode such an element by an integer 
. This is better than trying to encode which has infinitely
many elements! For this tutorial, we will write the permutations 
rather than an integer encoding it, because this is more
instructive.
For example, the braid 
has normal form 
, where 
. Therefore, 
, the canonical length is 1, and 
. Figure 5 below shows the equivalence- the left braid is , adding the two crossings below this (shown in blue) makes
the braid 
and adding the last two crossings gives a braid equivalent to (which can be seen be
“cancelling” the last two pairs (blue and red) of crossings).
Figure 5: 
If has canonical length p, then it can be stored in 
bits. The normal form
of 
can be computed in 
time. If 
are braids in
normal form, and q is the canonical
length of 
, then it takes 
amount of time to compute
the normal form of 
, and 
amount of time to
compute the normal form of 
. Therefore, it is feasible to store braids in the manner
described and to perform these operations, which will be used in the protocols.