基于迹函数的negabent函数构造

赵海霞 李文宇 韦永壮

①(桂林电子科技大学数学与计算科学学院，广西高校数据分析与计算重点实验室 桂林 541002)

②(广西应用数学中心 桂林 541002)

③(广西密码学与信息安全重点实验室 桂林 541002)

1 引言

在现代的对称密码体系中，布尔函数是不可替代的重要角色，其抵御攻击的能力决定着密码系统的安全性，故对安全性能良好的布尔函数的构造显得极其重要。非线性度是布尔函数的最重要的性质之一，具有高非线性度的布尔函数能够有效抵御最佳仿射攻击。具有最高非线性度的布尔函数被称为bent函数[1]，这类函数满足n阶扩散准则且其Walsh-Hadamard谱值的绝对值都是相等的，故bent函数是一类密码学性质较好的布尔函数。然而bent函数也有不足之处，例如bent函数不平衡，且其变元个数只能是偶数。Riera等人[2]提出了与Walsh-Hadamard变换相类似的Nega-Hadamard变换，并借鉴bent函数的谱值定义，将在任意点处Nega-Hadamard谱值的绝对值都为1的函数称为negabent函数。文献[3,4]指出negabent函数具有最优的自相关性，存在平衡的negabent函数，且其变元个数可为偶数也可为奇数。与bent函数一样，negabent函数在密码学、编码理论和组合设计中都有广泛的应用，故negabent函数的性质和构造成为布尔函数研究领域的一个重点问题。

目前，国内外的学者对negabent函数进行了若干的研究。Parker等人[5]讨论了既是bent又是negabent函数的构造和分类问题。Stănică等人[6]描述了nega-Hadamard变换的详细理论，研究了negabent函数级联后的结果，并刻画了M-M类中的bent-negabent函数所具备的特征。Stanica等人[7]继续证明了n元negabent函数代数次数的上界为，提出了一种利用完全映射多项式构造bentnegabent函数的方法。Su等人[8]给出了函数是negabent的充要条件，基于该充要条件证明了negabent函数至多有4种nega-谱值，并提供了一种构造偶变元bent-negabent的方法。Mandal等人[9]对MM类中的bent-negabent函数的存在性问题进行了研究。Sarkar[10]首次给出了通过迹函数的形式表示negabent函数，刻画了一类negabent 2次单项式函数，并给出了在M-M类中bent-negabent函数的充要条件。Zhou等人[11]利用迹函数给出了negabent函数的等价定义，分别构造了2次和3次的negabent单项式函数族。Wu等人[12]利用了2次置换的复合逆和3次置换的复合逆构造了一类新的negabent函数。Jiang等人[13]利用完全置换多项式给出了一类2次bent-negabent函数的充要条件，利用布尔函数和向量布尔函数组合的方法，计算了广义间接和的nega-Hadamard变换。Guo等人[14]分别通过间接与直接的方法对bent-negabent函数进行构造，并研究了多输出布尔函数的nega-Hadamard谱值。文献[15]利用基于迹函数定义的Kerdock码构造了2次bent-negabent函数族。迹函数是有限域上的一类线性函数，利用迹函数不仅可以更好地描述出negabent函数的性质，而且较其他方法而言，利用迹函数构造negabent函数也更加简便。

本文内容的安排如下：第2节介绍了布尔函数及有限域上的迹函数的基本知识；第3节给出了利用迹函数构造negabent函数的方法，并解决了所构造的negabent函数的计数问题；第4节总结。

2 预备知识

本文用F2表示只有两个元素0和1的有限域，F2上定义了加法和乘法两种2元运算，表示2元域上的n维向量空间。n元布尔函数是到F2上的映射[16]，用Bn表示所有的n元布尔函数构成的集合。

定义1[16]设f(x)∈Bn,x=(x1,x2,...,xn)∈，称多项式

为f(x)的代数正规型(Algebraic Normal Form,A N F)，这里的αe ∈F2,e=(e1,e2,...,en)∈F2n,f(x)的代数次数为deg(f)=max{wt(e)|αe ̸=0,e ∈F2n}，其中wt(e)为e的汉明重量，是e的分量中1的个数。代数次数至多为1的函数称为仿射函数。

设f(x)∈Bn，若|{x ∈F2n|f(x)=0}|=2n-1，则称该函数是一个平衡的布尔函数。两个布尔函数f(x)∈Bn,g(x)∈Bn之间的汉明距离为f ⊕g的汉明重量，记作d(f,g)，即d(f,g)=wt(f ⊕g)。

定义4[7]设f(x)∈Bn，若对任意的µ∈，均有|Nf(µ)|=1，则称函数f(x)为negabent函数。

定义5[17]设Q=Fqn,K=Fq为有限域，定义Fqn上的函数为

称此函数为Fqn上的迹函数。

迹函数具备下述性质：

定义6[17,18]设Fqn为有限域，多项式z(x)∈Fqn[x]，若由z(x)诱导的多项式函数是Fqn到Fqn上的一个双射(置换)，则称z(x)是有限域Fqn上的一个置换多项式。

3 两类negabent函数的构造

本节使用了有限域上的迹函数构造了两类negabent函数，并讨论了所构造的negabent函数的计数问题。

在第2类negabent函数的构造中，同样基于引理2中置换多项式的结论，利用迹函数构造negabent函数。与所构造的第1类negabent函数相比较，第2类negabent函数中可调的参数更多，因此由第2种构造方法可获得更多negabent函数。

命题2当λ ̸=1时，定理3中所构造的negabent函数数量的下界为2n-1[(2n-1-2)(2n-1-3)+2n-1-4]。

证明如定理3所示，f(x)中的u,v,m,d互不相同，确定有序数组(u,v,m,d)数量即可得到所构造出的negabent函数数量，将附表中的10元向量归纳可得：由定理3中的方法构造出的negabent函数的计数下界为2n-1[(2n-1-2)(2n-1-3)+2n-1-4]。

本文借鉴文献[12] 中利用有限域上的迹函数构造negabent函数的思想方法，通过增加可调参数获得了更多的negabent函数。文献[12]与本文所构造的negabent函数数量如表1所示。

表1 不同调参方案所构造函数数量

4 结论

Negabent函数作为bent函数的一种拓展，在密码学与编码理论中有着广泛应用，因此构造negabent函数具有重要实际意义。本文将迹函数与置换多项式相结合，提出了两种构造negabent函数的方法，解决了所构造出来的negabent函数的计数问题。研究结果表明，利用本方法可以获得大量的negabent函数。