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

项目名称： 基于矩阵半群的公钥密码体制研究

项目编号： No.61462016

项目类型： 地区科学基金项目

立项/批准年度： 2015

项目学科： 自动化技术、计算机技术

项目作者： 黄华伟

作者单位： 贵州师范大学

项目金额： 40万元

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

中文关键词： 公钥密码；有限域矩阵；群环；半群；半直积

英文摘要： 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.

英文关键词： public-key cryptography;matrix over finite field;group ring;semigroup;semidirect product