Computational Algebra Seminar
Given a finite group G, known to be isomorphic to a simple group H (we regard H is the standard copy of the simple group), we consider the algorithmic problem of writing down an explicit isomorphism from H to G. This problem, known as the constructive recognition problem, has important applications to several other algorithmic problems of current interest. Among these are the problem of constructing a composition series for a finite matrix group, and constructing the maximal subgroups of a permutation group.
In this talk I will give a more precise definition of a constructive recognition algorithm and indicate how such algorithms are applied to the problems mentioned above. I will also outline some of the algorithmic difficulties one is confronted with when devising such algorithms.
After recalling braid groups and the Garside normal form, I will explain the Diffie-Hellman like key exchange introduced by Ko et al. and some related cryptographic protocols, which are all based on the conjugacy search problem (CSP) in braid groups.
In the second part of the talk I will present recent solutions to the CSP and we will see that they yield effective attacks on these cryptographic protocols in their present form.
Time permitting, I will finally discuss some possible modifications to the cryptographic protocols, such as appropriate choice of keys or replacing the CSP by the decomposition problem.