In the past decades, cryptographers have focused their attention in braid groups to use them as a tool to construct authentication schemes and digital signatures. In this talk we will discuss the application of the root extraction problem for braid group-based cryptography. That is, given a braid $\beta$ and a number $k$, find a braid $\alpha$ such that $\alpha^k=\beta$ (if it exists). We will first go through an historical overview of the approaches to this problem and then we will describe the proposed cryptosystems that claim to be based on this problem. We will see that some of them can be attacked without solving the root extraction problem and that others are not safe if the parameters are not carefully chosen, as the latest algorithm to solve the problem work in almost every case.
Root extraction problem in braid group-based cryptography
María Cumplido, Universidad de Sevilla
Authors: María Cumplido, Delaram Kahrobaei, Marialaura Noce
2022 AWM Research Symposium
Mathematical Aspects of Cryptography