On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product. (English) Zbl 1491.15030
Summary: Tropical linear algebra has been recently put forward by D. Grigoriev and V. Shpilrain [Commun. Algebra 42, No. 6, 2624–2632 (2014; Zbl 1301.94114); Commun. Algebra 47, No. 10, 4224–4229 (2019; Zbl 1451.14179)] as a promising platform for implementation of protocols of Diffie-Hellman and Stickel type. Based on the CSR expansion of tropical matrix powers, we suggest a simple algorithm for the following tropical discrete logarithm problem: “Given that \(A=V\otimes F^{\otimes t}\) for a unique \(t\) and matrices \(A, V, F\) of appropriate dimensions, find this \(t\).” We then use this algorithm to suggest a simple attack on a protocol based on the tropical semidirect product. The algorithm and the attack are guaranteed to work in some important special cases and are shown to be efficient in our numerical experiments.
MSC:
| 15A80 | Max-plus and related algebras |
| 15A23 | Factorization of matrices |
| 94A60 | Cryptography |
| 14T90 | Applications of tropical geometry |
| 14T10 | Foundations of tropical geometry and relations with algebra |
References:
| [1] | Baccelli, F.; Cohen, G.; Olsder, G. J.; Quadrat, J. P., Synchronization and Linearity: An Algebra for Discrete Event Systems (1992), Chichester, UK: John Wiley & Sons Ltd · Zbl 0824.93003 |
| [2] | Balcer, Y.; Veinott, A. F., Computing a graph’s period quadratically by node condensation, Discr. Math, 4, 4, 295-303 (1973) · Zbl 0258.05114 · doi:10.1016/0012-365X(73)90166-0 |
| [3] | Butkovič, P., Max algebra: the linear algebra of combinatorics?, Linear Algebra Appl, 367, 313-335 (2003) · Zbl 1022.15017 · doi:10.1016/S0024-3795(02)00655-9 |
| [4] | Butkovič, P., Max-Linear Systems: Theory and Algorithms (2010), London, UK: Springer Science & Business Media · Zbl 1202.15032 |
| [5] | Butkovič, P.; Schneider, H.; Sergeev, S.; Tam, B.-S., Two cores of a nonnegative matrix, Linear Algebra Appl, 439, 7, 1929-1954 (2013) · Zbl 1305.15073 · doi:10.1016/j.laa.2013.05.029 |
| [6] | Cochet-Terrasson, J.; Cohen, G.; Gaubert, S.; Gettrick, M. M.; Quadrat, J.-P., Numerical computation of spectral elements in max-plus algebra, Proceedings of the IFAC conference on systems structure and control, 699-706 (1998) |
| [7] | Cohen, G.; Dubois, D.; Quadrat, J.-P.; Viot, M. (1983) |
| [8] | Cohen, G.; Dubois, D.; Quadrat, J.-P.; Viot, M., A linear system theoretic view of discrete event processes and its use for performance evaluation in manufacturing, IEEE Trans. Automat. Contr, 30, 3, 210-220 (1985) · Zbl 0557.93005 · doi:10.1109/TAC.1985.1103925 |
| [9] | Grigoriev, D.; Shpilrain, V., Tropical cryptography, Commun. Algebra, 42, 6, 2624-2632 (2014) · Zbl 1301.94114 · doi:10.1080/00927872.2013.766827 |
| [10] | Grigoriev, D.; Shpilrain, V., Tropical cryptography II. extensions by homomorphisms, Commun. Algebra, 47, 10, 4224-4229 (2019) · Zbl 1451.14179 · doi:10.1080/00927872.2019.1581213 |
| [11] | Heidergott, B.; Olsder, G. J.; Van der Woude, J., Max Plus at Work (2006), Princeton, NJ: Princeton University Press · Zbl 1130.93003 |
| [12] | Isaac, S.; Kahrobaei, D., A closer look at the tropical cryptography, Int. J. Comput. Math.: Comput. Syst. Theory, 6, 2, 137-142 (2021) · doi:10.1080/23799927.2020.1862303 |
| [13] | Kotov, M.; Ushakov, A., Analysis of a key exchange protocol based on tropical matrix algebra, J. Math. Cryptol., 12, 3, 137-141 (2018) · Zbl 1397.94082 · doi:10.1515/jmc-2016-0064 |
| [14] | Merlet, G.; Nowak, T.; Schneider, H.; Sergeev, S., Generalizations of bounds on the index of convergence to weighted digraphs, Discr. Appl. Math, 178, 121-134 (2014) · Zbl 1300.05121 · doi:10.1016/j.dam.2014.06.026 |
| [15] | Merlet, G.; Nowak, T.; Sergeev, S., Weak CSR expansions and transience bounds in max-plus algebra, Linear Algebra Appl, 461, 163-199 (2014) · Zbl 1314.15018 · doi:10.1016/j.laa.2014.07.027 |
| [16] | Muanalifah, A.; Sergeev, S., Modifying the tropical version of stickel’s key exchange protocol, Applmath, 65, 6, 727-753 (2020) · Zbl 07285954 · doi:10.21136/AM.2020.0325-19 |
| [17] | Nachtigall, K., Powers of matrices over an extremal algebra with applications to periodic graphs, Math. Methods Oper. Res, 46, 1, 87-102 (1997) · Zbl 0885.90111 · doi:10.1007/BF01199464 |
| [18] | Olsder, G.-J.; Roos, K.; van Egmond, R. J., An efficient algorithm for critical circuits and finite eigenvectors in the max-plus algebra, Linear Algebra Appl, 295, 1-3, 231-240 (1999) · Zbl 0947.90018 · doi:10.1016/S0024-3795(99)00120-2 |
| [19] | Rudy, D.; Monico, C., Remarks on a tropical key exchange system, J. Math. Cryptol., 15, 1, 280-283 (2020) · Zbl 1466.94036 · doi:10.1515/jmc-2019-0061 |
| [20] | Sergeev, S.; Schneider, H., CSR expansions of matrix powers in max algebra, Trans. Amer. Math. Soc, 364, 11, 5969-5994 (2012) · Zbl 1307.15036 · doi:10.1090/S0002-9947-2012-05605-4 |
| [21] | Vorobyev, N. N., Extremal algebra of positive matrices, Elektronische Informationsverarbeitung Und Kybernetik, 3, 39-71 (1967) |
| [22] | Vorobyev, N. N., Extremal algebra of non-negative matrices, Elektronische Informationsverarbeitung Und Kybernetik, 6, 303-311 (1970) |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
