密码函数的一类递归构造方法

摘要

首先利用递归的方法证明了结构形式更为一般的布尔函数的Walsh谱分解式，然后利用这类布尔函数Walsh谱分解式，给出了密码学和编码学中具有重要应用价值的一些布尔函数，如弹性函数、Bent函数以及满足严格雪崩准则的布尔函数的构造方法。

正文

《1 引言》

1 引言

在密码体制中, 密钥流生成器中非线性组合函数的设计对密码体制的安全起着关键的作用。根据相应需求, 密码设计者设计了各类特殊的非线性组合函数, 如为抵抗相关攻击, 密码设计者给出了相关免疫函数 ^[1] 的概念和构造, 而为抵抗差分攻击, Rothaus又提出了Bent函数 ^[2] 的概念, 后来不少专家又对Bent函数的性质和构造进行了深入研究。考虑到弹性函数 (平衡的相关免疫函数) 和Bent函数以及多输出Bent函数在密码设计中的重要应用, 构造这两类函数一直是密码设计者所关注的重要问题。T. Siegenthaler给出了一种构造平衡相关免疫布尔函数的方法 ^[1];而P. Camion等人利用编码理论来研究相关免疫布尔函数, 给出了具有高阶相关免疫性的代数次数为2的布尔函数的递归构造方法 ^[3];张木想等人利用Hadamard矩阵理论提出了直接构造任意阶相关免疫函数的思想和方法 ^[4];在Bent函数的构造方面, 典型的构造法有Rothaus构造法 (但它并不能构造全部Bent函数) 、Walsh-Hadamard矩阵构造法、基于Kronecker代数和变元置换的构造等 ^[5], 后来, 王隽又在Bent矩阵原则上给出了Bent函数的一种完全构造法 ^[6] ; 文献[7]给出了一类布尔函数的Walsh谱的分解式并且讨论了它在密码设计中的应用, 如通过它可以递归构造弹性函数 ^[8] 以及一维Bent函数 ^[6]。首先, 笔者利用布尔随机变量联合分布的分解式 ^[9], 用递归的方法证明了结构形式更为一般的一类布尔函数的Walsh谱分解式。由于密码学中逻辑函数的密码性质几乎完全可以由其Walsh谱来刻画, 因此所给出的Walsh谱分解式在密码函数的构造中有重要应用。其次, 讨论了这类Walsh谱分解式在密码设计中的应用, 通过它给出了弹性函数和Bent函数的一种递归构造方法, 而平衡且满足严格雪崩准则的函数有很大的应用价值, 同时, 满足严格雪崩的布尔函数和H布尔函数 ^[10] 又是等价的, 而H布尔函数是阵列编码中一个重要的函数类, 因此构造平衡且满足严格雪崩准则的布尔函数具有重要意义。

此外, 多输出Bent函数在分组密码设计和通信中都有重要应用, 但多输出Bent函数的构造和计数又是一个公开的同时也是困难的问题, 其中密码学中常用的通过级联来递归构造新的逻辑函数的方法, 在构造多输出Bent函数时是失效的。利用笔者所得到的一类布尔函数Walsh谱的分解式, 就可以给出多输出Bent函数的一种递归构造法。

《2 基本概念》

2 基本概念

定义1 ^[11] 设f (x) , x∈GFⁿ (2) 为n元布尔函数, 则称

《图1》

为f (x) 的Walsh循环谱。

定义2 ^[11] 设f (x) , x∈GFⁿ (2) 为n元布尔函数, 则 f (x) 是m阶弹性函数当且仅当对任意的w∈GFⁿ (2) , 且W (w) ≤ m, S_(f) (w) = 0, 其中W (w) 表示向量w中所含1的个数。

定义3 ^[2] 设f (x) , x∈GFⁿ (2) 为n元布尔函数, 则f (x) 是Bent函数的充分必要条件是对任意的w∈GFⁿ (2) , 都有S $_{(f)}^{2}$ $_{(f)}^{2}$ (w) = 1/2ⁿ;或等价的当且仅当对任意的s∈ GFⁿ (2) ＼{0}, 都有

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

引理1 (布尔随机变量联合分布的分解式) ^[9] 设 (Ω, F, P) 是一概率空间, Y = (Y₁, Y₂, …, Y_n) 是 (Ω, F, P) 上的任一n维布尔随机向量, B∈F是任一事件, 则对任意的a = (a₁, a₂, …, a_n) ∈GFⁿ (2) , 都有

$\begin{array}{l} Ρ {B, Y_{1} = a_{1}, Y_{2} = a_{2}, \dots, Y_{n} = a_{n}} = \\ \frac{1}{2^{n - 1}} \sum_{0 \neq (λ_{1}, \dots, λ_{n}) \in G F^{n} (2)} Ρ {B, λ_{1} Y_{1} + \dots + λ_{n} Y_{n} = \\ λ_{1} a_{1} + \dots + λ_{n} a_{n}} - \frac{2^{n - 1} - 1}{2^{n - 1}} Ρ (B) 。 \end{array}$ $\begin{array}{l} Ρ {B, Y_{1} = a_{1}, Y_{2} = a_{2}, \dots, Y_{n} = a_{n}} = \\ \frac{1}{2^{n - 1}} \sum_{0 \neq (λ_{1}, \dots, λ_{n}) \in G F^{n} (2)} Ρ {B, λ_{1} Y_{1} + \dots + λ_{n} Y_{n} = \\ λ_{1} a_{1} + \dots + λ_{n} a_{n}} - \frac{2^{n - 1} - 1}{2^{n - 1}} Ρ (B) 。 \end{array}$

