Thompson's group and public key cryptography

Vladimir Shpilrain, Alexander Ushakov

Research output: Contribution to journalConference articlepeer-review

77 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)151-163
Number of pages13
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3531
DOIs
StatePublished - 2005
EventThird International Conference on Applied Cryptography and Network Security, ACNS 2005 - New York, NY, United States
Duration: 7 Jun 200510 Jun 2005

Fingerprint

Dive into the research topics of 'Thompson's group and public key cryptography'. Together they form a unique fingerprint.

Cite this