Conjugacy Search Problem for Relatively Hyperbolic Groups

The asymptotic bound for a length-based attack on the Conjugacy Search Problem in relatively hyperbolic groups is cubic for hyperbolic elements and a “small” polynomial for parabolic elements, depending on the Conjugacy Search Problem for the peripheral subgroups. The bound for relatively hyperbolic groups in this paper is a significant improvement on previous work.