《3 一类布尔函数Walsh谱的分解式》

3 一类布尔函数Walsh谱的分解式

下面用概率的方法给出具有某种形式的一类布尔函数的Walsh谱分解式。

定理1 设ϕ (x, y) , x∈GFⁿ (2) , y∈GF^r (2) 为n+r元布尔函数, l₁ (x) 是n元布尔函数, l₁ (y) 是r元布尔函数, 则对任意的w∈GFⁿ (2) , v∈GF^r (2) , 有

$\begin{array}{l} S_{(ϕ + l_{1} l_{2})} (w, v) = \\ \frac{1}{2} [S_{(ϕ)} (w, v) + S_{(ϕ + l_{1})} (w, v) + \\ S_{(ϕ + l_{2})} (w, v) - S_{(ϕ + l_{1} + l_{2})} (w, v)] 。 (1) \end{array}$ $\begin{array}{l} S_{(ϕ + l_{1} l_{2})} (w, v) = \\ \frac{1}{2} [S_{(ϕ)} (w, v) + S_{(ϕ + l_{1})} (w, v) + \\ S_{(ϕ + l_{2})} (w, v) - S_{(ϕ + l_{1} + l_{2})} (w, v)] 。 (1) \end{array}$

证明设X₁, X₂, …, X_n, Y₁, Y₂, …, Y_r 是定义在同一概率空间上相互独立且都具有均匀分布的布尔随机变量, 对任意的w∈GFⁿ (2) , v∈GF^r (2) , 由全概率公式以及引理1有

$\begin{array}{l} Ρ {ϕ (X, Y) + l_{1} (X) l_{2} (Y) = w X + v Y} = Ρ {ϕ (X, Y) = w X + v Y, l_{1} (X) = 0, l_{2} (Y) = 0} + Ρ {ϕ (X, Y) = w X + v Y, l_{1} (X) = 0, l_{2} (Y) = 1} + Ρ {ϕ (X, Y) = w X + v Y, l_{1} (X) = 1, l_{2} (Y) = 0} + Ρ {ϕ (X, Y) + 1 = w X + v Y, l_{1} (X) = 1, l_{2} (Y) = 1} = \frac{1}{4} [Ρ {ϕ (X, Y) = w X + v Y} + Ρ {l_{1} (X) = 0} + Ρ {l_{2} (Y) = 0} + Ρ {ϕ (X, Y) + l_{1} (X) = w X + v Y} + Ρ {ϕ (X, Y) + l_{2} (Y) = w X + v Y} + Ρ {l_{1} (X) + l_{2} (Y) = 0} + Ρ {ϕ (X, Y) + l_{1} (X) + l_{2} (Y) = w X + v Y} - 3] + \frac{1}{4} [Ρ {ϕ (X, Y) = w X + v Y} + Ρ {l_{1} (X) = 0} + Ρ {l_{2} (Y) = 1} + Ρ {ϕ (X, Y) + l_{1} (X) = w X + v Y} + Ρ {ϕ (X, Y) + l_{2} (Y) = w X + v Y + 1} + Ρ {l_{1} (X) + l_{2} (Y) = 1} + Ρ {ϕ (X, Y) + l_{1} (X) + l_{2} (Y) = w X + v Y + 1} - 3] + \frac{1}{4} [Ρ {ϕ (X, Y) = w X + v Y} + \\ Ρ {l_{1} (X) = 1} + Ρ {l_{2} (Y) = 0} + Ρ {ϕ (X, Y) + l_{1} (X) = w X + v Y + 1} + Ρ {ϕ (X, Y) + l_{2} (Y) = w X + v Y} + \\ Ρ {l_{1} (X) + l_{2} (Y) = 1} + Ρ {ϕ (X, Y) + l_{1} (X) + l_{2} (Y) = w X + v Y + 1} - 3] + \frac{1}{4} [Ρ {ϕ (X, Y) = w X + v Y + \\ 1} + Ρ {l_{1} (X) = 1}, Ρ {l_{2} (Y) = 1} + Ρ {ϕ (X, Y) + l_{1} (X) = w X + v Y} + Ρ {ϕ (X, Y) + l_{2} (Y) = w X + v Y} + \\ Ρ {l_{1} (X) + l_{2} (Y) = 0} + Ρ {ϕ (X, Y) + l_{1} (X) + l_{2} (Y) = w X + v Y + 1} - 3] = \frac{1}{2} [Ρ {ϕ (X, Y) = w X + v Y} + \\ Ρ {ϕ (X, Y) + l_{1} (X) = w X + v Y} + Ρ {ϕ (X, Y) + l_{2} (Y) = w X + v Y} + Ρ {ϕ (X, Y) + l_{1} (X) + l_{2} (Y) = w X + v Y + 1}] - \frac{1}{2} = \frac{1}{4} [S (ϕ) (w, v) + S_{(ϕ + l_{1})} (w, v) + S_{(ϕ + l_{2})} (w, v) - S_{(ϕ + l_{1} + l_{2})} (w, v)] + \frac{1}{2} 。 \end{array}$ $\begin{array}{l} Ρ {ϕ (X, Y) + l_{1} (X) l_{2} (Y) = w X + v Y} = Ρ {ϕ (X, Y) = w X + v Y, l_{1} (X) = 0, l_{2} (Y) = 0} + Ρ {ϕ (X, Y) = w X + v Y, l_{1} (X) = 0, l_{2} (Y) = 1} + Ρ {ϕ (X, Y) = w X + v Y, l_{1} (X) = 1, l_{2} (Y) = 0} + Ρ {ϕ (X, Y) + 1 = w X + v Y, l_{1} (X) = 1, l_{2} (Y) = 1} = \frac{1}{4} [Ρ {ϕ (X, Y) = w X + v Y} + Ρ {l_{1} (X) = 0} + Ρ {l_{2} (Y) = 0} + Ρ {ϕ (X, Y) + l_{1} (X) = w X + v Y} + Ρ {ϕ (X, Y) + l_{2} (Y) = w X + v Y} + Ρ {l_{1} (X) + l_{2} (Y) = 0} + Ρ {ϕ (X, Y) + l_{1} (X) + l_{2} (Y) = w X + v Y} - 3] + \frac{1}{4} [Ρ {ϕ (X, Y) = w X + v Y} + Ρ {l_{1} (X) = 0} + Ρ {l_{2} (Y) = 1} + Ρ {ϕ (X, Y) + l_{1} (X) = w X + v Y} + Ρ {ϕ (X, Y) + l_{2} (Y) = w X + v Y + 1} + Ρ {l_{1} (X) + l_{2} (Y) = 1} + Ρ {ϕ (X, Y) + l_{1} (X) + l_{2} (Y) = w X + v Y + 1} - 3] + \frac{1}{4} [Ρ {ϕ (X, Y) = w X + v Y} + \\ Ρ {l_{1} (X) = 1} + Ρ {l_{2} (Y) = 0} + Ρ {ϕ (X, Y) + l_{1} (X) = w X + v Y + 1} + Ρ {ϕ (X, Y) + l_{2} (Y) = w X + v Y} + \\ Ρ {l_{1} (X) + l_{2} (Y) = 1} + Ρ {ϕ (X, Y) + l_{1} (X) + l_{2} (Y) = w X + v Y + 1} - 3] + \frac{1}{4} [Ρ {ϕ (X, Y) = w X + v Y + \\ 1} + Ρ {l_{1} (X) = 1}, Ρ {l_{2} (Y) = 1} + Ρ {ϕ (X, Y) + l_{1} (X) = w X + v Y} + Ρ {ϕ (X, Y) + l_{2} (Y) = w X + v Y} + \\ Ρ {l_{1} (X) + l_{2} (Y) = 0} + Ρ {ϕ (X, Y) + l_{1} (X) + l_{2} (Y) = w X + v Y + 1} - 3] = \frac{1}{2} [Ρ {ϕ (X, Y) = w X + v Y} + \\ Ρ {ϕ (X, Y) + l_{1} (X) = w X + v Y} + Ρ {ϕ (X, Y) + l_{2} (Y) = w X + v Y} + Ρ {ϕ (X, Y) + l_{1} (X) + l_{2} (Y) = w X + v Y + 1}] - \frac{1}{2} = \frac{1}{4} [S (ϕ) (w, v) + S_{(ϕ + l_{1})} (w, v) + S_{(ϕ + l_{2})} (w, v) - S_{(ϕ + l_{1} + l_{2})} (w, v)] + \frac{1}{2} 。 \end{array}$

