Conjugacy in braid groups with applications in non-commutative and non-associative cryptography

Abstract

We review braid and Garside groups and the history of conjugacy in this groups. Then we also consider the friends of the conjugacy problem like the subgroup (subCP), shifted (ShCP), simultaneous conjugacy (SCP) and the double coset problem (DCP). In particular we improved invariants for the SCP, developed the first deterministic algorithms for ShCP, and for subCP and DCP for parabolic subgroups of braid groups. This is based on joint work with several coauthors from Bar-Ilan University, Ramat Gan, Israel.

Further motivation for these problems comes from non-commutative public key cryptography, and we discuss basic key agreement protocols. Dehornoy's shifted conjugacy leads us to left-selfdistributive (LD) systems, multi-LD systems, and our new idea of non-associative cryptography.