Computer Science ›› 2022, Vol. 49 ›› Issue (6A): 571-574.doi: 10.11896/jsjkx.210700046

• Information Security • Previous Articles     Next Articles

Security Analysis of A Key Exchange Protocol Based on Tropical Semi-ring

HUANG Hua-wei1, LI Chun-hua2   

  1. 1 School of Mathematical Sciences,Guizhou Normal University,Guiyang 550001,China
    2 School of Science,East China Jiaotong University,Nanchang 330013,China
  • Online:2022-06-10 Published:2022-06-08
  • About author:HUANG Hua-wei,born in 1978,asso-ciate professor.His main researchin-terests include algebra and cryptography.
    LI Chun-hua,born in 1973,professor.His main research interests include algebra and cryptography.
  • Supported by:
    National Natural Science Foundation of China(61462016,61962011) and Science and Technology Foundation of Guizhou Province(QIANKEHEJICHU-ZK[2021]313,[2019]1221).

Abstract: This paper analyses the security of a key exchange protocol based on tropical semi-ring proposed by Grigoriev et al,and provides a method of algebraic cryptanalysis.Some tropical matrix equations are constructed according to the public information of the protocol.And the shared key of the protocol is obtained by solving the linear system of equations over tropical semi-ring.The parameters of the protocol should be increased appropriately for resisting the algebraic cryptanalysis.

Key words: Computational complexity, Key exchange protocol, Tropical matrix, Tropical semi-ring

CLC Number: 

  • TN918
[1] MAZE G,MONICO C,ROSENTHAL J.Public key cryptography based on semigroup actions[J].Advances of Mathematics of Communications,2007,1(4):489-507.
[2] HUANG H,XIAO G.A Key Establishment Protocol Based on Conjugacy Search Problem in Clifford Semigroups[J].Computer Science,2007,34(2):76-78.
[3] HUANG H,ZHANG J,WEN Y,et al.Public key encryption scheme based on a class of matrix semigroup action[J].Journal on Communications,2007,28(8A):5-12.
[4] BAUMSLAG G,FAZIO N,NICOLOSI A R,et al.Generalized learning problems and applications to non-commutative cryptography[C]//Provable Security 2011.2011:324-339.
[5] BAGHERI K,SADEGHI M R,PANARIO D.A non-commutative cryptosystem based on quaternion algebras[J].Designs,Codes and Cryptography,2018,86:2345-2377.
[6] CLIMENT J J,NAVARRO P R,TORTOSA L.An extension of the noncommutative Bergman's ring with a large number of noninvertible elements[J].Applicable Algebra in Engineering,Communication and Computing,2014,25(5):347-361.
[7] ZHANG Y.Cryptanalysis of a key exchange protocol based on the ring Ep(m)[J].Applicable Algebra in Engineering,Communication and Computing,2018,29:103-112.
[8] GRIGORIEV D.Complexity of solving Tropical linear systems[J].Computational Complexity,2013,22:71-88.
[9] GRIGORIEV D,SHPILRAIN V.Tropical cryptography[J].Com-munications in Algebra,2014,42(6):2624-2632.
[10] KOTOV M,USHAKOV A.Analysis of a key exchange protocol based on tropical matrix algebra[J].Journal of Mathematical Cryptology,2018,12(3):137-141.
[11] GRIGORIEV D,SHPILRAIN V.Tropical cryptography II:Extensions by homomorphisms[J].Communications in Algebra,2019,47(10):4224-4229.
[1] HAN Jie, CHEN Jun-fen, LI Yan, ZHAN Ze-cong. Self-supervised Deep Clustering Algorithm Based on Self-attention [J]. Computer Science, 2022, 49(3): 134-143.
[2] YOU Ling, GUAN Zhang-jun. Low-complexity Subcarrier Allocation Algorithm for Underwater OFDM Acoustic CommunicationSystems [J]. Computer Science, 2021, 48(6A): 387-391.
[3] ZHU Kai, WU Guo-qing, YUAN Meng-ting. On Hardness of Approximation for Optimized Problem of Synchronizing Partially Specified Deterministic Finite Automata [J]. Computer Science, 2020, 47(5): 14-21.
[4] YU Jian-jun, WU Chun-ming. Computational Complexity Analysis of Virtual Network Mapping Problem [J]. Computer Science, 2018, 45(11): 87-91.
[5] LU Zhao and ZHU Xiao-shu. Research on Image Processing Algorithm Based on Compressed Sensing [J]. Computer Science, 2017, 44(6): 312-316.
[6] CEN Yue-feng, WANG Wan-liang, YAO Xin-wei, WANG Chao-chao and PAN Tie-qiang. Decision Tree Based Coding Unit Splitting Algorithm for HEVC [J]. Computer Science, 2016, 43(4): 308-312.
[7] HE Kun,YAO Peng-cheng and LI Li-wen. Complete Algorithm for 2D Rectangular Packing Problem [J]. Computer Science, 2014, 41(8): 55-59.
[8] . Computational Complexity of Probabilistic Inference in Icing Graphical Model [J]. Computer Science, 2013, 40(2): 253-256.
[9] SHU Ming-lei,TAN Cheng-xiang,TAN Bo. Secure Communication Scheme of Mobile VPN Based on IKE Protocol [J]. Computer Science, 2010, 37(5): 84-86.
[10] . [J]. Computer Science, 2007, 34(4): 158-162.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!