由Walsh谱的概率表示式 ^[6]知

$\begin{array}{l} S_{(ϕ + l_{1} l_{2})} (w, v) = \frac{1}{2} \\ [S_{(ϕ)} (w, v) + S_{(ϕ + l_{1})} (w, v) + \\ S_{(ϕ + l_{2})} (w, v) - S_{(ϕ + l_{1} + l_{2})} (w, v)] 。 \end{array}$ $\begin{array}{l} S_{(ϕ + l_{1} l_{2})} (w, v) = \frac{1}{2} \\ [S_{(ϕ)} (w, v) + S_{(ϕ + l_{1})} (w, v) + \\ S_{(ϕ + l_{2})} (w, v) - S_{(ϕ + l_{1} + l_{2})} (w, v)] 。 \end{array}$

下面利用定理1, 用递归方法给出一类布尔函数Walsh谱的分解式的证明。

定理2 设n+r元布尔函数

$\begin{array}{l} ψ_{k} (x, y) = f (x) + g (y) + \sum_{i = 1}^{k} h_{1 i} (x) \cdot h_{2 i} (y) ‚ \\ x \in G F^{n} (2) ‚ y \in G F^{r} (2) ‚ \end{array}$ $\begin{array}{l} ψ_{k} (x, y) = f (x) + g (y) + \sum_{i = 1}^{k} h_{1 i} (x) \cdot h_{2 i} (y) ‚ \\ x \in G F^{n} (2) ‚ y \in G F^{r} (2) ‚ \end{array}$

其中h_1i (x) , x∈GFⁿ (2) , 1≤i≤k都是n元布尔函数, h_2i (y) , y∈GF^r (2) , 1≤i≤k都是r元布尔函数, 记

