类差分平衡函数的性质及其应用

摘要

定义了布尔函数的类差分和类差分平衡函数，研究了类差分平衡函数的密码学性质以及构造方法。作为类差分平衡函数的应用，给出了〓上逻辑函数是完全非线性函数的充要条件，并在首先分析得到所有四元类差分平衡函数的基础上，编程搜索出〓上所有的完全非线性函数。

正文

《1 引言》

1 引言

由于具有抗差分攻击和最优仿射逼近的能力, 以及具有最高的非线性度和高度的稳定性^[1], Bent函数^[2] 在密码设计中发挥了重要作用, 早在1982 年, Olsen 和Scholtz就将用Bent函数构造的具有良好的自相关和互相关性质的二元序列用于码分多址通信系统中^[3], 又如澳大利亚加密标准HAVAL算法^[4] 的设计中所用到的5个布尔函数无一例外都是由Bent函数演化而来。1990年, K. Nyberg 把Bent函数的概念从二元域上的n维向量空间推广为素域F_p上的n维向量空间上的完全非线性函数, 并研究了素域上完全非线性函数的密码性质及构造方法^[5]。由于剩余类环中含有零因子, 导致剩余类环上一大类逻辑函数 (特别是可用常义下的多项式表示的函数) 不是完全非线性函数^[6], 这就给剩余类环上的完全非线性函数的研究带来了很大的困难, 故迄今为止, 关于剩余类环上完全非线性函数的存在性和构造研究的文献目前仍不多见。

众所周知, 构造剩余类环上完全非线性函数是比较困难的, 笔者在用2-基分解的思想研究剩余类环上完全非线性函数新构造方法时, 发现了一类新的布尔函数类, 对这类函数做一种类似于“差分”的运算后可以得到平衡函数, 于是定义了布尔函数的“类差分”和布尔函数中的类差分平衡函数, 研究了类差分平衡函数的性质, 给出了类差分平衡函数的一些构造方法。作为类差分平衡函数的重要应用, 给出了Z $_{4}^{2}$ $_{4}^{2}$ 上逻辑函数是完全非线性函数的充要条件, 并在首先分析得到所有四元类差分平衡函数的基础上编程搜索出Z $_{4}^{n}$ $_{4}^{n}$ 上所有的完全非线性函数。第6章中研究问题的思想和方法同样可以用于Zⁿ₄上弹性函数的研究。

将会看到, 由于Z $_{4}^{n}$ $_{4}^{n}$ 上完全非线性函数的2-基分解式中的第一个分量都是类差分平衡函数, 所以, 研究类差分平衡函数对于Z $_{4}^{n}$ $_{4}^{n}$ 上完全非线性函数的研究具有重要的指导意义。

《2 基本概念》

2 基本概念

以GF (2) 表示二元域, 记Ω=GFⁿ (2) , F={A:A⊂Ω}, 可测空间 (Ω, F) 上的概率测度P (·) 满足

$\begin{array}{l} Ρ {(x_{1}, \dots, x_{n})} = 2^{- n} ‚ \\ (x_{1}, \dots, x_{n}) \in Ω = G F^{n} (2) 。 \end{array}$ $\begin{array}{l} Ρ {(x_{1}, \dots, x_{n})} = 2^{- n} ‚ \\ (x_{1}, \dots, x_{n}) \in Ω = G F^{n} (2) 。 \end{array}$

又定义

《图1》

《图2》

易知X₁, X₂, …, X_n是概率空间 (Ω, F, P) 上的n个相互独立的布尔随机变量, 且满足

$Ρ {X_{k} = 0} = Ρ {X_{k} = 0} = 1 / 2 ‚ 1 \leq k \leq n 。$ $Ρ {X_{k} = 0} = Ρ {X_{k} = 0} = 1 / 2 ‚ 1 \leq k \leq n 。$

从GFⁿ (2) 到GF (2) 的一个映射称为布尔函数, 布尔函数f可以用关于x₁, …, x_n的多项式唯一表示, 该多项式称为f的代数标准形, 简记为ANF^[7]。f的ANF中各单项式所含变元个数的最大值称为f的代数次数。如果GFⁿ (2) 中使得f (x) =1的向量的个数为2^n-1, 则称f是平衡的。 GFⁿ (2) 中2个向量的点积记为w·x, 布尔函数f的Walsh循环谱S_(f) (w) ^[2] 是定义在GFⁿ (2) 上的一个实值函数:

$\begin{array}{l} S_{(f)} (w) = 2^{- n} \sum_{x \in G F^{n} (2)} (- 1)^{f (x) + w \cdot x} ‚ \\ w \in G F^{n} (2) 。 (1) \end{array}$ $\begin{array}{l} S_{(f)} (w) = 2^{- n} \sum_{x \in G F^{n} (2)} (- 1)^{f (x) + w \cdot x} ‚ \\ w \in G F^{n} (2) 。 (1) \end{array}$

它反映了f与各个仿射函数的距离, 分组密码中的线性攻击和流密码中的相关攻击都等价于寻找一个与给定布尔函数距离最近的仿射函数或线性函数。自相关函数r_f (s) ^[2] 也是定义在GFⁿ (2) 上的一个实值函数:

