Let be the group of braids on strands and the set of standard generators. Thus,

Let , , and be preset parameters. The AAG protocol is the following sequence of steps:

(1) Alice randomly generates an -tuple of braid words , each of length between and , such that each generator of non-trivially occurs in . The tuple is called Alice's public set.

(2) Bob randomly generates an -tuple of braid words , each of length between and , such that each generator of is non-trivially involved in . The tuple is called Bob's public set.

(3) Alice randomly generates a product , where and (for each ). The word is called Alice's private key.

(4) Bob randomly generates a product , where and (for each ). The word is called Bob's private key.

(5) Alice computes () and transmits them to Bob. Here denotes Dehornoy's form of a braid word .

(6) Bob computes () and transmits them to Alice.

(7) Alice computes . It is straightforward to see that in the group .

(8) Bob computes . Again, it is easy to see that in the group .

Thus, Alice and Bob end up with the same element of the group . This is now their common secret key.

Parameters

Initially, (in [1]) the system was claimed secure for values of parameters: .

Later, the values were increased to: .

Known Attacks

1) Length-based attack (heuristic) [3]: The principal idea behind the attack is that the braid group has
exponential growth and a conjugation of a tuple
by an element from must (almost always) increase the lengths of the elements on the tuple .

2) Algorithm for solving the MSCP in Braid Groups [2]: Authors propose an algorithm for solving the MSCP in Braid
Groups. The algorithm is analagous to the Super Summit approach
for solving the SCP in Braid Groups. Its efficiency is analyzed in terms
of the size of the corresponding Summit set, which can easily
be exponential in terms of the "lengths parameters".
Must be used in conjunction with the algorithm [4]
and the subgroup attack:

3) Subgroup Attack (heuristic): This attack tries to find to an "easier" generating set for the
given subgroup.

4) Algorithm for solving MSCP in Braid Groups using
images of braids in permutations (heuristic): A Practical Attack on Some Braid Group Based Cryptographic Primitives,
by Dennis Hofheinz and Rainer Steinwandt (PKC 2003).

Challenges

Under construction ...

References

I.Anshel, M.Anshel, D.Goldfeld.
An algebraic method for public-key cryptography.
Mathematical research letters, 6, pp.287-291, 1999.

J. Gonzalez-Meneses,
Improving an algorithm to solve MultipleSimultaneous Conjugacy Problems in braid groups,
Contemp. Math.,Amer. Math. Soc., to appear.

Stevens Institute of Technology •
Hoboken, NJ • (201) 216-5000
Sitemap