基于多变量二次拟群的密码体制的若干问题研究

Multivariate cryptosystem is a hot research topic in the field of quantum-resistant cryptosystem. As a new type of multivariate cryptosystems, the cryptosystems based on multivariate quadratic quasigroups (MQQ) attract attentions of the researchers all over the world because of its high efficiency. However, the generation theory of MQQ is not complete. Moreover, the MQQ cryptosystems are confronted with several problems, such as, though the MQQ signature scheme (MQQ-SIG) is still safe, the MQQ public key cryptosystem (MQQ-PKC) is not safe, and the specialized signature schemes based on MQQ-SIG have not been designed corresponding to the different usage. In order to solve those problems, we are trying to do the following work in this project: (1) By representing the quadratic polynomial in the form of matrix production and using the mathematical tools such as tensor product and matrix equations, establish the condition for a given quasigroup to be MQQ and propose the algorithms to generate the corresponding polynomial functions over binary/large finite fields; (2) By compounding the Dobbertin transformation and the high order monomial and adjusting the compounding strategies, construct the permutation polynomial which can make the MQQ-PKC, whose Dobbertin transformation has been substituted by this permutation polynomial, be safe; (3) By using MQQ operation structure as the central map and discovering the relationship representation among the secret keys which are partially hidden, design the MQQ proxy signature scheme.

多变量密码体制是抗量子计算密码学领域中的热点研究课题之一。多变量二次拟群（MQQ）密码体制作为新型的多变量密码体制以其高效性引起了国内外同行的广泛关注。然而，MQQ的生成理论尚不完善，且当前MQQ密码体制存在仅能实现安全签名不能实现安全加密以及缺乏面向特殊应用需求的签名方案等问题。针对上述问题，本项目拟开展如下工作：(1)以二次多项式函数的矩阵形式为突破口，以张量积和矩阵方程为主要工具，在二元域及大数域上建立拟群为MQQ的判定条件及相应多项式函数的生成算法，进一步完善MQQ的生成理论；(2)尝试将Dobbertin变换与高次单项式复合，通过调整复合方式构造恰当的置换多项式，来替换MQQ公钥密码体制中的Dobbertin变换，进而实现安全加密；(3)以MQQ运算结构为中心映射，通过建立在隐藏信息的条件下密钥间的关联表达式，设计MQQ代理签名方案，从而拓展MQQ签名方案的研究空间和应用领域。

针对多变量二次拟群（MQQ）密码体制中MQQ的生成理论尚不完善，以及MQQ密码体制优化等问题，本项目从MQQ的生成和轮换矩阵等方面开展研究，取得如下成果：.(1) 为了抵抗 Gröbner 基攻击，Chen提出Strict Type MQQ的概念，并指出2^d（d>3）阶 Strict Type MQQ的存在性问题是一个公开问题。为此，我们建立了2^d阶拟群是Strict Type MQQ的充要条件，并在此充要条件基础上，将判断拟群能否生成/如何生成Strict Type MQQ的问题转换成一个矩阵方程是否有解/如何求解的问题，提出相应的生成算法，利用一个2^4阶Strict Type MQQ 实例部分回答了 Strict Type MQQ（d>3）的存在性问题。.（2）为了建立p^kd阶拟群是大有限域GF(p^k)上双线性/一般MQQ的判定/生成算法，首先建立p^kd阶拟群MQQ是大有限域GF(p^k)上双线性/一般MQQ的充要条件，在此基础上，提出p^kd阶拟群是大有限域GF(p^k)上双线性/一般MQQ的判定条件和生成算法，使获得大有限域上给定阶数的全部双线性/一般MQQ在理论上成为可能。.（3）针对k-斐波那契序列轮换矩阵，斜轮换矩阵以及斜左轮换矩阵，通过计算它们的特征值，进而利用k-斐波那契序列的性质，得到了上述矩阵的最大列和矩阵范数，最大行和矩阵范数，Frobenius范数，谱范数，以及传播界。.（4）提出了矩阵方程A_1X_1B_1+.... + A_lX_lB_l = C的对称反伪对称解的迭代求解算法，并在矩阵方程相容的情况下，对任意初始对称反伪对称矩阵组，计算得到最小范数对称反伪对称解组。此外，对给定对称反伪对称矩阵组，计算出最优逼近对称反伪对称解组。利用数值实验验证了迭代算法的有效性。.（5）通过将宽线性模型表示成分块Hankle 斜轮换矩阵，建立了四元数值信号处理中宽线性模型的实表示方法框架。.在本项目的资助下，项目组已发表论文9篇，其中SCI期刊论文4篇、EI论文3篇。