$r_{f} (s) = 2^{- n} \sum_{x \in G F^{n} (2)} (- 1)^{f (x + s) + f (x)} ‚ s \in G F^{n} (2) ‚$ $r_{f} (s) = 2^{- n} \sum_{x \in G F^{n} (2)} (- 1)^{f (x + s) + f (x)} ‚ s \in G F^{n} (2) ‚$

它反映了当输入改变量为s时的输出与原输出的符合优势, 显然, r_f (s) =0等价于差分函数f (x+s) + f (x) 平衡。布尔函数的Walsh循环谱与自相关函数之间有如下联系^[8]:

$\begin{array}{l} [S_{(f)} (w)]^{2} = 2^{- n} \sum_{s \in G F^{n} (2)} r_{f} (s) (- 1)^{w - s} ‚ \\ w \in G F^{n} (2) 。 (2) \end{array}$ $\begin{array}{l} [S_{(f)} (w)]^{2} = 2^{- n} \sum_{s \in G F^{n} (2)} r_{f} (s) (- 1)^{w - s} ‚ \\ w \in G F^{n} (2) 。 (2) \end{array}$

如果对任意的w∈GFⁿ (2) 都有[S_(f) (w) ]²=2^-n (等价于对任意的0≠s∈GFⁿ (2) , 都有r_f (s) =0) , 则称f是Bent函数。

《3 类差分平衡函数及其性质》

3 类差分平衡函数及其性质

《3.1类差分函数与类自相关函数》

3.1类差分函数与类自相关函数

在这节中n为正偶数。

定义1 设f (x) , x= (x₁, …, x_n) ∈GFⁿ (2) 是布尔函数, 对s= (s₁, …, s_n) ∈GFⁿ (2) , 称

$\begin{array}{l} f (x_{1} + s_{1}, s_{1} x_{1} + x_{2} + s_{2}, \dots, x_{n - 1} + s_{n - 1}, \\ s_{n - 1} x_{n - 1} + x_{n} + s_{n}) + f (x_{1}, x_{2}, \dots, x_{n - 1}, x_{n}) \end{array}$ $\begin{array}{l} f (x_{1} + s_{1}, s_{1} x_{1} + x_{2} + s_{2}, \dots, x_{n - 1} + s_{n - 1}, \\ s_{n - 1} x_{n - 1} + x_{n} + s_{n}) + f (x_{1}, x_{2}, \dots, x_{n - 1}, x_{n}) \end{array}$

为f (x) , x= (x₁, …, x_n) ∈GFⁿ (2) 在s点的类差分函数。

为了书写方便, 记

《图3》

注意:此处的x⊕s不同于通常意义下2个n维布尔向量之间的逐个比特模2加。

定义2 设f (x) , x= (x₁, …, x_n) ∈GFⁿ (2) 是布尔函数, x⊕s的定义如式 (3) , 称

《图4》

为f (x) 关于变量组 (x₁, x₂) , …, (x_n-1, x_n) 的类自相关函数, 简称为f (x) 的类自相关函数。

注1 δ_f (s) =0的充要条件是类差分函数f (x⊕s) +f (x) 平衡。

注2 由于当s的下标为奇数的分量都是0, 即s形如 (0, s₂, …, 0, s_n) 时,

《图5》

故此时有δ_f (s) =r_f (s) , 其中r_f (s) 是布尔函数f (x) 自相关函数在s= (0, s₂, …, 0, s_n) 处的函数值, 特别地有δ_f (0) =r_f (0) =0。

另外δ_f (s) , s∈GFⁿ (2) 还有如下特点:

定理1 设f (x) , x= (x₁, …, x_n) ∈GFⁿ (2) 是布尔函数, e_k∈GFⁿ (2) 是n维标准单位向量——只有第k分量是1的布尔向量, 1≤k≤n, 则

$δ_{f} (e_{i}) = δ_{f} (e_{i} + e_{i + 1}) ‚ i = 1, 3, \dots, n 。$ $δ_{f} (e_{i}) = δ_{f} (e_{i} + e_{i + 1}) ‚ i = 1, 3, \dots, n 。$

证明只证δ_f (e₁) =δ_f (e₁+ e₂) , 其他类似可证。由式 (4) 容易得到

《图6》

注意对任意的x= (x₁, …, x_n) ∈GFⁿ (2) , 可有

《图7》

其中h_i (x₃, …, x_n) , 0≤i≤3是关于 (x₃, …, x_n) 的n-2元布尔函数, 因而有

《图8》

于是

《图9》

《图10》

类似可证

《图11》

所以,

《图12》

再由式 (5) 即知δ_f (e₁) =δ_f (e₁+e₂) 。

自相关函数和Walsh循环谱之间有关系式 (2) , 那么类自相关函数和Walsh循环谱之间是否也有类似的关系?事实上只有在形如w= (w₁, 0, …, w_n-1, 0) 的点处类似的关系式才成立。

定理2 设f (x) , x∈GFⁿ (2) 是布尔函数, 其类自相关函数和Walsh谱分别为δ_f (s) 和S_(f) (w) , 则在形如w= (w₁, 0, …, w_n-1, 0) 的点处下列等式成立:

《图13》

证明首先注意有

《图14》

所以

《图15》

因而, 对任意的w∈GFⁿ (2) , 根据类自相关函数的定义及式 (6) 可得:

《图16》

将定理题设条件w₂=…=w_2k=…= w_n=0代入式 (7) , 再用式 (1) 即得

《图17》

