Paper 2004/321

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
combinatorial cryptographygroup-theoretic cryptography
Contact author(s)
shpil @ groups sci ccny cuny edu
History
2004-12-28: revised
2004-11-24: received
See all versions
Short URL
https://ia.cr/2004/321
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/321,
      author = {Vladimir Shpilrain and Alexander Ushakov},
      title = {The conjugacy search problem in public key cryptography: unnecessary and insufficient},
      howpublished = {Cryptology ePrint Archive, Paper 2004/321},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/321}},
      url = {https://eprint.iacr.org/2004/321}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.