$\begin{array}{l} h_{1}^{(k)} (x) = (h_{11} (x), h_{12} (x), \dots, h_{1 k} (x)), \\ h_{2}^{(k)} (y) = (h_{21} (x), h_{22} (y), \dots, h_{2 k} (y)), \end{array}$ $\begin{array}{l} h_{1}^{(k)} (x) = (h_{11} (x), h_{12} (x), \dots, h_{1 k} (x)), \\ h_{2}^{(k)} (y) = (h_{21} (x), h_{22} (y), \dots, h_{2 k} (y)), \end{array}$

则对任意的w∈GFⁿ (2) , v∈GF^r (2) , 有

$\begin{array}{l} S_{(ψ_{k})} (w, v) = \frac{1}{2^{k}} \sum_{α \in G F^{k} (2)} S_{(g + α h_{2}^{(k)})} (v) \cdot \\ \sum_{β \in G F^{k} (2)} (- 1)^{α β} S_{(f + β h_{1}^{(k)})} (w) ； (2) \\ S_{(ψ_{k})} (w, v) = \frac{1}{2^{k}} \sum_{β \in G F^{k} (2)} S_{(f + β h_{1}^{(k)})} (w) \cdot \\ \sum_{α \in G F^{k} (2)} (- 1)^{α β} S_{(g + α h_{2}^{(k)})} (v) (3) \end{array}$ $\begin{array}{l} S_{(ψ_{k})} (w, v) = \frac{1}{2^{k}} \sum_{α \in G F^{k} (2)} S_{(g + α h_{2}^{(k)})} (v) \cdot \\ \sum_{β \in G F^{k} (2)} (- 1)^{α β} S_{(f + β h_{1}^{(k)})} (w) ； (2) \\ S_{(ψ_{k})} (w, v) = \frac{1}{2^{k}} \sum_{β \in G F^{k} (2)} S_{(f + β h_{1}^{(k)})} (w) \cdot \\ \sum_{α \in G F^{k} (2)} (- 1)^{α β} S_{(g + α h_{2}^{(k)})} (v) (3) \end{array}$

证明 (归纳法) 当k=1时, 在定理1中, 取

$\begin{array}{l} ϕ (x, y) = f (x) + g (x) ‚ l_{1} (x) = h_{11} (x) ‚ \\ l_{2} (y) = h_{21} (y), \end{array}$ $\begin{array}{l} ϕ (x, y) = f (x) + g (x) ‚ l_{1} (x) = h_{11} (x) ‚ \\ l_{2} (y) = h_{21} (y), \end{array}$

可得

$\begin{array}{l} S_{(f + g + h_{11} h_{21})} (w, v) = \frac{1}{2} [S_{(f)} (w) S_{(g)} (v) + \\ S_{(f + h_{11})} (w) S_{(g)} (v) + S_{(f)} (w) S_{(g + h_{21})} (v) - \\ S_{(f + h_{11})} (w) S_{(g + h_{21})} (v)] = \\ \frac{1}{2} S_{(g)} (v) [S_{(f)} (w) + S_{(f + h_{11})} (w)] + \\ \frac{1}{2} S_{(g + h_{21})} (v) [S_{(f)} (w) - S_{(f + h_{11})} (w)], \end{array}$ $\begin{array}{l} S_{(f + g + h_{11} h_{21})} (w, v) = \frac{1}{2} [S_{(f)} (w) S_{(g)} (v) + \\ S_{(f + h_{11})} (w) S_{(g)} (v) + S_{(f)} (w) S_{(g + h_{21})} (v) - \\ S_{(f + h_{11})} (w) S_{(g + h_{21})} (v)] = \\ \frac{1}{2} S_{(g)} (v) [S_{(f)} (w) + S_{(f + h_{11})} (w)] + \\ \frac{1}{2} S_{(g + h_{21})} (v) [S_{(f)} (w) - S_{(f + h_{11})} (w)], \end{array}$

这正是文献[7]所给出的布尔函数的Walsh谱分解式。假设结论对k成立, 即

$\begin{array}{l} S_{(ψ_{k})} (w, v) = \frac{1}{2^{k}} \sum_{α \in G F^{k} (2)} S_{(g + α h_{2}^{(k)})} (v) \cdot \\ \sum_{β \in G F^{k} (2)} (- 1)^{α β} S_{(f + β h_{1}^{(k)})} (w) 。 (4) \end{array}$ $\begin{array}{l} S_{(ψ_{k})} (w, v) = \frac{1}{2^{k}} \sum_{α \in G F^{k} (2)} S_{(g + α h_{2}^{(k)})} (v) \cdot \\ \sum_{β \in G F^{k} (2)} (- 1)^{α β} S_{(f + β h_{1}^{(k)})} (w) 。 (4) \end{array}$

对k+1, 由归纳假设知

《图2》

在式 (4) 中, 取f (x) 为f (x) +h_1k+1 (x) , 则

$\begin{array}{l} S_{(ψ_{k} + h_{1 k + 1})} (w, v) = \frac{1}{2^{k}} \sum_{α \in G F^{k} (2)} S_{(g + α h_{2}^{(k)})} (v) \cdot \\ \sum_{β \in G F^{k} (2)} (- 1)^{α β} S_{(f + h_{1 k + 1} + β h_{1}^{(k)})} (w) 。 \end{array}$ $\begin{array}{l} S_{(ψ_{k} + h_{1 k + 1})} (w, v) = \frac{1}{2^{k}} \sum_{α \in G F^{k} (2)} S_{(g + α h_{2}^{(k)})} (v) \cdot \\ \sum_{β \in G F^{k} (2)} (- 1)^{α β} S_{(f + h_{1 k + 1} + β h_{1}^{(k)})} (w) 。 \end{array}$

