## CryptoDB

### Alexander Ushakov

#### Affiliation: Stevens Institue of Technology

#### Publications

**Year**

**Venue**

**Title**

2007

PKC

2005

EPRINT

A new key exchange protocol based on the decomposition problem
Abstract

In this paper we present a new key establishment protocol based on the decomposition problem in non-commutative groups which is: given two elements w, w_1 of the platform group G and two subgroups A, B of G (not necessarily distinct), find elements a in A, b in B such that w_1 = a w b. Here we introduce two new ideas that improve the security of key establishment protocols based on the decomposition problem.
In particular, we conceal (i.e., do not publish explicitly) one of the subgroups A, B, thus introducing an additional computationally hard problem for the adversary, namely, finding the centralizer of a given
finitely generated subgroup.

2004

EPRINT

The conjugacy search problem in public key cryptography: unnecessary and insufficient
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.

#### Coauthors

- Jintai Ding (1)
- Matvei Kotov (1)
- Alexei Miasnikov (1)
- Alex D. Myasnikov (1)
- Alexei G. Myasnikov (2)
- Vladimir Shpilrain (4)