《3.2类差分平衡函数》

3.2类差分平衡函数

定义3 设f (x) , x∈GFⁿ (2) 是布尔函数, 若对任意的0≠s∈GFⁿ (2) , 类差分函数f (x⊕s) + f (x) , x∈GFⁿ (2) 都平衡, 等价的就是δ_f (s) =0, 则称f (x) 是关于变量组 (x₁, x₂) , … , (x_n-1, x_n) 的类差分平衡函数。

根据类差分平衡函数的定义, 可以验证x₁x₂, x₁x₄+x₂x₃, x₁x₆+x₂x₄+x₃x₅+x₁x₂x₃x₅分别是二元、四元、六元类差分平衡函数, 所以类差分平衡函数的存在性是勿庸置疑的。

由于布尔函数的许多密码学性质都可以通过其Walsh谱予以刻画, 下面来考察类差分平衡函数的谱特征。由定理2可以得到类差分平衡函数的Walsh循环谱的取值有如下特点:

定理3 若f (x) , x∈GFⁿ (2) 是类差分平衡函数, 则一定有

《图18》

证明因为f (x) 是类差分平衡函数, 故对任一0≠s∈GFⁿ (2) , 都有δ_f (s) =0, 且δ_f (0) =1, 由定理2即知, 当w= (w₁, 0, …, w_n-1, 0) 时有

《图19》

定理4 若f (x) , x∈GFⁿ (2) 是类差分平衡函数, 则其常义下的自相关函数r_f (s) 满足

《图20》

证明由前述关于类自相关函数定义的注2即得。

众所周知, n元Bent函数的代数次数至多可达到n/2, 即在n元Bent函数的多项式表达式中代数次数大于n/2的单项式的系数都是0, 然而对于类差分平衡函数可以得到下面的结论:

定理5 若f (x) , x= (x₁, …, x_n) ∈GFⁿ (2) 是类差分平衡函数, 则当n≥4时, f (x) 的ANF中不含有以x₂x₄…x_n作为因式的单项式。

证明设i₁, i₂, …, i_k是奇数, 且1≤i₁≤i₂≤ … ≤i_k≤n-1, 记

《图21》

则由文献[1]中“定理7.2.5”及定理3知, f (x) 的多项式表示式中单项式x₂x₄…x_nx_i₁…x_{i_k}的系数

《图22》

《图23》

而当k=1时, $a_{24 \dots n i_{1}} = [2^{n / 2} - \sum_{w \in \bar{S}_{24 \dots n i_{1} i_{2} \dots i_{r}}} (\pm 1)]_{m o d 2}$ $a_{24 \dots n i_{1}} = [2^{n / 2} - \sum_{w \in \bar{S}_{24 \dots n i_{1} i_{2} \dots i_{r}}} (\pm 1)]_{m o d 2}$ , 由n≥4得2^n/2=0_mod2且 $| \bar{S}_{24 \dots n i_{1}} | = 2^{n / 2 - 1}$ $| \bar{S}_{24 \dots n i_{1}} | = 2^{n / 2 - 1}$ 是偶数, 故和式 $\sum_{w \in \bar{S}_{24 \dots n i_{1}}} (\pm 1)$ $\sum_{w \in \bar{S}_{24 \dots n i_{1}}} (\pm 1)$ 中+1和-1的个数有相同的奇偶性, 从而 $\sum_{w \in \bar{S}_{24 \dots n i_{1}}} (\pm 1) = 0_{m o d 2}$ $\sum_{w \in \bar{S}_{24 \dots n i_{1}}} (\pm 1) = 0_{m o d 2}$ , 所以a_{24…ni₁…i_k}=0, 故定理结论成立。

例如, 四元类差分平衡函数的多项式表达式中不含有x₁x₂x₄, x₂x₃x₄, x₁x₂x₃x₄六元类差分平衡函数的多项式表达式中不含有x₁x₂x₄x₆, x₂x₃x₄x₆, x₂x₄x₅x₆, x₁x₂x₃x₄x₆, x₁x₂x₄x₅x₆x₂x₃x₄x₅x₆, x₁x₂x₃x₄x₅x₆等, 所以定理5为确定类差分平衡函数的多项式表达式提供了一定的理论依据。

《4 类差分平衡函数与Bent函数的关系》

4 类差分平衡函数与Bent函数的关系

由于布尔函数的类差分和差分的运算法则不同, 所以类差分平衡函数和Bent函数这2个概念是有区别的, 例如类差分平衡函数x₁x₆+x₂x₄+x₃x₅+x₁x₂x₃x₅就不是Bent函数, 而四元Bent函数x₁x₂+x₃x₄+x₂x₄等也不是类差分平衡函数。但类差分平衡函数与Bent函数也有一些相同的地方, 例如在形如 (w₁, 0, …, w_n-1, 0) 点的循环谱的二次方都是2^-n, 在形如 (0, s₂, …, 0, s_n) 的点处的差分都平衡等。因此类差分平衡函数与Bent函数是交集非空的2个不同的函数类。关于二者的联系, 有下面的定理:

定理6 代数次数为2的类差分平衡函数都是Bent函数。

