一些密码函数的构造与分析

Rotation symmetric Boolean functions (Abbr. RSBFs )and low differentially uniform functions with highly nonlinearity on finite fields are widely used in cryptography because they can be used to construct cryptographic functions. In recent years, this kind of functions caused researchers’ attentions. In 2002 Cusick and Stănică proposed a conjecture that the weight of a kind of 3-degree RSBF is same as its nonlinearity, and proposed a conjecture about the nonexistence of nonlinear balanced elementary symmetric Boolean function except for some cases in 2006. Firstly,Starting from proving the two conjectures, by using some new methods, we will study the cryptographic properties and constructions of rotation symmetric functions, and study relevant exponential sum of trace functions, along with proving the above two conjectures. By using techniques of recursion and decomposition, we will compute the Walsh spectrum values of RSBFs of degree 2, and compute the first-order and second-order nonlinearity of RSBFs of degree 3, which may prove the general cases of the Cusick’ conjecture in 2002; By studying the short algebraic normal form, we will obtain some non-existence results about homogeneous rotation symmetric bent functions, and construct some rotation symmetric bent functions with degree>2. Secondly, we will use polynomial difference factorization method to calculate the exponential sum of some trace functions with degree 2 on finite fields; Construct quadratic permutation funcionts of cryptographic interest; Construct normal basis with good trace orthogonal properties and low complexity on finite fields. Finally, we will construct perfect nonlinear functions, almost perfect nonlinear functions and low differentially uniform functions with high nonlinearity.

旋转对称布尔函数和低差分一致性函数可用于构造密码学函数，在密码学等领域中具有重要的应用价值。本课题将采用一些新方法研究这两类函数的性质、构造和相关密码学问题。首先，利用递归以及函数分解办法，研究二次旋转对称布尔函数的谱值，和三次旋转对称布尔函数的一阶和二阶非线性度，证明Cusick2002年猜想（一些旋转对称函数的重量和非线性度相同）的更一般形式；利用Bent函数的系数规律，证明2002年Stanica猜想（不存在次数大于2的齐次旋转对称Bent函数）的部分情况，并构造次数大于2的旋转对称Bent函数。其次，利用我们的多项式差分分解的这种新方法计算二次迹函数的指数和；构造密码学上的二次置换函数；解决有限域上正规基的迹正交关系；构造低计算复杂度的正规基，以及研究几乎完美序列等相关组合学结构的存在性。最后，构造具有高非线性度的新完全非线性函数、几乎完全非线性函数和低差分4一致性函数。

我们围绕原申报书的研究计划和研究目标展开了研究，具体结果如下：.1）构造了新的二次置换函数，证明了几个关于二次置换函数的公开猜想；.2）利用差分分解的方法，刻画出有限域上任意向量是否对应一组正规基的迹正交关系，以及如何计算出这组正规基；可以计算系数为1的几乎全部二次迹函数的指数和；.3）利用提升和傅里叶反演的方法，给出了任意有限域上的正交循环矩阵的构造和计数；.4）给出任意二次旋转对称布尔函数的谱值。利用特殊的正规基，把向量空间上的多变元二次布尔函数转化为有限域上的二次迹函数，从而可以计算出任意的二次旋转对称布尔函数的谱值；.5）证明了2002年法国学者Stanica提出的不存在次数大于2的齐次旋转对称Bent函数猜想的更多情形，得到的结果优于目前的非存在性结果；.6）构造了新的完全非线性函数、几乎完全非线性函数、和低差分一致性函数；.7）计算了一些三次旋转对称布尔函数的非线性度；.8）构造了有限域上的迹形式的Bent函数，从而也构造了旋转对称形式的布尔Bent函数。也构造了其他形式的Bent函数；.9）构造了一些参数优的码本，构造了新的跳频序列；.10）构造一些循环码及其他的二重线性码，给出了码重分布和最小距离。