CGC Bulletin 6
Contents:
- An entire issue of AAECC devoted to CGC
- The lower central and derived series of the braid groups of the sphere and the punctured sphere
- A Weak Key Test for Braid Based Cryptography
- Random walks on the mapping class group
* Congratulations to our friend and colleage Eran Tromer, for his winning the 2006 John F. Kennedy Prize of the Feinberg Graduate School.
* Thanks to Mike Anshel and Rainer Steinwandt for their contributions to this issue.
Boaz Tsaban
1. An entire issue of AAECC devoted to CGC
http://www.springerlink.com/(1ifc1jeyu0w0nm45vvhcflqk)/app/home/issue.asp?referrer=backto&backto=journal,1,90;linkingpublicationresults,1:100499,1;&absoluteposition=6#A6
Contents:
- Conjugacy Search in Braid Groups: From a Braid-based Cryptography Point of View 07 April, 2006 Volker Gebhardt DOI: 10.1007/s00200-006-0008-7
- Homomorphic Public-Key Cryptosystems and Encrypting Boolean Circuits 30 March, 2006 Dima Grigoriev and Ilia Ponomarenko DOI: 10.1007/s00200-006-0005-x
- Gröbner Basis Cryptosystems 23 March, 2006 Peter Ackermann and Martin Kreuzer DOI: 10.1007/s00200-006-0002-0
- Representation Attacks on the Braid Diffie-Hellman Public Key Encryption 22 March, 2006 Arkadius G. Kalka DOI: 10.1007/s00200-006-0007-8
- The Conjugacy Search Problem in Public Key Cryptography: Unnecessary and Insufficient 22 March, 2006 Vladimir Shpilrain and Alexander Ushakov DOI: 10.1007/s00200-006-0009-6
- A Linear Time Matrix Key Agreement Protocol Over Small Finite Fields 16 March, 2006 Iris Anshel, Michael Anshel, Dorian Goldfeld DOI: 10.1007/s00200-006-0001-1
2. The lower central and derived series of the braid groups of the sphere and the punctured sphere
Daciberg Lima Gonçalves (IME), John Guaschi (LEP)
Our aim is to determine the lower central series (LCS) and derived series (DS) for the braid groups of the sphere and of the finitely-punctured sphere. We show that for all n (resp. all n \geq 5 ), the LCS (resp. DS) of the n-string braid group B_n(S^2) is constant from the commutator subgroup onwards, and that \Gamma_2(B_4(S^2)) is a semi-direct product of the quaternion group by a free group of rank 2. For n=4, we determine the DS of B_4(S^2) , as well as its quotients. For n \geq 1 , the class of m-string braid groups B_m(S^2) \backslash \{x_1,...,x_n\} of the n-punctured sphere includes the Artin braid groups B_m , those of the annulus, and certain Artin and affine Artin groups. We extend results of Gorin and Lin, and show that the LCS (resp. DS) of B_m is determined for all m (resp. for all m \neq 4 ). For m = 4 , we obtain some elements of the DS. When n \geq 2 , we prove that the LCS (resp. DS) of B_m(S^2) \backslash \{x_1,...,x_n\} is constant from the commutator subgroup onwards for all m \geq 3 (resp. m \geq 5 ). We then show that B_2 (S^2 \backslash \{x_1,x_2\}) is residually nilpotent, that its LCS coincides with that of Z_2*Z , and that the \Gamma_i / \Gamma_{i+1} are 2-elementary finitely-generated groups. For m \geq 3 and n=2, we obtain a presentation of the derived subgroup and its Abelianisation. For n=3, we see that the quotients \Gamma_i / \Gamma_{i+1} are 2-elementary finitely-generated groups.
http://arxiv.org/abs/math.GT/0603701
3. A Weak Key Test for Braid Based Cryptography
Samuel Maffre
This work emphasizes an important problem of braid based cryptography: the random generation of good keys. We present a deterministic, polynomial algorithm that reduces the conjugacy search problem in braid group. The algorithm is based on the decomposition of braids into products of canonical factors and gives a partial factorization of the secret: a divisor and a multiple. The tests we performed on different keys of existing protocols showed that many protocols in their current form are broken and that the efficiency of our attack depends on the random generator used to create the key. Therefore, this method gives new critera for testing weak keys. We also propose a new random generator of key which is secure against our attack and the one of Hofheinz and Steinwandt.
Designs, Codes and Cryptography Volume 39 (2006), 347 -- 373.
DOI: 10.1007/s10623-005-5382-9
4. Random walks on the mapping class group
Joseph Maher
We show that a random walk on the mapping class group of a closed orientable surface gives rise to a pseudo-Anosov element with probability one. A random 3-manifold may be constructed by using a random walk in the mapping class group as the gluing map for a Heegaard splitting. We show that the random 3-manifolds constructed in this way have Heegaard splitting distance which tends to infinity with probability one. Assuming Thurston's Geometrization Conjecture, this implies that the random 3-manifolds are hyperbolic with probability one.
http://www.arxiv.org/abs/math.GT/0604433
(This may be of interest with respect to the conjugacy problem.)
