zbMATH — the first resource for mathematics

Tropical cryptography. II: Extensions by homomorphisms. (English) Zbl 1451.14179
The aim of this paper is to strengthen results obtained in [D. Grigoriev and V. Shpilrain, Commun. Algebra 42, No. 6, 2624–2632 (2014; Zbl 1301.94114)]. Earlier article employed tropical or min-plus algebras (algebras with the usual operations of addition and multiplication replaced by the operations \(\min(x, y)\) and \(x+y\), respectively) as platforms for two cryptographic schemes by mimicking two well-known “classical” schemes. The main benefit of using tropical algebras as platforms is unparalleled efficiency because in tropical schemes, one does not have to perform any multiplications of numbers since tropical multiplication is the usual addition. Max-plus algebras have some inherent weaknesses since powers of matrices exhibit certain patterns in such algebraic setting. This was exploited in [M. Kotov and A. Ushakov, J. Math. Cryptol. 12, No. 3, 137–141 (2018; Zbl 1397.94082)] to arrange an attack on one of the schemes in the original paper.
The present paper uses extensions of tropical matrix algebras by homomorphisms as platforms in an attempt to destroy patterns in powers of elements of a platform algebra. These extensions are called semidirect products since they are similar to a well-known operation (with the same name) in (semi)group theory. The author uses adjoint multiplication (\(a\circ b=a+b+ab\)) to construct homomorphisms and builds a special version of the standard Diffie-Hellman Public key exchange protocol.
14T90 Applications of tropical geometry
94A60 Cryptography
15A80 Max-plus and related algebras
Full Text: DOI
[1] Butkovic, P., Max-Linear Systems: Theory and Algorithms, (2010), London: Springer, London · Zbl 1202.15032
[2] Grigoriev, D.; Ponomarenko, I., Constructions in public-key cryptography over matrix groups, Contemp. Math. Am. Soc., 418, 103-119, (2006) · Zbl 1207.94053
[3] Grigoriev, D.; Shpilrain, V., Tropical cryptography, Commun. Algebra, 42, 6, 2624-2632, (2014) · Zbl 1301.94114
[4] Habeeb, M.; Kahrobaei, D.; Koupparis, C.; Shpilrain, V., Public key exchange using semidirect product of (semi)groups, ACNS 2013. Lecture Notes in Computer Science, 7954, 475-486, (2013) · Zbl 1356.94059
[5] Kahrobaei, D.; Shpilrain, V., Using semidirect product of (semi)groups in public key cryptography, CiE 2016. Lecture Notes in Computer Science, 9709, 132-141, (2016) · Zbl 1353.94055
[6] Kotov, M.; Ushakov, A., Analysis of a key exchange protocol based on tropical matrix algebra, J. Math. Cryptol., 12, 137-141, (2018) · Zbl 1397.94082
[7] Menezes, A.; van Oorschot, P.; Vanstone, S., Handbook of Applied Cryptography, (1996), Boca Raton, FL: CRC-Press, Boca Raton, FL · Zbl 0868.94001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.