TY - JOUR
T1 - The conjugacy search problem in public key cryptography
T2 - Unnecessary and insufficient
AU - Shpilrain, Vladimir
AU - Ushakov, Alexander
PY - 2006/8
Y1 - 2006/8
N2 - 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.
AB - 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.
KW - Conjugacy search problem
KW - Decomposition problem
KW - Public key exchange
UR - http://www.scopus.com/inward/record.url?scp=33746352068&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33746352068&partnerID=8YFLogxK
U2 - 10.1007/s00200-006-0009-6
DO - 10.1007/s00200-006-0009-6
M3 - Article
AN - SCOPUS:33746352068
SN - 0938-1279
VL - 17
SP - 285
EP - 289
JO - Applicable Algebra in Engineering, Communications and Computing
JF - Applicable Algebra in Engineering, Communications and Computing
IS - 3-4
ER -