General algebraic cryptographic key exchange scheme and its cryptanalysis

V. A. Roman'kov ; A. A. Obzor

Prikladnaâ diskretnaâ matematika, no. 3 (2017), pp. 52-61.

Résumé

We show that many known schemes of the cryptographic key public exchange protocols in algebraic cryptography using two-sided multiplications are the special cases of a general scheme of this type. In most cases, such schemes are built on the platforms that are subsets of some linear spaces. They have been repeatedly compromised by the linear decomposition method introduced by the first author. The method allows to compute the exchanged keys without computing any private data and, consequently, without solving the hard algorithmic problems on which the assumptions are based. Here, we show that this method can be successfully applied to the following general scheme and, thus, is a universal one. The general scheme proceeds as follows. Let $G$ be an algebraic system with the associative multiplication, for example, a group chosen as the platform. We assume that $G$ is a subset of a finitely dimensional linear space. First, some public elements $g_1,\dots,g_k\in G$ are taken. Then the correspondents, Alice and Bob, sequentially publicise the elements of the form $\varphi_{a,b}(f)$ for some $a,b\in G$, where $\varphi_{a,b}(f)=afb$, $f\in G$ and $f$ is a given or previously built element. The exchanged key has the form \begin{equation*} K=\varphi_{a_l, b_l}(\varphi_{a_{l-1},b_{l-1}}(\dots(\varphi_{a_1,b_1}(g_i)\dots))=a_la_{l-1}\dots a_1g_ib_1\dots b_{l-1}b_l. \end{equation*} We suppose that Alice chooses parameters $a,b$ in a given finitely generated subgroup $A$ of $G$, and Bob picks up parameters $a,b$ in a finitely generated subgroup $B$ of $G$ to construct their transformations of the form $\varphi_{a,b}$. Under some natural assumptions about $G,A$ and $B,$ we show that an intruder can efficiently calculate the exchanged key $K$ without calculation of the transformations used in the scheme.

Détail

Keywords: cryptography, key exchange, linear decomposition.
Mots-clés : cryptanalisis

Bibliographie

[1] Andrecut M., A Matrix Public Key Cryptosystem, 31 May 2015, arXiv: 1506.00277v1[cs.CR]

[2] Wang X., Xu C., Li G., et al., Double Shielded Public Key Cryptosystems, Cryptology ePrint Archive, Report 2014/558, Version 20140718:185200, , 2014 https://eprint.iacr.org/2014/558

[3] Stickel E., “A new method for exchanging secret keys”, Proc. Third Intern. Conf. ICITA 05, Contemp. Math., 2, 2005, 426–430

[4] Harley B., Harley T., Group Ring Cryptography, 9 April 2011, 20 pp., arXiv: 1104.1724v1[math.GR]

[5] Harley T., Cryptographic Schemes, Key Exchange, Public Key, May 2013, 19 pp., arXiv: 1305.4063v1[cs.CR]

[6] Shpilrain V., Ushakov A., “A new key exchange protocol based on the decomposition problem”, Algebraic Methods in Cryptography, Contemp. Math., 418, 2006, 161–167 | DOI | MR | Zbl

[7] Myasnikov A., Shpilrain V., Ushakov A., Group-Based Cryptography., Advances courses in Math., CRM, Barselona, Birkhäuser Verlag, Basel–Berlin–New York, 2008, 183 pp. | MR | Zbl

[8] Myasnikov A., Shpilrain V., Ushakov A., Non-commutative Cryptography and Complexity of Group-Theoretic Problems, Amer. Math. Soc. Surveys and Monographs, Amer. Math. Soc., Providence, RI, 2011, 385 pp. | DOI | MR | Zbl

[9] Ko K. H., Lee S. J., Cheon J. H., et al., “New public-key cryptosystem using braid groups”, CRYPTO 2000, LNCS, 1880, 2000, 166–183 | MR | Zbl

[10] Roman'kov V. A., Introduction to Cryptography, Lecture Course, Forum Publ., Moscow, 2012, 240 pp. (in Russian)

[11] Roman'kov V. A., Algebraic Cryptography, OmSU Publ., Omsk, 2013, 135 pp. (in Russian)

[12] Roman'kov V. A., “Cryptographic analysis of some known encryption schemes using automorphisms”, Prikladnaya Diskretnaya Matematika, 2013, no. 3(21), 35–51 (in Russian)

[13] Myasnikov A. G., Roman'kov V. A., “A linear decomposition attack”, Groups Complexity Cryptology, 7 (2015), 81–94 | DOI | MR | Zbl

[14] Roman'kov V. A., Menshov A. V., Cryptanalysis of Andrecut's Public Key Cryptosystem, 6 Jul. 2015, arXiv: 1507.01496v1[math.GR]

[15] Gornova M. N., Kukina E. G., Roman'kov V. A., “Cryptographic analysis of the autentification protocol by Ushakov–Shpilrain based on the bi-twisted conjugacy problem”, Prikladnaya Diskretnaya Matematika, 2015, no. 2(28), 46–53 (in Russian)

[16] Roman'kov V. A., “A polynomial time algorithm for the braid double shielded public key cryptosystems”, Bulletin of the Karaganda University. Mathematics Series, 2014, no. 4(84), 110–115; 17 Dec. 2014, arXiv: 1412.5277v1[math.GR]

[17] Roman'kov V. A., “A nonlinear decomposition attack”, Groups Complexity Cryptology, 8 (2017), 197–207 | MR

[18] Eick B., Kahrobaei D., Polycyclic Groups: A New Platform for Cryptology?, 3 Nov. 2004, 7 pp., arXiv: math/0411077[math.GR]

[19] Gryak K. J., Kahrobaei D., “The status of polycyclic group-based cryptography: A survey and open problems”, Groups Complexity Cryptology, 8 (2017), 171–186 | MR

[20] Cavallo B., Kahrobaei D., A Family of Polycyclic Groups over which the Conjugacy Problem is NP-complete, 19 Mar. 2014, 14 pp., arXiv: 1403.4153v2[math.GR] | MR

[21] Cheon J. H., Jun B., “A polynomial time algorithm for the Braid Diffie–Hellman Conjugacy Problem”, CRYPTO-2003, LNCS, 2729, 2003, 212–225 | DOI | MR | Zbl