The group factorization problem in finite groups of Lie type

• Published in: Information processing letters 2024-08, Vol.186, p.106484, Article 106484
• Main Authors: Hong, Haibo, Bai, Shi, Liu, Fenghao
• Format: Article
• Language: English
• Subjects: Cryptography; Discrete logarithmic problem; Finite groups of Lie type; Group factorization problem; Non-abelian factorization problem
• ISSN: 0020-0190; 1872-6119
• DOI: 10.1016/j.ipl.2024.106484

With the development of Lie theory, Lie groups have profound significance in many branches of mathematics and physics. In Lie theory, matrix exponential plays a crucial role between Lie groups and Lie algebras. Meanwhile, as finite analogues of Lie groups, finite groups of Lie type also have wide application scenarios in mathematics and physics owning to their unique mathematical structures. In this context, it is meaningful to explore the potential applications of finite groups of Lie type in cryptography. In this paper, we firstly built the relationship between matrix exponential and discrete logarithmic problem (DLP) in finite groups of Lie type. Afterwards, we proved that the complexity of solving non-abelian factorization (NAF) problem is polynomial with the rank n of the finite group of Lie type. Furthermore, combining with the Algebraic Span, we proposed an efficient algorithm for solving group factorization problem (GFP) in finite groups of Lie type. Therefore, it's still an open problem to devise secure cryptosystems based on Lie theory. •We built the relationship between matrix exponential and discrete logarithmic problem (DLP) in finite groups of Lie type.•We proved that the complexity of solving non-abelian factorization (NAF) problem in finite groups of Lie type is polynomial.•We proposed an efficient algorithm for solving group factorization problem (GFP) in finite groups of Lie type.