Computer Science

Computer Science ›› 2025, Vol. 52 ›› Issue (6A): 240600036-6.doi: 10.11896/jsjkx.240600036

• Information Security • Previous Articles     Next Articles

Dual-platform Key Agreement Protocol Based on Semidirect Product

ZHANG Jing1,2, WANG Yuping3   

  1. 1 Modern Industrial Innovation Practice Center,Dongguan Polytechnic College,Dongguan,Guangdong 523808,China
    2 School of Computer Science and Engineering,Sun Yat-sen University,Guangzhou 510006,China
    3 School of Computer Science and Technology,Xidian University,Xi’an 710075,China
  • Online:2025-06-16 Published:2025-06-12
  • About author:ZHANG Jing,born in 1981,master,associate professor.Her main research interests include cryptography and information security.
  • Supported by:
    National Natural Science Foundation of China(62272367) and Dongguan Science and Technology of Social Deve-lopment Project(20221800905832).

PDF (PC)

88

Abstract: Cryptosystems based on non-commutative algebra have advantages in resisting quantum computing attacks,combinatorial group theory,as an important source of non-commutative algebra,has been widely applied in cryptography field.By utilizing some mathematical problems on combination groups,cryptographic schemes resistant to quantum computing attacks can be constructed.Semidirect products are an important concept in combinatorial group theory and the decomposition search problem on certain groups is intractable,so a non-commutative key agreement protocol based on which has been introduced.Bythe method of constructing semidirect products,a category of cryptographic-friendly non-commutative groups employed by both parties of communication as cryptographic platforms is constructed by adopting non-commutative groups and cyclic groups oftheir bijections.Then,the key agreement is achieved through a single interaction when the communicating parties select different cryptographic platform.The security of this protocol is reduced to the decomposition search-discrete logarithm problem on non-commutative groups,and the protocol’s resistance against algebraic and exhaustive attacks is elaborated in detail.Finally,using braid groups as an example,it is shown that the computational and storage complexities of this protocol are polynomial,so the protocol has practical application value.Additionally,the dual-platform design can conceal user information to a greater extent,which has the potential of applications in the post-quantum cryptography era.

Key words: Key agreement protocol, Non-abelian group, Semidirect product, DS-DLP, Quantum-resistant computing

CLC Number: 

  • TP309.7
