Cryptanalysis of Public Key Protocols in cryptography using braid groups

Abstract: Several post-quantum cryptography protocols have been proposed, taking as base “intractable” problem the conjugacy problem in non-commutative groups. The groups proposed to implement these protocols were braid groups. In our research group, in a series of papers, we developed the best solution known to solve the conjugacy problem in these groups. Using this algorithm, we showed that this problem is solved in polynomial time in the generic case. This shows that the proposed protocols are not secure in its original form, and that refinements of this protocol must be obtained, namely in the key generation procedure.