Conjugacy search in braid groups - From a braid-based cryptography point of view

摘要

We demonstrate that recent advances in the theory of braid groups, in particular a new invariant of conjugacy classes of braids, the ultra summit set, make some braid-based cryptographic protocols insecure for almost all randomly chosen keys. As part of this we present an overview of the known algorithms for solving the conjugacy decision and search problems in braid groups and an assessment of their practical performance from the point of view of braid-based cryptography.