Cryptanalysis of a noncommutative key exchange protocol

Giacomo  Micheli

doi:10.3934/amc.2015.9.247

Article Contents

2015, Volume 9, Issue 2: 247-253. Doi: 10.3934/amc.2015.9.247

This issue Previous Article Families of nested completely regular codes and distance-regular graphs Next Article

Cryptanalysis of a noncommutative key exchange protocol

Giacomo Micheli^1,

1.
Institut für Mathematik, Universität Zürich, Winterthurerstrasse 190, Zürich

Received: June 30, 2014

Revised: January 31, 2015

Published: April 2015

Abstract Related Papers Cited by

Abstract

In the papers by Alvarez et al. and Pathak and Sanghi a non-commutative based public key exchange is described. A similiar version of it has also been patented (US7184551). In this paper we present a polynomial time attack that breaks the variants of the protocol presented in the two papers. Moreover we show that breaking the patented cryptosystem US7184551 can be easily reduced to factoring. We also give some examples to show how efficiently the attack works.

Keywords:

Mathematics Subject Classification: Primary: 94A60; Secondary: 11T71.

Citation:

Related Papers

Cited by

References

[1]	R. Álvarez, F. Martinez, J. Vicent and A. Zamora, A new public key cryptosystem based on matrices, in 6th WSEAS Int. Conf. Inform. Secur. Privacy, Tenerife, Spain, 2007.
[2]	R. Álvarez, L. Tortosa, J. Vicent and A. Zamora, Analysis and design of a secure key exchange scheme, Inform. Sci., 179 (2009), 2014-2021.doi: 10.1016/j.ins.2009.02.008.
[3]	M. F. Atiyah and I. G. MacDonald, Introduction to Commutative Algebra, Westview Press, 1969.
[4]	N. Courtois, A. Klimov, J. Patarin and A. Shamir, Efficient algorithms for solving overdefined systems of multivariate polynomial equations, in Advances in Cryptology - EUROCRYPT 2000 (ed. B. Preneel), Springer, Berlin, 2000, 392-407.doi: 10.1007/3-540-45539-6_27.
[5]	W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Inf. Theory, IT-22 (1976), 644-654.
[6]	T. ElGamal, A public-key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inf. Theory, 31 (1985), 469-472.doi: 10.1109/TIT.1985.1057074.
[7]	J.-C. Faugère, A new efficient algorithm for computing Gröbner bases (F4), J. Pure Appl. Algebra, 139 (1999), 61-88.doi: 10.1016/S0022-4049(99)00005-5.
[8]	J. Hoffstein, J. Pipher and J. H. Silverman, NTRU: A ring-based public key cryptosystem, in Algorithmic Number Theory, 1998, 267-288.doi: 10.1007/BFb0054868.
[9]	G. Maze and C. Monico and J.Rosenthal, Public key cryptography based on semigroup actions, Adv. Math. Commun., 1 (2007), 489-507.doi: 10.3934/amc.2007.1.489.
[10]	G. Micheli, J. Rosenthal and P. Vettori, Linear spanning sets for matrix spaces, preprint, arXiv:1409.3020
[11]	G. Micheli and M. Schiavina, A general construction for monoid-based knapsack protocols, Adv. Math. Commun., 8 (2014), 343-358.doi: 10.3934/amc.2014.8.343.
[12]	D. Naccache and J. Stern, A new public key cryptosystem, in Advances in Cryptology, EUROCRYPT, 1997, 27-36.doi: 10.1007/3-540-69053-0_3.
[13]	D. Naccache and J. Stern, A new public key cryptosystem based on higher residues, in Proc. 5th ACM Conf. Computer Commun. Secur., San Francisco, 1998, 59-66.doi: 10.1145/288090.288106.
[14]	H. K. Pathak and M. Sanghi, Public key cryptosystem and a key exchange protocol using tools of non-abelian groups, Int. J. Comput. Sci. Engin., 2 (2010), 1029-1033.
[15]	D. Pointcheval, Rabin cryptosystem, in Encyclopedia of Cryptography and Security, Springer, 2011, 1013-1014.doi: 10.1007/978-1-4419-5906-5_151.
[16]	R. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, 21 (1978), 120-126.doi: 10.1145/359340.359342.
[17]	Slavin, Public key cryptography using matrices, available at http://www.patentgenius.com/patent/7184551.html, 2007.
[18]	R. Steinwandt and A. S. Corona, Cryptanalysis of a 2-party key establishment based on a semigroup action problem, Adv. Math. Commun., 5 (2011), 87-92.doi: 10.3934/amc.2011.5.87.
[19]	M. I. G. Vasco, A. L. Pérez del Pozo, P. T. Duarte and J. L. Villar, Cryptanalysis of a key exchange scheme based on block matrices, Inf. Sc., 276 (2014), 319-331.doi: 10.1016/j.ins.2013.11.009.