  Recently, several public key exchange protocols based on symbolic computation
in non-commutative (semi)groups were proposed as a more efficient alternative
to well established protocols based on numeric computation. Notably, the
protocols due to Anshel-Anshel-Goldfeld and Ko-Lee et al. exploited the
conjugacy search problem in groups, which is a ramification of the discrete
logarithm problem. However, it is a prevalent opinion now that the conjugacy
search problem alone is unlikely to provide sufficient level of security no
matter what particular group is chosen as a platform.
  In this paper we employ another problem (we call it the decomposition
problem), which is more general than the conjugacy search problem, and we
suggest to use R. Thompson's group as a platform. This group is well known in
many areas of mathematics, including algebra, geometry, and analysis. It also
has several properties that make it fit for cryptographic purposes. In
particular, we show here that the word problem in Thompson's group is solvable
in almost linear time.
