zbMATH — the first resource for mathematics

Tropical cryptography. (English) Zbl 1301.94114
This paper analyses replacement of classical algebraic operations with ones based on tropical algebras for two selected cryptographic schemas. It shows that this approach has two primary advantages: it eliminates known vulnerability of selected schemas against various linear algebra attacks and has improved efficiency as one does not have to perform any multiplications since tropical multiplication is the usual addition.
Tropical algebras are built over tropical semiring \(S\) with two operations \(x\oplus y=\min(x,y)\) and \(x\otimes y=x+y\). If we replace linear algebra with tropical one in a key exchange protocol built on an idea of E. Stickel [A new method for exchanging secret keys, Proc. Third Int. Conf. on Information Technology and Applications (ICITA ’05), Vol. 2, 426–430 (2005), doi:10.1109/ICITA.2005.33], we are able to show that it now resists the vulnerability of original approach described in [V. Shpilrain, in: Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008, Lect. Notes Comput. Sci. 5010, 283–288 (2008; Zbl 1142.94360)]. Another cryptographic schema analysed in this paper that would be susceptible to linear algebra attack in the classical case is a public key encryption scheme described in [T. T. Moh, Commun. Algebra 27, No. 5, 2207–2222 (1999; Zbl 0933.94022)]. Two known attacks were analysed and proven infeasible.

94A60 Cryptography
14T99 Tropical geometry
15A80 Max-plus and related algebras
Full Text: DOI arXiv
[1] DOI: 10.1016/j.ipl.2009.11.007 · Zbl 1206.68284 · doi:10.1016/j.ipl.2009.11.007
[2] DOI: 10.1007/978-1-84996-299-5 · Zbl 1202.15032 · doi:10.1007/978-1-84996-299-5
[3] Garey M., Computers and Intractability, A Guide to NP-Completeness (1979)
[4] Goubin , L. , Courtois , N. ( 2000 ). Cryptanalysis of the TTM cryptosystem. In:ASIACRYPT 2000, Lecture Notes in Comput. Sci.Vol. 1976. pp. 44–57 . · Zbl 0980.94017 · doi:10.1007/3-540-44448-3_4
[5] DOI: 10.1090/conm/418/07949 · doi:10.1090/conm/418/07949
[6] Maze G., Advances in Mathematics of Communications 4 pp 489– (2007)
[7] DOI: 10.1201/9781439821916 · doi:10.1201/9781439821916
[8] DOI: 10.1007/978-3-0346-0048-4 · doi:10.1007/978-3-0346-0048-4
[9] DOI: 10.1080/00927879908826559 · Zbl 0933.94022 · doi:10.1080/00927879908826559
[10] Mullan C., Cryptanalysing Variants of Stickel’s Key Agreement Scheme · Zbl 1211.94033 · doi:10.1515/jmc.2011.003
[11] Shpilrain , V. ( 2008 ). Cryptanalysis of Stickel’s key exchange scheme. In:Computer Science in Russia 2008, Lecture Notes Comp. Sc.Vol. 5010. pp. 283–288 . · Zbl 1142.94360
[12] DOI: 10.3934/amc.2011.5.87 · Zbl 1213.94134 · doi:10.3934/amc.2011.5.87
[13] Stickel , E. ( 2005 ). A new method for exchanging secret keys. In:Proc. of the Third International Conference on Information Technology and Applications (ICITA’05).Vol. 2. pp. 426–430 . · doi:10.1109/ICITA.2005.33
[14] DOI: 10.1016/j.jsc.2005.11.006 · Zbl 1121.14047 · doi:10.1016/j.jsc.2005.11.006
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.