非交换密码学有关群分解问题的研究

With the rapid development of quantum computation, most cryptosystems based on number theory will be broken in the future. In order to resist known quantum algorithmic attacks, non-commutative cryptography come on the stage of modern cryptography. At the same time, a type of cryptosystems based on the intractable assumption in non-abelian group--group factorization problem (GFP) has gradually become a typical representative of non-commutative cryptography and achieved rapid development in recent thirty years. In this project, we will study GFP and related cryptosystems to deal with core problems in non-commutative cryptography by utilizing classical theories in many disciplines. Our motivations are as follows: Firstly, probe underlying platforms and private key generation mechanisms of MST cryptosystems, explore minimum length key to find more platforms for MST cryptosystems, and ultimately solve the MLS conjecture. Secondly, design new secure schemes based on GFP;Thirdly,explore various non-commutative algebra structures, analyze the capabilities of GFP for resisting known quantum attacks and the mechanism of non-commutativity for enhancing the hardness of the related problem.

随着量子计算的迅速发展，当前基于数论中难解问题的密码系统将面临安全威胁。为了应对已有的量子算法攻击，非交换密码学登上了历史舞台。同时，基于非交换群分解难题假设—群分解问题(Group Factorization Problem, GFP)的密码系统逐渐成为非交换密码学的典型代表并在最近三十年取得了迅速发展。本项目拟围绕GFP问题及与之相关的非交换密码系统展开研究，结合多学科的经典理论和工具，探索并解决非交换密码学中的核心问题。本项目研究目标如下：第一，研究MST 系列密码系统底层数学平台及其公私钥的产生机制，探索最短长度密钥的生成问题，为MST系列密码系统寻找更广阔的密钥平台，并最终解决MLS猜想；第二，设计新型的以GFP问题为难题假设基于密码原语的安全高效的密码方案；第三，考察多种非交换代数结构，分析实例化GFP问题对已知量子算法的抵抗能力，揭示非交换代数结构抵抗量子算法攻击的内在机理。

随着量子计算的迅速发展，当前基于数论中难解问题的密码系统将面临安全威胁。为了应对已有的量子算法攻击，非交换密码学登上了历史舞台。同时，基于非交换群分解难题假设—群分解问题(Group Factorization Problem, GFP)的密码系统逐渐成为非交换密码学的典型代表并在最近三十年取得了迅速发展。本项目围绕GFP问题及与之相关的非交换密码系统展开研究，结合多学科的经典理论和工具，探索并解决了非交换密码学中的核心问题。具体如下：第一，在探索MST密码系统最短长度密钥的生成问题方面，本项目组成员利用有限群论、展形理论和代数几何理论等相关背景知识，构造了一类有限单群的极小对数签名，最终证明了MLS猜想；第二，在基于GFP系列问题可证明安全公钥密码体制的设计与分析方面，本项目组成员设计了一个在随机预言模型下基于非交换嵌入（NAI）问题的CCA安全公钥加密方案。进一步设计了一个在随机预言模型下基于有限李型群非交换分解（NAF）问题的CCA安全公钥加密方案。最后利用随机覆盖和对数签名，设计了一个基于群分解问题的新型公钥加密方案，与现有的方案相比，我们的方案具有更高的效率。