[1]CAO Z F.New directions of modern cryptography[M].NewYork:CRC Press,2012.
[2]SIDELNIKOV V,CHEREPNEV M,YASCHENKO V.Systems of open distribution of keys on the basis of noncommutative semigroup[J].Russian Acad.Sci.Dokl.Math.,1993,48(2):566-567.
[3]ANSHEL I,ANSHEL M,GOLDFELD D.An algebraic method for public key cryptography[J].Math.Res.Lett,Springer Verlag,1999,6:287-291.
[4]KO K,SANG J L,CHEON J H,et al.New public-key crypto-system using braid groups[C]//Proceedings of the20th Annual International Cryptology Conference.Berlin:Springer,2000:166-183.
[5]SHPILRAIN V,USHAKOV A.A new key exchange protocol based on the decomposition problem[J].Contemp. Math. Amer. Math. Soc,2005,172(2):161-167.
[6]SHPILRAIN V,USHAKOV A.The conjugacy search problem in public key cryptography:Unnecessary and insufficient[J].Applicable Algebra in Engineering Communication & Computing,2006,17:285-289.
[7]SAKALAUSKAS E,TVARIJONAS P,RAULYNAITIS A.Key agreement protocol(kap) using conjugacy and discrete logarithm problems in group representation level[J].Informatica,2006,18(1):115-124.
[8]HABEEB M,KAHROBAEI D,KOUPPARIS C,et al.Publickey exchange using semidirect product of(semi)groups[C]//Proceedings of International Conference on Applied Cryptography and Network Security.Berlin:Springer,2013,2013:226-237.
[9]SKURATOVSKII R,WILLIAMS A.Some approach to key exchange protocol based on non-commutative groups[J].International Journal of Mathematical Models and Methods in Applied Sciences,2020,14(2):5-7.
[10]ALEKSEJUS M,ELIGIJUS S,KESTUTIS L.Key exchangeprotocol defined over a non-commuting group based on an NP-complete decisional problem[J].Symmetry,2020,12:1389.
[11]MYASNIKOV A D,USHAKOV A.Quantum algorithm for the discrete logarithm problem for matrices over finite group rings[J].Group Complexity Cryptology,2014,6(1):31-36.
[12]KAHROBAEI D,LAM H T,SHPILRAIN V.Pubilc key ex-change using extensions by endomorphisms and matrices over a Galois field[C]//Proceedings of the DIMACS Workshop on Multicore and Cryptography.USA:Hoboken NJ,2014:1-9.
[13]SHPILRAIN V,ZAPATA G.Combinatorial group theory andpublic key cryptography[J].Applicable Algebra in Engineering,Communication and Computing,2006,17:291-302.
[14]FENG K Q,LI S Z,ZHANG P.Introduction to modern algebra[M].Anhui:China University of Science and Technology Press,2020:6-21.
[15]MYASNIKOV A,SHPILRAIN V,USHAKOV A.Non-Com-mutative Cryptography and Complexity of Group-Theoretic Problems[M]//American Mathematical Society,2011:15-18.
[16]ELRIFAI E A,MORTON H R.Algorithms for positive braid[J].Q.J.Math,1994,45(4):479-497.
[17]FRANCO N,JUAN G M.Computation of centralizers in braid groups and garside groups[J].Revista Matematica Iberoamericana,2007,19(2):367-384.
[18]JUAN G M.On the structure of the centralizer of a braid[J].Annales Scientifiques De l′école Normale SupéRieure,2004,37(5):729-757.
[19]GASHKOV S B,SERGEEV I S.Complexity of computation in finite fields[J].Journal of Mathematical Sciences,2013,191(5):661-685.
[20]KREUZER M,MYASNIKOV A D,Ushakova.A linear algebra attack to group-ring-based key exchange protocols[C]//Proceedings of the International Conference on Applied Cryptography and Network Security.Switzerland:Springer,2014:37-43.
[21]GENNARO R,MICCIANCIo D.Cryptanalysis of a pseudorandom generator based on braid groups[C]//Proceedings of theInternational Conference on the Theory and Applications of Cryptographic Techniques(Eurocrypt 2002).Berlin,Heidelberg:Springer,2002:1-13.
[22]LONGRIG G J,USHAKOVA.A practical attack on a certainbraid group based shifted conjugacy authentication protocol[J].Group Complexity Cryptology,2009,1:275-286.
[23]FINE B,HABEEB M,KAHROBAEI D,et al.Aspects of nonabelian group based cryptography:a survey and open problems[J].Journal of Algebra Number Theory & Applications,2011,21(1):1-40.
[24]CAI D,WANG Y P,MIAO Y,et al.An orthogonal evolutionary algorithm with learning automata for multi-objective optimization[J].IEEE Transactions on Cybernetics,2016,46(12):3306-3319.
[25]XUE X S,WANG Y P.Optimizing ontology alignments through a memetic algorithm using both match measure and unanimous improvement ratio[J].Artificial Intelligence,2015,223:65-81.
[26]XUE X S,CHEN J F.Optimizing ontology alignment throughhybrid population-based incremental learning algorithm[J].Memetic Computing,2019,11(2):209-217.
[27]XUE X S,WANGY P.Using memetic algorithm for instance coreference resolution[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(2):580-591.
[1] QIN Yan-lin, WU Xiao-ping, HU Wei. Efficient Identity-based Authenticated Key Agreement Protocol with Multiple Private Key Generators [J]. Computer Science, 2020, 47(11): 68-72.
[2] WANG Yong-tao,FENG Wei-duan,LIU Xiao-nan,SONG Jing and GUO Zhen-zhou. Message Policy Attribute Based Key Agreement Protocol [J]. Computer Science, 2013, 40(9): 106-110.
[3] GUO Hua,ZHANG Fan,LI Zhou-jun,ZHOU Xiao-juan. Cryptanalysis and Improvement of a New Identity-based Key Exchange Protocol [J]. Computer Science, 2010, 37(10): 78-81.
[4] . [J]. Computer Science, 2009, 36(1): 60-64.
[5] TANG Xue-Ming, HONG Fan, CUI Cuo-Hua, WANG Xiao-Fei （College of Computer Science, Huazhong University of Science and Technology, Wuhan 430074）. [J]. Computer Science, 2006, 33(8): 121-125.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.