SES Home » Science Departments » Algebraic Cryptography Center » Arithmetica Key Eschange Search |  People Finder

# Arithmetica Key Eschange

 Introduction 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. Sang Jin Lee, Eonkyung Lee, Potential Weaknesses of the Commutator Key Agreement Protocol Based on Braid Groups, (EUROCRYPT 2002). J. Hughes, A. Tannenbaum, Length-Based Attacks for Certain Group Based Encryption Rewriting System, (SECI 02). 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