多项式同构问题与多变量密码分类分析研究

多变量密码学是基于多项式方程组求解困难性而提出的一种新型公钥密码，被Diffie称为是基于二十世纪数学代数几何的密码学。本项目主要是利用有限几何的方法与理论，系统研究多变量公钥密码及其核心问题多项式同构的分类与计数问题，从整体上研究多变量公钥密码体制的规模与发展潜力。主要研究内容包括：已有多变量公钥密码方案的多余密钥问题、现有多变量公钥密码方案的等价及其计数问题，研究多项式方程组在同构意义下分类与计数问题，并在此基础上，进一步研究多变量公钥密码系统的可证明安全性及多项方程组的求解困难性在密码原子构件设计中的应用。本项目的研究，有望更多地揭示多变量公钥密码系统中的代数结构，挖掘多变量公钥密码系统的潜力，为更加安全的多变量公钥密码的设计和分析提供必要的指导。

作为后量子时代密码学的备选方案之一，多变量公钥密码系统的安全性与多项式同构问题的困难性密切相关，而该问题也一直是多变量密码学研究领域内的热点与难点问题。多项式同构相应的计数问题则决定了多变量公钥密码学中等价方案和等价密钥的数量，从而对多变量公钥密码学的潜力和整体安全性有着重要影响。本项目重点研究多项式同构计数问题及其在多变量密码分类分析中的应用。具体地，首次将有限几何的思想引入到多项式同构计数问题的研究中并给出了对多项式等价类数目的下界的估计；完整给出了单项式 $aX^{q^i + q^j}$ 所在线性等价类数目以及各等价类大小的计算公式，还给出了含有单项式的线性等价类中项数大于二的多项式数量的计算公式，从而证明了作为MI方案改进的HFE方案，其安全性并不一定高于MI方案，实际上有相当多的HFE方案与MI方案等价并给出了这类HFE方案数量的计算公式；给出了二项式 $aX^{2q^i} + bX^{2q^j}$ 所在线性等价类大小的计算公式并指出多项式 $\sum_{i=0}^{n-1} a_i X^{2q^i}$ 的作用类似于线性多项式，应避免将其作为方案的中心函数使用；在此基础上，利用多项式集合 $\{\sum_{i=0}^{n-1} a_i X^{2q^i}\}$的封闭性，根据分治策略设计了一个计算所有线性等价类数目的算法并对该算法的时间复杂性进行了分析。