Key Agreement and Authentication Schemes Using Non-Commutative Semigroups

The authors give a new two-pass authentication scheme, which is a generalisation of an authentication scheme of Sibert-Dehornoy-Girault based on the Diffie-Hellman conjugacy problem. Compared to the above scheme, for some parameters it is more efficient with respect to multiplications. They sketch a proof that the authentication scheme is secure. In recent years various cryptographic protocols using infinite non-abelian groups have been proposed. For example the seminal algebraic key establishment protocol given in, and Artin's braid groups have been popular choices for such protocols. Braid groups are a popular choice because they are not too complicated to work with and they are more complicated than abelian groups. In particular the conjugacy problem in braid groups is algorithmically difficult and hence gives a one-way function.