同理, 在式 (4) 中, 取g (y) 为g (y) +h_2k+1 (y) , 则

《图3》

在式 (4) 中, 取g (y) 为g (y) +h_2k+1 (y) , 取f (x) 为f (x) +h_1k+1 (x) , 则

《图4》

由式 (5) 得

《图5》

所得结论对k+1也成立, 因而式 (2) 得证。

同样的方法, 由f (x) 和g (y) 的对称性可得式 (3) 。

《4 一类Walsh谱分解式在密码函数的构造中的应用》

4 一类Walsh谱分解式在密码函数的构造中的应用

文献[8]指出了研究弹性函数——平衡的相关免疫函数的意义, 并给出了弹性函数的一些构造方法。下面的定理表明, 利用上面的Walsh谱的分解式也可以递归构造弹性函数。

定理3 设ψ_k (x, y) =f (x) +g (y) + $\sum_{i = 1}^{k} h_{1 i} (x) h_{2 i} (y),$ $\sum_{i = 1}^{k} h_{1 i} (x) h_{2 i} (y),$ h $_{1}^{(k)}$ $_{1}^{(k)}$ (x) 和h $_{2}^{(k)}$ $_{2}^{(k)}$ (y) 如定理2中所定义, 若对任意的α, β∈GF^k (2) , f (x) +βh $_{1}^{(k)}$ $_{1}^{(k)}$ (x) 都是m₁阶弹性函数, g (y) +αh $_{2}^{(k)}$ $_{2}^{(k)}$ (y) 都是m₂阶弹性函数, 则ψ_k (x, y) 是n+r元m₁+m₂+1阶弹性函数。

证明对任意的w∈GFⁿ (2) , v∈GF^r (2) , 若W (w, v) ≤m₁+m₂+1, 则有下列两种情况:

1) w=0或v=0, 设w=0, 则由式 (2) 知

$\begin{array}{l} S_{(ψ_{k})} (0, v) = \frac{1}{2^{k}} \sum_{α \in G F^{k} (2)} S_{(g + α h_{2}^{(k)})} (v) \cdot \\ \sum_{β \in G F^{k} (2)} (- 1)^{α β} S_{(f + β h_{1}^{(k)})} (0), \end{array}$ $\begin{array}{l} S_{(ψ_{k})} (0, v) = \frac{1}{2^{k}} \sum_{α \in G F^{k} (2)} S_{(g + α h_{2}^{(k)})} (v) \cdot \\ \sum_{β \in G F^{k} (2)} (- 1)^{α β} S_{(f + β h_{1}^{(k)})} (0), \end{array}$

由f (x) +βh $_{1}^{(k)}$ $_{1}^{(k)}$ (x) 是平衡函数知

$S_{(f + β h_{1}^{(k)}} (0) = 0 ‚ 所以 S_{(ψ_{k})} (0, v) = 0 。$ $S_{(f + β h_{1}^{(k)}} (0) = 0 ‚ 所以 S_{(ψ_{k})} (0, v) = 0 。$

当v=0时, 同样的方法, 由式 (3) 知S_{(ψ_k)} (w, 0) =0。

2) w≠0且v≠0, 则此时或者W (w) ≤m₁, 或者W (v) ≤m₂, 不妨设W (w) ≤m₁, 则由于对任意的β∈GF^k (2) , f (x) +βh $_{1}^{(k)}$ $_{1}^{(k)}$ (x) 是m₁阶弹性函数, 即S_{(f+βh^(k)₁)} (w) =0, 由式 (2) 知

$\begin{array}{l} S_{(ψ_{k})} (w, v) = \frac{1}{2^{k}} \sum_{α \in G F^{k} (2)} S_{(g + α h_{2}^{(k)})} (v) \cdot \\ \sum_{β \in G F^{k} (2)} (- 1)^{α β} S_{(f + β h_{2}^{(k)})} (w) = 0 。 \end{array}$ $\begin{array}{l} S_{(ψ_{k})} (w, v) = \frac{1}{2^{k}} \sum_{α \in G F^{k} (2)} S_{(g + α h_{2}^{(k)})} (v) \cdot \\ \sum_{β \in G F^{k} (2)} (- 1)^{α β} S_{(f + β h_{2}^{(k)})} (w) = 0 。 \end{array}$

若W (v) ≤m₂, 同样的方法, 由式 (3) 知S_{(ψ_k)} (w, v) =0。

所以由定义2知ψ_k (x, y) 是n+r元m₁+m₂+1阶弹性函数。

推论1 设ψ_k (x, y) =f (x) +g (y) + $\sum_{i = 1}^{k} h_{1 i} (x) h_{2 i} (y) ‚$ $\sum_{i = 1}^{k} h_{1 i} (x) h_{2 i} (y) ‚$ h $_{1}^{(k)}$ $_{1}^{(k)}$ (x) 和h $_{2}^{(k)}$ $_{2}^{(k)}$ (y) 如定理2中所定义, 若对任意的α, β∈GF^k (2) , f (x) +βh^(k)₁ (x) 是m₁阶弹性函数, g (y) +αh $_{2}^{(k)}$ $_{2}^{(k)}$ (y) 是任意r元平衡的布尔函数, 则ψ_k (x, y) 是n+r元m₁+1阶弹性函数。

注:在定理3中, 特别地取k=2, 即得文献[8]的结论。

Bent函数的构造也是密码设计者关心的问题, 利用上面的Walsh谱的分解式同样可以由变元个数少的Bent函数构造变元个数多的Bent函数。

定理4 设ψ_k (x, y) =f (x) +g (y) + $\sum_{i = 1}^{k} h_{1 i} (x) h_{2 i} (y) ‚$ $\sum_{i = 1}^{k} h_{1 i} (x) h_{2 i} (y) ‚$ h $_{1}^{(k)}$ $_{1}^{(k)}$ (x) 和h $_{2}^{(k)}$ $_{2}^{(k)}$ (y) 如定理2中所定义, 若对任意的α, β∈GF^k (2) , f (x) +βh^(k)₁ (x) 和g (y) +αh $_{2}^{(k)}$ $_{2}^{(k)}$ (y) 都是Bent函数, 且下列条件之一成立:

1) 对任意给定的w∈GFⁿ (2) , 存在α_w∈GF^k (2) , b_w∈GF (2) (只与w有关) , 使得对任意的β∈GF^k (2) , 都有

