An improvement of cryptographic schemes based on the conjugacy search problem

V. A. Roman'kov

Prikladnaya Diskretnaya Matematika. Supplement, no. 14 (2021), pp. 114-118.

Résumé

The key exchange protocol is a method of securely sharing cryptographic keys over a public channel. It is considered as important part of cryptographic mechanism to protect secure communications between two parties. The Diffie — Hellman protocol, based on the discrete logarithm problem, which is generally difficult to solve, is the most well-known key exchange protocol. One of the possible generalizations of the discrete logarithm problem to arbitrary noncommutative groups is the so-called conjugacy search problem: given two elements $g, h$ of a group $G$ and the information that $g^x = h$ for some $x \in G$, find at least one particular element $x$ like that. Here $g^x$ stands for $x^{-1}gx.$ This problem is in the core of several known public key exchange protocols, most notably the one due to Anshel et al. and the other due to Ko et al. In recent years, effective algebraic cryptanalysis methods have been developed that have shown the vulnerability of protocols of this type. The main purpose of this short note is to describe a new tool to improve protocols based on the conjugacy search problem. This tool has been introduced by the author in some recent papers. It is based on a new mathematical concept of a marginal set.

Détail

Keywords: cryptography, key exchange protocol, conjugacy search problem, marginal set, algorithm.

Bibliographie

[1] Diffie W., Hellman M. I., “New directions in cryptography”, IEEE Trans. Inform. Theory, 22 (1976), 644–654 | DOI | MR | Zbl

[2] Anshel I., Anshel M., Goldfeld D., “An algebraic method for public-key cryptography”, Math. Res. Lett., 6:3 (1999), 287–291 | DOI | MR | Zbl

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

[4] Roman'kov V. A., Algebraic Cryptography, Omsk State University Publ., Omsk, 2013, 136 pp. (in Russian)

[5] Myasnikov A. G., Roman'kov V. A., “A linear decomposition attack”, Groups, Complex., Cryptol., 7:1 (2015), 81–94 | DOI | MR | Zbl

[6] Roman'kov V. A., “Cryptanalysis of some schemes applying automorphisms”, Prikladnaya Discretnaya Matematika, 2013, no. 3, 35–51 (in Russian) | DOI | Zbl

[7] Roman'kov V. A., “A nonlinear decomposition attack”, Groups, Complex., Cryptol., 8:2 (2016), 197–207 | MR | Zbl

[8] Roman'kov V. A., Essays in Algebra and Cryptology: Algebraic Cryptanalysis, Omsk State University Publ., Omsk, 2018, 207 pp.

[9] Tsaban B., “Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography”, J. Cryptol., 28:3 (2015), 601–622 | DOI | MR | Zbl

[10] Ben-Zvi A., Kalka A., Tsaban B., “Cryptanalysis via algebraic span”, LNCS, 10991, 2018, 255–274 | MR | Zbl

[11] Roman'kov V. A., “An improved version of the AAG cryptographic protocol”, Groups, Complex., Cryptol., 11:1 (2019), 35–42 | DOI | MR

[12] Roman'kov V, A., “Algebraic cryptanalysis and new security enhancement”, Moscow J. Combinat. Number Theory, 9:2 (2020), 123–146 | DOI | MR | Zbl

[13] Roman'kov V. A., “An improvement of the Diffie-Hellman noncommutative protocol”, Designs, Codes, Cryptogr. (to appear)