基于矩阵半群的公钥密码体制研究

With the development of quantum computer,the classical public key cryptosystem widely used will encounter potential threat. So it is currently a research focus of cryptography to explore the cryptosystem which can resist quantum attack. This project studies the public-key cryptosystems based on matrix semigroups. After studying the algebraic properties of two types of finie non-communicative semigroups which are the matrix semigroup over finite field and group ring, and analyzing the the automorphisms and semidirect product of the two types of semigroups, we construct the algebraic structures which are suited to cryptographic applications. We will analyze the complexity of the relative computational hard problem (the TEME problem of ergodic matrix over finite field and the DDH problem of matrix over group rings) and design the efficient algorithms of generating ergodic matrix over finite field, and studies the enumeration problem of the invertible elements of the matrix semigroup over group rings. Finally, we will design the CCA2 secure public-key encryption schemes, the key exchange protocols and the Identity authentication protocols. The cryptosystems based on matrix semigroup have the characteristic of anti quantum analysis and will provide the new theoretical and technical support for the cryptographic product during the age of the post-quantum cryptogrphy.

由于量子计算机的发展对目前广泛使用的公钥密码体制构成了潜在的威胁， 探索可以抵抗已知量子分析的公钥密码系统是目前密码学的一个研究热点。 本项目主要研究基于矩阵半群的公钥密码体制。通过研究两类有限非交换半群，即有限域矩阵半群和群环上的矩阵半群的代数性质，分析有限域矩阵半群和群环矩阵半群的自同构和半直积，构造适合密码学应用的半群代数结构。分析两类矩阵半群的相关计算困难性问题（有限域遍历矩阵的TEME 问题和群环矩阵 DDH 问题）的计算复杂度，设计高效的有限域遍历矩阵的快速生成算法；研究群环上矩阵半群中的可逆元计数问题，设计基于矩阵半群的标准模型下自适应性选择密文安全的公钥加密方案、密钥交换协议和身份认证协议。项目提出的基于矩阵半群的公钥密码体制具有抗量子分析的特性，将为后量子时代密码产品提供新的理论和技术支持。

探索基于新代数结构的抗量子分析的公钥密码系统是目前密码学的研究热点。项目主要通过半群代数理论的相关研究结果，探索基于有限域和有限域矩阵半群的新型公钥密码体制。项目研究了一些广义正则半群和富足半群的性质。并研究某些半群形成的半直积的性质和特征，探索适合密码学应用的半群代数结构。在讨论了数论和有限域的若干问题后，提出基于有限域矩阵的多变量公钥密码体制，讨论了遍历矩阵密码体制的安全性、攻破了一类基于有限域矩阵的加密方案、提出基于矩阵幂问题和对称遍历矩阵指数问题的零知识身份认证方案。项目设计了一些基于有限域的无证书代理签名方案和基于身份的多签名者通用指定多验证者签名方案，在随机预言机模型下证明了其安全性。这些结果为设计新型基于矩阵半群的抗量子分析密码体制提供理论和技术上的准备。