Charles V. Schaefer, Jr. School of Engineering and Science
 
 
ACC Top Page » Algebra and Cryptology Center » Arithmetica Key Eschange

Arithmetica Key Eschange

Introduction

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

479


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

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

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

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

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

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

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

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

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

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

Parameters

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

Later, the values were increased to:
481.

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 456 by an element from 459 must (almost always) increase the lengths of the elements on the tuple 456.

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

  1. I.Anshel, M.Anshel, D.Goldfeld. An algebraic method for public-key cryptography. Mathematical research letters, 6, pp.287-291, 1999.
  2. Sang Jin Lee, Eonkyung Lee, Potential Weaknesses of the Commutator Key Agreement Protocol Based on Braid Groups, (EUROCRYPT 2002).
  3. J. Hughes, A. Tannenbaum, Length-Based Attacks for Certain Group Based Encryption Rewriting System, (SECI 02).
  4. J. Gonzalez-Meneses, Improving an algorithm to solve MultipleSimultaneous Conjugacy Problems in braid groups, Contemp. Math.,Amer. Math. Soc., to appear.