The conjugacy search problem in public key cryptography: Unnecessary and insufficient

Vladimir Shpilrain, Alexander Ushakov

Research output: Contribution to journalArticlepeer-review

49 Scopus citations

Abstract

The conjugacy search problem in a group G is the problem of recovering an x ∈ G from given g ∈ 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 et 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 ∈ G such that h = ygx for given g, h ∈ 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.

Original languageEnglish
Pages (from-to)285-289
Number of pages5
JournalApplicable Algebra in Engineering, Communications and Computing
Volume17
Issue number3-4
DOIs
StatePublished - Aug 2006

Keywords

  • Conjugacy search problem
  • Decomposition problem
  • Public key exchange

Fingerprint

Dive into the research topics of 'The conjugacy search problem in public key cryptography: Unnecessary and insufficient'. Together they form a unique fingerprint.

Cite this