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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Anshel, I., Anshel, M., Goldfeld, D.: An algebraic method for public-key cryptography. Math. Res. Lett. 6, 287–291 (1999)
Cannon, J.W., Floyd, W.J., Parry, W.R.: Introductory notes on Richard Thompson’s groups. L’Enseignement Mathematique 42(2), 215–256 (1996)
Cha, J.C., Ko, K.H., Lee, S.J., Han, J.W., Cheon, J.H.: An efficient implementation of braid groups. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 144–156. Springer, Heidelberg (2001)
Hofheinz, D., Steinwandt, R.: A practical attack on some braid group based cryptographic primitives. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 187–198. Springer, Heidelberg (2002)
Hughes, J., Tannenbaum, A.: Length-based attacks for certain group based encryption rewriting systems, Workshop SECI02 Securitè de la Communication sur Intenet, Tunis, Tunisia (September 2002), http://www.storagetek.com/hughes/
Ko, K.H., Lee, S.J., Cheon, J.H., Han, J.W., Kang, J., Park, C.: New public-key cryptosystem using braid groups. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 166–183. Springer, Heidelberg (2000)
Shpilrain, V.: Assessing security of some group based cryptosystems. Contemp. Math., Amer. Math. Soc. 360, 167–177 (2004)
Shpilrain, V., Ushakov, A.: The conjugacy search problem in public key cryptography: unnecessary and insufficient, Applicable Algebra in Engineering, Communication and Computing (to appear), http://eprint.iacr.org/2004/321/
Shpilrain, V., Zapata, G.: Combinatorial group theory and public key cryptography. Applicable Algebra in Engineering, Communication and Computing (to appear)
Sims, C.: Computation with finitely presented groups, Encyclopedia of Mathematics and its Applications, vol. 48. Cambridge University Press, Cambridge (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shpilrain, V., Ushakov, A. (2005). Thompson’s Group and Public Key Cryptography. In: Ioannidis, J., Keromytis, A., Yung, M. (eds) Applied Cryptography and Network Security. ACNS 2005. Lecture Notes in Computer Science, vol 3531. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11496137_11
Download citation
DOI: https://doi.org/10.1007/11496137_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26223-7
Online ISBN: 978-3-540-31542-1
eBook Packages: Computer ScienceComputer Science (R0)