计算机科学

计算机科学 ›› 2025, Vol. 52 ›› Issue (6A): 240600036-6.doi: 10.11896/jsjkx.240600036

• 信息安全 • 上一篇    下一篇

基于半直积的双平台密钥协商协议

张静1,2, 王宇平3   

  1. 1 东莞职业技术学院现代工业创新实践中心 广东 东莞 523808
    2 中山大学计算机学院 广州 510006
    3 西安电子科技大学计算机科学与技术学院 西安 710075
  • 出版日期:2025-06-16 发布日期:2025-06-12
  • 通讯作者: 张静(2010120@dgpt.edu.cn)
  • 基金资助:
    国家自然科学基金面上项目(62272367);东莞市社会发展科技项目(20221800905832)

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)

91

摘要： 基于非交换代数的密码系统在抗量子计算攻击方面具有一定优势,组合群理论作为非交换代数的重要来源已在密码学中广泛应用。利用组合群上的一些数学难题,可构造出具有抗量子计算攻击的密码方案。半直积是组合群理论中的重要内容,且某些群上的分解搜索问题是困难问题。基于此,构建了一种非交换密钥协商协议。利用构建半直积的方法,以非交换群及其双射生成的循环群构造出一类适合建立密码方案的非交换群,通信双方构建不同的非交换群作为密码平台,通过一次交互实现密钥协商。该密钥协商协议的安全性可归约到非交换群上的“分解搜索—离散对数”问题,并对协议抵抗代数攻击与遍历攻击进行了详细分析。安全性分析结果表明该协议具有抵抗量子计算等多种攻击方式。最后,以辫群为例,得到了协议的计算和空间复杂度均为多项式级,因此该协议具有实际应用的价值。此外,由于双平台设计可更大程度地隐藏用户信息,因此,这种构建方法在后量子密码时代具有一定的应用前景。

关键词: 密钥协商协议, 非交换群, 半直积, 搜索-离散对数问题, 抗量子计算

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

中图分类号: 

  • 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.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发