非交换密码的两个核心问题研究

The development of quantum algorithms breaks some typical cryptographic assumptions based on commutative algebraic structures. With the purpose to resist known quantum algorithmic attacks, non-commutative algebraic structures come on the stage of modern cryptography. After more than a decade of research, the conjugacy search problem (CSP) and the group factorization problem (GFP) has become two key problems of non-commutative cryptography. This project will study the CSP problem, the GFP problem and therewith closely related braid cryptosystems and MST cryptosystems, and probe common problems of research on non-commutative cryptography. Our objectives are: Firstly, solve the problem of securing key generation and the problem of securing platform realization for braid cryptography and MST cryptography; Secondly, design novel and provably secure braid-based schemes and MST-like schemes; Thirdly, clarify the capabilities of the CSP problem and the GFP problem for resisting known quantum attacks and the mechanism of non-commutativity for enhancing the hardness of the related problems; Fourthly, probe common methods for selecting non-commutative crypgraphic platforms, designing schemes and conducting cryptanalysis.

量子计算的进展攻破了几类典型的基于交换代数结构的密码学难题假设。为了抵抗已知量子算法攻击，非交换代数结构登上了现代密码学的舞台。经过十多年的研究，共轭搜索问题（CSP）和群分解问题（GFP）已成为非交换密码研究的两个核心问题。本项目拟围绕CSP问题和GFP问题及与之密切相关的辫群密码系统和MST密码系统展开研究，并探索非交换密码研究的共性问题。本项目的目标是：第一，解决辫群密码和MST密码的安全密钥生成问题和安全平台实现问题；第二，设计具有可证明安全性的新型的基于辫群的密码方案和MST类型的密码方案；第三，阐明CSP问题和GFP问题抵抗已知量子算法攻击的能力以及非交换性在提升相关问题求解难度方面的机理；第四，探索非交换密码平台选择和方案设计与分析的共性方法。

本项目围绕非交换密码的两个核心问题共轭搜索问题（CSP）问题和群分解问题（GFP）及与之密切相关的辫群密码系统和MST密码系统展开研究，并探索非交换密码研究的共性问题，计划要点均已完成，部分成果有超出。一是，首次给出了非交换性在抵抗Shor量子算法攻击方面的证据，并阐明了非交换密码的两个核心问题——共轭搜索问题和群分解问题在抽象群模型下的难解性。同时，也指出了基于抽象群模型的难解性结论与密码系统实际构造所需要的安全实例化之间存在的差异和空白地带，为后续更深入的研究指明了方向；二是，证明了MST密码系统和计算群论领域共同关心的开放性问题——极小对数签名猜想，为新型MST密码系统的构造奠定的基础；三是，提出了典型加密系统Cramer-Shoup方案的非交换模拟新框架，并给出了基于两个核心问题——CSP问题和GFP问题的安全实例化，回答了国际密码旗舰会议TCC’05上的一个开放性问题；四是，对基于非交换代数结构的无噪声全同态加密方案的构造进行了系统的分析，亦提出了新的设计；五是，提出了首个基于非交换代数结构的具有密文等值测试特性的加密方案和首个属性基密文等值测试加密方案；六是，提出了星拓扑加密、多秘密共享、新型格基抽样算法、格基签名等密码构造。.本项目共发表/录用论文31篇，其中SCI检索26篇，EI检索4篇，会议1篇，新增申请发明专利4项，并出版学术专著1部；培养博士生/留学生7名。