S_{(f+βh^(k)₁} (w) =2^-n/2 (-1) ^α_wβ+b_w;

2) 对任意给定的v∈GF^r (2) , 存在β_v∈GF^k (2) , b_v∈GF (2) (只与v有关) , 使得对任意的α∈GF^k (2) , 都有

S_{(g+αh^(k)₁} (v) =2^-r/2 (-1) ^β_vα+b_v;

则ψ_k (x, y) 是n+r元Bent函数。

证明 1) 若对任意给定的w∈GFⁿ (2) , 存在α_w∈GF^k (2) , b_w∈GF (2) , 使得对任意的β∈GF^k (2) , 都有

S_{(f+βh^(k)₁} (w) =2^-n/2 (-1) ^α_wβ+b_w,

则由式 (2) 知

$\begin{array}{l} S_{(ψ_{k})} (w, v) = \frac{1}{2^{k}} \sum_{α \in G F^{k} (2)} S_{(g + α h_{2}^{(k)})} (v) \cdot \\ \sum_{β \in G F^{k} (2)} (- 1)^{α β} S_{(f + β h_{1}^{(k)})} (w) = \\ 2^{- k - n / 2} \sum_{α \in G F^{k} (2)} S_{(g + α h_{2}^{(k)})} (v) \cdot \\ \sum_{β \in G F^{k} (2)} (- 1)^{α β + α_{w} β + b_{w}} \overset{正交性}{=} \\ 2^{- n / 2} (- 1)^{b_{w}} S_{(g + α_{w} h_{2}^{(k)})} (v) \end{array}$ $\begin{array}{l} S_{(ψ_{k})} (w, v) = \frac{1}{2^{k}} \sum_{α \in G F^{k} (2)} S_{(g + α h_{2}^{(k)})} (v) \cdot \\ \sum_{β \in G F^{k} (2)} (- 1)^{α β} S_{(f + β h_{1}^{(k)})} (w) = \\ 2^{- k - n / 2} \sum_{α \in G F^{k} (2)} S_{(g + α h_{2}^{(k)})} (v) \cdot \\ \sum_{β \in G F^{k} (2)} (- 1)^{α β + α_{w} β + b_{w}} \overset{正交性}{=} \\ 2^{- n / 2} (- 1)^{b_{w}} S_{(g + α_{w} h_{2}^{(k)})} (v) \end{array}$

所以ψ_k (x, y) 是n+r元Bent函数。

用同样的方法, 由式 (3) 可以证明, 当条件2成立时ψ_k (x, y) 是n+r元Bent函数。

注:在上面的定理中, 当k=1时, 则对任意的w∈GFⁿ (2) , S_(f) (w) 和S_(f+h₁₁) (w) 自然满足条件1;当k=2时, 若对任意的w∈GFⁿ (2) , S_(f) (w) , S_(f+h₁₁) (w) , S_(f+h₁₂) (w) , S_{(f+h₁₁+h₁₂)} (w) 同号, 或两个为正值、两个为负值时, 则满足定理的条件1。

下面给出一类满足定理4条件的函数的构造:

定理5 设f (x) =π (x⁽²⁾) x⁽¹⁾, x= (x⁽¹⁾, x⁽²⁾) ∈GF²ⁿ (2) , 其中π为GFⁿ (2) 到GFⁿ (2) 的置换, 又设h_1i (x⁽¹⁾, x⁽²⁾) =l_i (x⁽²⁾) (1≤i≤k) , g (y) , h_2i (y) (1≤i≤k) , y∈GF^r (2) 满足:对任意的α∈GF^k (2) , g (y) +αh $_{2}^{(k)}$ $_{2}^{(k)}$ (y) 都是Bent函数, 则

$ψ_{k} (x, y) = f (x) + g (y) + \sum_{i = 1}^{k} l_{i} (x^{(2)}) h_{2 i} (y)$ $ψ_{k} (x, y) = f (x) + g (y) + \sum_{i = 1}^{k} l_{i} (x^{(2)}) h_{2 i} (y)$

是2n+r元Bent函数。

证明记l^(k) (x⁽²⁾) = (l₁ (x⁽²⁾) , …, l_k (x⁽²⁾) ) , 则对任意的w⁽¹⁾, w⁽²⁾∈GFⁿ (2) , 及任意的β∈GF^k (2) , 有

$\begin{array}{l} S_{(f + β h_{1}^{(k)})} (w^{(1)}, w^{(2)}) = 2^{- 2 n} \sum_{x^{(1)} \in G F^{n} (2), x^{(2)} \in G F^{n} (2)} (- 1)^{π (x^{(2)}) x^{(1)} + β l^{(k)} (x^{(2)}) + w^{(1)} x^{(1)} + w^{(2)} x^{(2)}} = \\ 2^{- 2 n} \sum_{x^{(2)} \in G F^{n} (2)} (- 1)^{β l^{(k)} (x^{(2)}) + w^{(2)} x^{(2)}} \sum_{x^{(1)} \in G F^{n} (2)} (- 1)^{(π (x^{(2)}) + w^{(1)}) x^{(1)}} = 2^{- 2 n} (- 1)^{β l^{(k)} (x_{w^{(1)}}^{(2)} + w^{(2)} x_{w^{(1)}}^{(2)}}, \end{array}$ $\begin{array}{l} S_{(f + β h_{1}^{(k)})} (w^{(1)}, w^{(2)}) = 2^{- 2 n} \sum_{x^{(1)} \in G F^{n} (2), x^{(2)} \in G F^{n} (2)} (- 1)^{π (x^{(2)}) x^{(1)} + β l^{(k)} (x^{(2)}) + w^{(1)} x^{(1)} + w^{(2)} x^{(2)}} = \\ 2^{- 2 n} \sum_{x^{(2)} \in G F^{n} (2)} (- 1)^{β l^{(k)} (x^{(2)}) + w^{(2)} x^{(2)}} \sum_{x^{(1)} \in G F^{n} (2)} (- 1)^{(π (x^{(2)}) + w^{(1)}) x^{(1)}} = 2^{- 2 n} (- 1)^{β l^{(k)} (x_{w^{(1)}}^{(2)} + w^{(2)} x_{w^{(1)}}^{(2)}}, \end{array}$

则α_{(w⁽¹⁾, w⁽²⁾)}=l^(k) (x⁽²⁾_w⁽¹⁾) = (l₁ (x⁽²⁾_w⁽¹⁾) , l₂ (x⁽²⁾_w⁽¹⁾) , …, l_k (x⁽²⁾_w⁽¹⁾) , 而b_{(w⁽¹⁾, w⁽²⁾)}=w⁽²⁾x⁽²⁾_w⁽¹⁾, 其中π (x⁽²⁾_w⁽¹⁾) =w⁽¹⁾, 所以对任意的β∈GF^k (2) , S_{(f+βh^(k)₁)} (w⁽¹⁾, w⁽²⁾) 满足定理4的条件1, 因此ψ_k (x, y) 是2n+r元Bent函数。

下面考察了在一定的限制条件下, ψ_k (x, y) 的自相关特征:

定理6 设ψ_k (x, y) =f (x) +g (y) + $\sum_{i = 1}^{k} h_{1 i} (x) h_{2 i} (y) ‚$ $\sum_{i = 1}^{k} h_{1 i} (x) h_{2 i} (y) ‚$ h $_{1}^{(k)}$ $_{1}^{(k)}$ (x) 和h $_{2}^{(k)}$ $_{2}^{(k)}$ (y) 如定理2中所定义, 若对任意的α, β∈GF^k (2) , f (x) +βh^(k)₁ (x) 都是满足l₁次扩散准则的n元布尔函数, g (y) +αh^(k)₂ (y) 都是满足l₂次扩散准则的r元布尔函数, 则对任意的s₁∈GFⁿ (2) , s₂∈GF^r (2) , 且W (s₁) ≤l₁, W (s₂) ≤l₂, ψ_k (x, y) 的自相关函数满足:

1) r_{ψ_k} (s₁, 0) =0;

2) r_{ψ_k} (0, s₂) =0;

证明对任意的s₁∈GFⁿ (2) , W (s₁) ≤l₁, 由X和Y的相互独立性知

$\begin{array}{l} Ρ {ψ_{k} (X + s, Y) + ψ_{k} (X, Y) = 0} = \\ Ρ {f (X + s_{1}) + \sum_{i = 1}^{k} h_{1 i} (X + s_{1}) h_{2 i} (Y) + f (x) + \\ \sum_{i = 1}^{k} h_{1 i} (X) h_{2 i} (Y) = 0} = \\ \sum_{β \in G F^{k} (2)} Ρ {h_{2}^{(k)} (Y) = β, f (X + s_{1}) + f (x) + \\ β (h_{1}^{(k)} (X + s_{1}) + h_{1}^{(k)} (X)) = 0} = \\ \sum_{β \in G F^{k} (2)} Ρ {h_{2}^{(k)} (Y) = β} Ρ {f (X + s_{1}) + \\ β h_{1}^{(k)} (X + s_{1}) + f (X) + β h_{1}^{(k)} (X) = 0}, \end{array}$ $\begin{array}{l} Ρ {ψ_{k} (X + s, Y) + ψ_{k} (X, Y) = 0} = \\ Ρ {f (X + s_{1}) + \sum_{i = 1}^{k} h_{1 i} (X + s_{1}) h_{2 i} (Y) + f (x) + \\ \sum_{i = 1}^{k} h_{1 i} (X) h_{2 i} (Y) = 0} = \\ \sum_{β \in G F^{k} (2)} Ρ {h_{2}^{(k)} (Y) = β, f (X + s_{1}) + f (x) + \\ β (h_{1}^{(k)} (X + s_{1}) + h_{1}^{(k)} (X)) = 0} = \\ \sum_{β \in G F^{k} (2)} Ρ {h_{2}^{(k)} (Y) = β} Ρ {f (X + s_{1}) + \\ β h_{1}^{(k)} (X + s_{1}) + f (X) + β h_{1}^{(k)} (X) = 0}, \end{array}$

由于对β∈GF^k (2) , f (x) +βh $_{1}^{(k)}$ $_{1}^{(k)}$ (x) 都是满足l₁次扩散准则, 即

$\begin{array}{l} Ρ {f (X + s_{1}) + β h_{1}^{(k)} (X + s_{1}) + \\ f (X) + β h_{1}^{(k)} (X) = 0} = 1 / 2 ‚ \end{array}$ $\begin{array}{l} Ρ {f (X + s_{1}) + β h_{1}^{(k)} (X + s_{1}) + \\ f (X) + β h_{1}^{(k)} (X) = 0} = 1 / 2 ‚ \end{array}$

所以

$\begin{array}{l} Ρ {ψ_{k} (X + s, Y) + ψ_{k} (X, Y) = 0} = \\ \frac{1}{2} \sum_{β \in G F^{k} (2)} Ρ {h_{2}^{(k)} (Y) = β} = \frac{1}{2} ‚ \end{array}$ $\begin{array}{l} Ρ {ψ_{k} (X + s, Y) + ψ_{k} (X, Y) = 0} = \\ \frac{1}{2} \sum_{β \in G F^{k} (2)} Ρ {h_{2}^{(k)} (Y) = β} = \frac{1}{2} ‚ \end{array}$

即r_{ψ_k} (s₁, 0) =0。对任意的s₂∈GF^r (2) , 由对称性同样可证r_{ψ_k} (0, s₂) =0。

在实际应用中, 平衡且满足严格雪崩准则的函数有很大的应用价值, 同时满足严格雪崩的布尔函数和H函数是等价的, 它是阵列编码中的一个重要的函数类。因此, 构造平衡且满足严格雪崩准则的布尔函数具有重要意义, 而下面的定理表明利用上面的谱分解式可以递归构造平衡的满足严格雪崩的布尔函数。

定理7 设ψ_k (x, y) =f (x) +g (y) + $\sum_{i = 1}^{k} h_{1 i} (x) h_{2 i} (y) ‚$ $\sum_{i = 1}^{k} h_{1 i} (x) h_{2 i} (y) ‚$ h $_{1}^{(k)}$ $_{1}^{(k)}$ (x) 和h $_{2}^{(k)}$ $_{2}^{(k)}$ (y) 如定理2中所定义, 若对任意的α, β∈GF^k (2) , f (x) +βh^(k)₁ (x) 都是平衡且满足严格雪崩准则的n元布尔函数, g (y) +αh $_{2}^{(k)}$ $_{2}^{(k)}$ (y) 都是满足严格雪崩准则的r元布尔布尔函数, 则ψ_k (x, y) 是n+r元平衡且满足严格雪崩准则的布尔函数。

证明平衡性由式 (2) 可证, 而满足严格雪崩准则由定理6可知。

注: 在上面的定理中, 并不要求g (y) +αh^(k)₂ (y) 是平衡的布尔函数。

例1 设f (x) =x₀ (x₁x₂+x₃) +x₁x₄+

x₂x₅+ (x₀+x₁+x₂+1) x₆, x∈GF⁷ (2) ;

h₁₁ (x) = (x₀+x₁) x₃+x₀ (x₁+x₁x₂+x₄) +

(x₁+1) x₅+x₂x₆+x₂, x∈GF⁷ (2) ;

h₁₂ (x) = (x₀+x₁+x₂) x₃+ (1+x₀+x₂) x₄+

x₀x₅+x₁x₆, x∈GF⁷ (2) ;

g (y) =y₀ (y₁y₂+y₃) +y₁y₄+y₂y₅+ (y₀+

y₁+y₂+1) y₆, y∈GF⁷ (2) ;

h₂₁ (y) = (y₀+y₁) y₃+y₀ (y₁+y₁y₂+y₄) +

(y₁+1) y₅+y₂y₆+y₂, y∈GF⁷ (2) ;

h₂₂ (y) = (y₀+y₁+y₂) y₃+ (1+y₀+y₂) y₄+

y₀y₅+y₁y₆, y∈GF⁷ (2) 。

则可以验证f (x) , h₁₁ (x) , h₁₂ (x) , g (y) , h₂₁ (y) , h₂₂ (y) 满足定理7的条件, 所以函数ψ₂ (x, y) =f (x) +g (y) +h₁₁ (x) h₂₁ (y) +h₁₂ (x) 是平衡的满足严格雪崩准则的14元布尔函数。

《5 结语》

5 结语

给出了结构形式更为一般的一类布尔函数Walsh谱的分解式, 并利用这种谱分解式给出了在密码设计中有重要应用的弹性函数和Bent函数的一些新的递归构造方法, 还利用这种谱分解式和概率的方法考察了一类特殊布尔函数的自相关特征等, 构造了平衡且满足严格雪崩准则的一类布尔函数。而且利用所提的方法也可以给出多输出Bent函数 ^[11]的递归构造等。

展示更多