**The conjugacy search problem in public key cryptography: unnecessary and insufficient**

*Vladimir Shpilrain and Alexander Ushakov*

**Abstract: **The conjugacy search problem in a group $G$ is the problem
of recovering an $x \in G$ from given $g \in G$ and $h=x^{-1}gx$.
This problem is in the core of several recently suggested
public key exchange protocols, most notably the one due to
Anshel, Anshel, and Goldfeld, and the one due to Ko, Lee at al.

In this note, we make two observations that seem to have eluded most people's attention. The first observation is that solving the conjugacy search problem is not necessary for an adversary to get the common secret key in the Ko-Lee protocol. It is sufficient to solve an apparently easier problem of finding $x, y \in G$ such that $h=ygx$ for given $g, h \in G$.

Another observation is that solving the conjugacy search problem is not sufficient for an adversary to get the common secret key in the Anshel-Anshel-Goldfeld protocol.

**Category / Keywords: **public-key cryptography / combinatorial cryptography, group-theoretic cryptography

**Date: **received 22 Nov 2004, last revised 28 Dec 2004

**Contact author: **shpil at groups sci ccny cuny edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20041228:213057 (All versions of this report)

**Short URL: **ia.cr/2004/321

[ Cryptology ePrint archive ]