证明由于代数次数为2的布尔函数都是部分Bent函数^[8], 因部分Bent函数的循环谱的二次方最多取2个不同的值0和2^-n+r, 1≤r≤n, 再由定理3知道, 代数次数为2的类差分平衡函数的循环谱的二次方有一部分是2^-n。再由能量守恒定理^[7] 知此类函数在所有点处循环谱的二次方都必须是2^-n。所以代数次数为2的类差分平衡函数都是Bent函数。

下面的定理7可以用来判定Bent函数何时是类差分平衡函数。

定理7 若f (x) , x∈GFⁿ (2) 是Bent函数, 且其循环谱满足:对任意的

《图24》

都成立

《图25》

则f (x) , x∈GFⁿ (2) 是类差分平衡函数。

证明这是因为一方面由f (x) 是Bent函数知

《图26》

另一方面根据式 (7) 和式 (8) 又有

《图27》

因而有

$δ_{f} (s) = {\begin{cases} 1, s = 0, \\ 0, s \neq 0, \end{cases}$ $δ_{f} (s) = {\begin{cases} 1, s = 0, \\ 0, s \neq 0, \end{cases}$

即f (x) 是类差分平衡函数。

满足定理7中条件的Bent函数是存在的, 例如f (x, y) =xy, x, y∈GF (2) 便是一类。

《5 类差分平衡函数的构造》

5 类差分平衡函数的构造

定理8 形如

$\begin{array}{l} f (x) = x_{1} x_{2} + x_{3} x_{4} + \dots + x_{n - 1} x_{n} + g (x_{1}, \\ x_{3}, \dots, x_{n - 1}) ‚ (x_{1}, \dots, x_{n}) \in G F^{n} (2) (9) \end{array}$ $\begin{array}{l} f (x) = x_{1} x_{2} + x_{3} x_{4} + \dots + x_{n - 1} x_{n} + g (x_{1}, \\ x_{3}, \dots, x_{n - 1}) ‚ (x_{1}, \dots, x_{n}) \in G F^{n} (2) (9) \end{array}$

的布尔函数都是关于变量组 (x₁, x₂) , … , (x_n-1, x_n) 的类差分平衡函数, 其中

$g (x_{1}, x_{3}, \dots, x_{n - 1}) ‚ (x_{1}, x_{3}, \dots, x_{n - 1}) \in G F^{n / 2} (2)$ $g (x_{1}, x_{3}, \dots, x_{n - 1}) ‚ (x_{1}, x_{3}, \dots, x_{n - 1}) \in G F^{n / 2} (2)$

是关于变元 (x₁, x₃, …, x_n-1) 的任一布尔函数。

证明因为形如式 (9) 的布尔函数都是Bent函数^[2], 且对任意的s∈GF^n/2 (2) , 都有

$f (x \oplus s) + f (x) = f (x + s) + f (x) ‚ x \in G F^{n} (2)$ $f (x \oplus s) + f (x) = f (x + s) + f (x) ‚ x \in G F^{n} (2)$

所以对于任意的0≠s∈GFⁿ (2) , 都有δ_f (s) =r_f (s) =0。

引理1 设f_i (x^{(i) )}, x⁽ⁱ⁾ , ∈GF^n_i (2) , 1≤i≤k都是布尔函数, x⁽ⁱ⁾∈GF^n_i (2) , x= (x⁽¹⁾ , x⁽²⁾ , …, x^(k)) , f (x) = f₁ (x⁽¹⁾ + f₂ (x⁽²⁾) + … + f_k (x^(k)) , s⁽ⁱ⁾∈GF^n_i (2) , s= (s⁽¹⁾ , s⁽²⁾ , …, s^(k) ) , δ_f (s) 是f (x) 的类自相关函数, 则有

$δ_{f} (s) = \prod_{i = 1}^{k} δ_{f_{i}} (s^{(i)}) 。$ $δ_{f} (s) = \prod_{i = 1}^{k} δ_{f_{i}} (s^{(i)}) 。$

证明为记号简单, 仅证k=2时结论成立:记s= (s⁽¹⁾ , s⁽²⁾) ∈GF^n₁+n₂ (2) , 其中s⁽¹⁾∈GF^n₁ (2) , s⁽²⁾∈GF^n₂ (2) , 则由类自相关函数的定义知

《图28》

由引理1不难得到下面的类差分平衡函数的构造方法:

定理9 设f_i (x⁽ⁱ⁾) , x⁽ⁱ⁾∈∈GF^n_i (2) , 1≤i≤k都是布尔函数, 则

$\begin{array}{l} f_{1} (x^{(1))} + f_{2} (x^{(2)}) + \dots + f_{k} (x^{(k)}) ‚ \\ x^{(i)} \in G F^{n_{i}} (2) ‚ 1 \leq i \leq k \end{array}$ $\begin{array}{l} f_{1} (x^{(1))} + f_{2} (x^{(2)}) + \dots + f_{k} (x^{(k)}) ‚ \\ x^{(i)} \in G F^{n_{i}} (2) ‚ 1 \leq i \leq k \end{array}$

是类差分平衡函数的充分必要条件是f_i (x⁽ⁱ⁾) , x⁽ⁱ⁾∈GF^n_i (2) , 1≤i≤k都是类差分平衡函数。

证明充分性显然。

必要性设f₁ (x⁽¹⁾) +f₂ (x⁽²⁾) +…+f_k (x^(k)) , x⁽ⁱ⁾∈GF^n_i (2) 是类差分平衡函数, 由引理1, 对任意的0≠s= (s⁽¹⁾ , s⁽²⁾, …, s^(k) ) , 都有

$\begin{array}{l} δ_{f_{1} + f_{2} + \dots + f_{k}} (s^{(1)}, s^{(2)}, \dots, s^{(k)}) = \\ δ_{f_{1}} (s^{(1)}) δ_{f_{2}} (s^{(2)}) \dots δ_{f_{k}} (s^{(k)}) = 0 ‚ \end{array}$ $\begin{array}{l} δ_{f_{1} + f_{2} + \dots + f_{k}} (s^{(1)}, s^{(2)}, \dots, s^{(k)}) = \\ δ_{f_{1}} (s^{(1)}) δ_{f_{2}} (s^{(2)}) \dots δ_{f_{k}} (s^{(k)}) = 0 ‚ \end{array}$

特别取s⁽¹⁾≠0, 而s⁽ⁱ⁾=0, 2≤i≤k, 即知

$\begin{array}{l} δ_{f_{1} + f_{2} + \dots + f_{k}} (s^{(1)}, 0, \dots, 0) = \\ δ_{f_{1}} (s^{(1)}) δ_{f_{2}} (0) \dots δ f_{k} (0) = 0 ‚ \end{array}$ $\begin{array}{l} δ_{f_{1} + f_{2} + \dots + f_{k}} (s^{(1)}, 0, \dots, 0) = \\ δ_{f_{1}} (s^{(1)}) δ_{f_{2}} (0) \dots δ f_{k} (0) = 0 ‚ \end{array}$

因δ_{f_i} (0) =1, 2≤i≤k, 故对任意的s⁽¹⁾≠0, δ_f₁ (s⁽¹⁾) =0, 可见f₁ (x⁽¹⁾) 是类差分平衡函数, 同理可知, f_i (x⁽ⁱ⁾) , 1≤i≤k都是类差分平衡函数。

在构造密码函数时, 总希望所构造的函数具有较高的代数次数和不要过于简单的代数结构形式, 而由定理9所构造的布尔函数的代数次数不会超过2个函数的代数次数的最大值, 结构形式也过于简单, 为了构造具有较高代数次数, 代数形式稍微复杂的密码函数, 有必要去寻求其他的构造方法, 定理10将给出一种新的构造方法, 这里处理问题的思想方法不同于Rothous 在文献[2]中所给出的Bent的经典构造法。

定理10 设f_i (x⁽ⁱ⁾) , x⁽ⁱ⁾∈GF^n_i (2) , i=1, 2都是类差分平衡函数, 若存在h_i (x⁽ⁱ⁾) , i =1, 2 使得f_i (x⁽ⁱ⁾) +h_i (x⁽ⁱ⁾) , i=1, 2也都是类差分平衡函数, 则下述函数是类差分平衡函数:

$\begin{array}{l} f_{1} (x^{(1)}) + f_{2} (x^{(2)}) + h_{1} (x^{(1)}) + h_{2} (x^{(2)}) ‚ \\ x^{(i)} \in G F^{n_{i}} (2) ‚ i = 1, 2 。 \end{array}$ $\begin{array}{l} f_{1} (x^{(1)}) + f_{2} (x^{(2)}) + h_{1} (x^{(1)}) + h_{2} (x^{(2)}) ‚ \\ x^{(i)} \in G F^{n_{i}} (2) ‚ i = 1, 2 。 \end{array}$

用与文献[6]中定理1.11完全相同的方法可证定理10 (证明略) 。下面仅举一例说明其应用。

例设f₁ (x⁽¹⁾) =x₁x₂+x₁x₅+x₁x₆+x₂x₃+x₂x₆+x₄x₆+x₂x₃x₄+x₁x₃x₄x₅, f₂ (x⁽²⁾) =x₇, h₁ (x⁽¹⁾) = x₁x₆+x₂x₄+x₃x₅+x₁x₂x₃x₅, h₂ (x⁽²⁾) =x₇x₈, 则上述函数满足定理10的条件, 故f₁ (x⁽¹⁾) + f₂ (x⁽²⁾) + h₁ (x⁽¹⁾) h₂ (x⁽²⁾) 是代数次数为5的类差分平衡函数。

《6 类差分平衡函数的应用》

6 类差分平衡函数的应用

下面给出类差分平衡函数在Z₄上完全非线性函数构造中的应用。

定义4^[5] 称n元m值逻辑函数f (y) , y∈Zⁿ_m为完全非线性函数, 如果对任意的v∈Z $_{m}^{n}$ $_{m}^{n}$ 0}, 差分函数f (y+v) -f (y) , y∈Z $_{m}^{n}$ $_{m}^{n}$ 在Z_m上取值都是均匀的, 即

$\begin{array}{l} | {y ∶ f (y + v) - f (y) = i ‚ \\ y \in Ζ_{m}^{n}} | = m^{n - 1} ‚ i \in Ζ_{m} 。 \end{array}$ $\begin{array}{l} | {y ∶ f (y + v) - f (y) = i ‚ \\ y \in Ζ_{m}^{n}} | = m^{n - 1} ‚ i \in Ζ_{m} 。 \end{array}$

因在Z₄上完全非线性函数的概念中涉及到变元之间以及逻辑函数之间的模4加法、减法运算, 故先给出2-基分解意义下各个变量y_i∈Z₄, 1≤i≤n及函数f的2-基分解表示:

当y₁∈Z₄时, y₁可以分解表示为

$\begin{array}{l} y_{1} = x_{1} + 2 x_{2} ‚ (x_{1}, x_{2}) \in G F^{2} (2) = \\ {(0, 0), (1, 0), (0, 1), (1, 1)} ‚ \end{array}$ $\begin{array}{l} y_{1} = x_{1} + 2 x_{2} ‚ (x_{1}, x_{2}) \in G F^{2} (2) = \\ {(0, 0), (1, 0), (0, 1), (1, 1)} ‚ \end{array}$

其意义是

$\begin{array}{l} y_{1} = 0 \Leftrightarrow (x_{1}, x_{2}) = (0, 0), \\ y_{1} = 1 \Leftrightarrow (x_{1}, x_{2}) = (1, 0), \\ y_{1} = 2 \Leftrightarrow (x_{1}, x_{2}) = (0, 1), \\ y_{1} = 3 \Leftrightarrow (x_{1}, x_{2}) = (1, 1), \end{array}$ $\begin{array}{l} y_{1} = 0 \Leftrightarrow (x_{1}, x_{2}) = (0, 0), \\ y_{1} = 1 \Leftrightarrow (x_{1}, x_{2}) = (1, 0), \\ y_{1} = 2 \Leftrightarrow (x_{1}, x_{2}) = (0, 1), \\ y_{1} = 3 \Leftrightarrow (x_{1}, x_{2}) = (1, 1), \end{array}$

称y₁= (x₁, x₂) 为y的2-基分解。由此不难知道, 当v₁∈Z₄的2-基分解为v₁= (s₁, s₂) 时, y₁和v₁在Z₄中的“和”y₁+v₁的2-基分解即为

$y_{1} + v_{1} = (x_{1} s_{1}, s_{1} x_{1} + x_{2} + s_{2}) 。$ $y_{1} + v_{1} = (x_{1} s_{1}, s_{1} x_{1} + x_{2} + s_{2}) 。$

在2-基分解的意义下, Z $_{4}^{n}$ $_{4}^{n}$ 上的四值逻辑函数f (y₁, y₂, …, y_n) 就可以表示为

$\begin{array}{l} f (y_{1}, y_{2}, \dots, y_{n}) = f_{1} (y_{1}, y_{2}, \dots, y_{n}) + \\ 2 f_{2} (y_{1}, y_{2}, \dots, y_{n}) ‚ (y_{1}, y_{2}, \dots, y_{n}) \in Ζ_{4}^{n} ‚ \end{array}$ $\begin{array}{l} f (y_{1}, y_{2}, \dots, y_{n}) = f_{1} (y_{1}, y_{2}, \dots, y_{n}) + \\ 2 f_{2} (y_{1}, y_{2}, \dots, y_{n}) ‚ (y_{1}, y_{2}, \dots, y_{n}) \in Ζ_{4}^{n} ‚ \end{array}$

其中f₁ (y₁, y₂, …, y_n) , f₂ (y₁, y₂, …, y_n) 都是定义在Z $_{4}^{n}$ $_{4}^{n}$ 上的逻辑函数, 又因为存在Z $_{4}^{n}$ $_{4}^{n}$ 到GF²ⁿ (2) 的一一映射

$\begin{array}{l} y = (y_{1}, y_{2}, \dots, y_{n}) \in Ζ_{4}^{n} | \to x = \\ (x_{1}, x_{2}, x_{3}, x_{4}, \dots, x_{2 n - 1}, x_{2 n}) \end{array}$ $\begin{array}{l} y = (y_{1}, y_{2}, \dots, y_{n}) \in Ζ_{4}^{n} | \to x = \\ (x_{1}, x_{2}, x_{3}, x_{4}, \dots, x_{2 n - 1}, x_{2 n}) \end{array}$

所以可将定义在Z $_{4}^{n}$ $_{4}^{n}$ 上的逻辑函数f₁ (y) , f₂ (y) , y∈Zⁿ₄分别转化为2n元布尔函数

《图29》

《图30》

对于a=a₁+2a₂, b=b₁+2b₂∈Z₄, 易知a和b在Z₄中的“差”a-b的2-基分解为

$\begin{array}{l} a - b = a + 3 b = (a_{1} + b_{1})_{m o d 2} + \\ 2 [(a_{1} b_{1} + a_{2} + b_{2})_{m o d 2}] ‚ (10) \end{array}$ $\begin{array}{l} a - b = a + 3 b = (a_{1} + b_{1})_{m o d 2} + \\ 2 [(a_{1} b_{1} + a_{2} + b_{2})_{m o d 2}] ‚ (10) \end{array}$

由式 (10) 知, 在上述意义下, 对v∈Z $_{4}^{n}$ $_{4}^{n}$ , Z $_{4}^{n}$ $_{4}^{n}$ 上的4值逻辑函数f (y) , y∈Z $_{4}^{n}$ $_{4}^{n}$ 的差分函数

$f (y + v) - f (y), y \in Ζ_{4}^{n} 。$ $f (y + v) - f (y), y \in Ζ_{4}^{n} 。$

可如下转换

$\begin{array}{l} f (y + v) - f (y) = [f_{1} (y + v) + f_{1} (y)]_{m o d 2} + \\ 2 {[f_{2} (y + v) + f_{2} (y) + \\ f_{1} (y) + f_{1} (y + v) f_{1} (y)]_{m o d 2}} ‚ (11) \end{array}$ $\begin{array}{l} f (y + v) - f (y) = [f_{1} (y + v) + f_{1} (y)]_{m o d 2} + \\ 2 {[f_{2} (y + v) + f_{2} (y) + \\ f_{1} (y) + f_{1} (y + v) f_{1} (y)]_{m o d 2}} ‚ (11) \end{array}$

再将y+v, y都用2-基分解表示可得到

f (y+v) -f (y) =[f₁ (x₁+s₁, s₁x₁+

x₂+s₂, …, x_n-1+s_n-1, s_n-1x_n-1+x_n+s_n) +

f₁ (x) ]_mod2 +2[f₁ (x₁+s₁, s₁x₁+x₂+s₂ , …,

x_n-1+s_n-1, s_n-1x_n-1+x_n+s_n) f₁ (x) +

f₁ (x) +f₂ (x₁+s₁, s₁x₁+x₂+s₂, …, x_n-1+

s_n-1, s_n-1x_n-1+x_n+s_n) +f₂ (x) ]_mod2 =

[f₁ (x⊕s) +f₁ (x) ]_mod2+2{[f₂ (x⊕s) +

f₂ (x) +f₁ (x) +f₁ (x⊕s) f₁ (x) ]_mod2}, (12)

其中

$\begin{array}{l} y = (y_{1}, y_{2}, \dots, y_{n}) \in Ζ_{4}^{n} | \to x = (x_{1}, x_{2}, \\ x_{3}, x_{4}, \dots, x_{2 n - 1}, x_{2 n}) \in G F^{2 n} (2) ‚ \\ v = (v_{1}, v_{2}, \dots, v_{n}) \in Ζ_{4}^{n} | \to s = (s_{1}, s_{2}, \\ s_{3}, s_{4}, \dots, s_{2 n - 1}, s_{2 n}) \in G F^{2 n} (2) 。 \end{array}$ $\begin{array}{l} y = (y_{1}, y_{2}, \dots, y_{n}) \in Ζ_{4}^{n} | \to x = (x_{1}, x_{2}, \\ x_{3}, x_{4}, \dots, x_{2 n - 1}, x_{2 n}) \in G F^{2 n} (2) ‚ \\ v = (v_{1}, v_{2}, \dots, v_{n}) \in Ζ_{4}^{n} | \to s = (s_{1}, s_{2}, \\ s_{3}, s_{4}, \dots, s_{2 n - 1}, s_{2 n}) \in G F^{2 n} (2) 。 \end{array}$

运用式 (11) 和式 (12) 及相关知识可以得到如下定理:

定理11 4值逻辑函数f (y) , y∈Z $_{4}^{n}$ $_{4}^{n}$ 为完全非线性函数的充要条件是对任意的

$\begin{array}{l} 0 \neq (v_{1}, \dots, v_{n}) = \\ (s_{1} + 2 s_{2}, \dots, s_{2 n - 1} + 2 s_{2 n}) \in Ζ_{4}^{n} ‚ \end{array}$ $\begin{array}{l} 0 \neq (v_{1}, \dots, v_{n}) = \\ (s_{1} + 2 s_{2}, \dots, s_{2 n - 1} + 2 s_{2 n}) \in Ζ_{4}^{n} ‚ \end{array}$

差分函数f (y+v) -f (y) 的2-基分解表示式 (11) 中的2值布尔函数

$\begin{array}{l} f_{1} (y + v) + f_{1} (y) ‚ f_{2} (y + v) + \\ f_{2} (y) + f_{1} (y) + f_{1} (y + v) f_{1} (y) \end{array}$ $\begin{array}{l} f_{1} (y + v) + f_{1} (y) ‚ f_{2} (y + v) + \\ f_{2} (y) + f_{1} (y) + f_{1} (y + v) f_{1} (y) \end{array}$

都平衡, 等价的就是式 (12) 中的2n元布尔函数

$\begin{array}{l} f_{1} (x \oplus s) + f_{1} (x) ‚ \\ f_{2} (x \oplus s) + f_{2} (x) + f_{1} (x) + f_{1} (x \oplus s) f_{1} (x) \end{array}$ $\begin{array}{l} f_{1} (x \oplus s) + f_{1} (x) ‚ \\ f_{2} (x \oplus s) + f_{2} (x) + f_{1} (x) + f_{1} (x \oplus s) f_{1} (x) \end{array}$

都平衡。

证明必要性显然。充分性由定理的假设及文献[6]中的“引理6.2”即得。

注3 由定理11的结论知, 若记n元四值完全非线性函数f (y₁, y₂, …, y_n) 的“2-基分解”为

$\begin{array}{l} f (y_{1}, \dots, y_{n}) = f_{1} (x_{1} + 2 x_{2}, \dots, x_{2 n - 1} + 2 x_{2 n}) + \\ 2 f_{2} (x_{1} + 2 x_{2}, \dots, x_{2 n - 1} + 2 x_{2 n}) = \\ (f_{1} (x_{1}, x_{2}, \dots, x_{2 n - 1}, x_{2 n}) ‚ \\ f_{2} (x_{1}, x_{2}, \dots, x_{2 n - 1}, x_{2 n})) ‚ \end{array}$ $\begin{array}{l} f (y_{1}, \dots, y_{n}) = f_{1} (x_{1} + 2 x_{2}, \dots, x_{2 n - 1} + 2 x_{2 n}) + \\ 2 f_{2} (x_{1} + 2 x_{2}, \dots, x_{2 n - 1} + 2 x_{2 n}) = \\ (f_{1} (x_{1}, x_{2}, \dots, x_{2 n - 1}, x_{2 n}) ‚ \\ f_{2} (x_{1}, x_{2}, \dots, x_{2 n - 1}, x_{2 n})) ‚ \end{array}$

则作为关于 (x₁, x₂, …, x_2n-1, x_2n) 的布尔函数

$f_{1} (x) = f_{1} (x_{1}, x_{2}, \dots, x_{2 n - 1}, x_{2 n})$ $f_{1} (x) = f_{1} (x_{1}, x_{2}, \dots, x_{2 n - 1}, x_{2 n})$

一定是关于变量组 (x₁, x₂) , …, (x_2n-1, x_2n) 的类差分平衡函数。

根据定理11若想构造Z $_{4}^{n}$ $_{4}^{n}$ 上的完全非线性函数, 只须先构造一个2n元类差分平衡函数f₁;再根据f₂ (x⊕s) + f₂ (x) +f₁ (x) +f₁ (x⊕s) ·f₁ (x) 平衡的要求寻找f₂即可, 基于此, 在首先分析得到所有4元类差分平衡函数的基础上, 可编程搜索出Z $_{4}^{2}$ $_{4}^{2}$ 上所有的完全非线性函数, 具体做法是:

假设f₁ (x) , f₂ (x) 的常数项为0。首先通过理论分析找到所有的四元类差分平衡函数, 共192个, 然后对于每个四元类差分平衡函数f₁ (x) , 通过上机搜索找到与上述各四元类差分平衡函数做成二元四值完全非线性函数的四元布尔函数f₂ (x) , 共得到16 384个二元四值完全非线性函数。另外, 可以证明完全非线性函数的2个分量函数中的任意一个分量加1后所得到的新的函数仍然是完全非线性函数, 所以二元四值完全非线性函数的总个数为16 384×4=65 536。这个搜索过程在Pentium (Ⅳ) 计算机上用不到2 h的时间便全部完成, 而若直接按照真值表穷尽搜索所有的二元四值完全非线性函数, 搜索量是4¹⁶, 如果没有快速算法这个计算量在普通计算机上实施起来是比较困难的, 可见类差分平衡函数的研究是很有意义的。下面给出用这种方法得到的2个二元四值完全非线性函数:

$\begin{array}{l} g (y_{1}, y_{2}) = (x_{1} x_{2} + x_{3} x_{4})_{m o d 2} + \\ 2 (x_{4} + x_{1} x_{4} + x_{2} x_{3} + x_{1} x_{3} x_{4})_{m o d 2} ； \\ h (y_{1}, y_{2}) = (x_{1} x_{2} + x_{3} x_{4})_{m o d 2} + \\ 2 (x_{2} + x_{4} + x_{1} x_{4} + x_{2} x_{3} + x_{3} x_{4})_{m o d 2} 。 \end{array}$ $\begin{array}{l} g (y_{1}, y_{2}) = (x_{1} x_{2} + x_{3} x_{4})_{m o d 2} + \\ 2 (x_{4} + x_{1} x_{4} + x_{2} x_{3} + x_{1} x_{3} x_{4})_{m o d 2} ； \\ h (y_{1}, y_{2}) = (x_{1} x_{2} + x_{3} x_{4})_{m o d 2} + \\ 2 (x_{2} + x_{4} + x_{1} x_{4} + x_{2} x_{3} + x_{3} x_{4})_{m o d 2} 。 \end{array}$

《7 结语》

7 结语

笔者提出了类差分平衡函数的概念, 讨论了类差分平衡函数的性质及其在剩余类环上的完全非线性函数研究中的应用。因为完全非线性函数的直和仍然是完全非线性函数, 所以Z₄上关于任意正偶数个变量的完全非线性函数都存在, 并且上面得到的二元四值完全非线性函数可以大量构造。

计算表明, 当m>2时, 环Z_2^m上的完全非线性函数的2-基分解意义下的第一个分量函数的形式和性质与类差分平衡函数相似, 故类差分平衡函数的研究对环上的完全非线性函数的研究也有重要的指导意义;另外, 用2-基分解的方法研究环上的问题, 这一思想还可用于一般剩余类环Z_p^m (p是大于2的素数) 上该类逻辑函数的研究中。

关于类差分平衡函数的研究仍然有许多遗留问题, 比如类差分平衡函数是否像Bent函数那样非退化?其谱特征和自相关特征为何?笔者曾经计算了大量的六元类差分平衡函数的Walsh谱及自相关函数值, 发现这些六元类差分平衡函数都是非退化的, 其Walsh谱至多取下述5个值:0, ±2^-3, ±2^-2, 其自相关函数在非零点至多取下述3个值:0, ±2^-2。由此猜测n元类差分平衡函数的Walsh谱取值可能比较均匀;自相关函数在非零点的绝对值也比较均匀。故类差分平衡函数除去可用于构造Z $_{4}^{n}$ $_{4}^{n}$ 上的完全非线性函数外, 也许其自身在密码设计中还能有直接应用。

展示更多