The Strict Avalanche Criterion of Order k Spectral Properties of m-Valued Logical Functions

Abstract

Many cryptographic properties of m - valued logical functions are often described by their Chrestenson cyclic spectrums and auto-correlation functions, so Chrestenson cyclic spectrums and autocorrelation functions play important roles in properties and construct ions for m-valued logical functions. In this paper, in residue class ring Z_m, the concept of the strict avalanche criterion of order k of m-valued logical functions is presented. Then, by applying probabilistic thought and methods, the rule that a w-valued logical function fulfills the SAC of lower order if it fulfills the SAC of higher order is proved. Finally, by Chrestenson cyclic spectrums, a necessary and sufficient condition on a m-valued logical function is given, which fulfills the strict avalanche criterion of order k.

Content

在诸多密码攻击方法中有一种差分方法, 是以输入的改变导致输出有相对较大改变为基础的一种攻击方法, 针对此种攻击, Webster和Tavares定义了布尔函数的严格雪崩准则 (SAC) 的概念:如果一个函数满足严格雪崩准则, 那么当输入只有1 b改变时, 输出改变的概率将是1/2 ^[1], 故以这样的布尔函数为非线性组合器产生的密钥流能够抗针对输入只改变1 b时的差分攻击。基于此, 人们对满足严格雪崩准则的布尔函数的性质和构造等进行了一系列研究 ^[2,3,4,5], 文献[2]得到了布尔函数满足严格雪崩准则的谱判别条件。

然而在选择性明文攻击中, 密码破译者们又可以通过固定某些输入比特为常值后再作差分攻击, 为此, Forre'对布尔函数的严格雪崩准则概念进行了拓展, 给出了布尔函数满足k阶严格雪崩准则的定义, 并得到了布尔函数满足k阶严格雪崩准则的谱判别条件 ^[2]。以上工作对密码的设计者和分析者无疑都是有意义的。

依据实际应用的需要, 近年来人们在密码学中对多值逻辑函数的有关性质和构造给予了更多的关注, 将布尔函数的许多研究成果都拓广到了多值逻辑函数中, 也特别给出了多值逻辑函数的严格雪崩准则的概念 ^[6], 有不少成果问世 (参见文献[6,7]) 。但是, 多值逻辑函数满足高阶严格雪崩准则的定义迄今尚未见到。笔者给出了剩余类环Z_m上逻辑函数满足k阶严格雪崩准则的定义, 证明了m值逻辑函数满足高阶严格雪崩准则时一定满足低阶严格雪崩准则, 考虑到谱在逻辑函数密码学性质研究中所发挥的作用, 肖国镇、冯登国教授等在这方面做了很出色的工作 ^[6], 笔者还利用反演公式得到了谱的一个分解公式, 据此给出了m值逻辑函数满足k阶严格雪崩准则的一个谱判别条件, 将文献[2]中的结果推广到了一般的m值逻辑函数。为记号简便, 只就k=1的情况给出m值逻辑函数满足k阶严格雪崩准则的主要结论的证明。

《1 基本概念和预备知识》

1 基本概念和预备知识

以下m≥2是任一取定的正整数, 且以Z_m记整数模m的剩余类环, 又对任一取定的正整数n, 以Z $_{m}^{n}$ $_{m}^{n}$ 表示n个Z_m的笛卡尔积。当w= (w₁, w₂, …, w_n) ∈Zⁿ_m时, 称w的不为0元的分量个数为其汉明重量, 且记为W (w) 。

定义1 ^[7]Z $_{m}^{n}$ $_{m}^{n}$ →Z_m的任一映射f都为Z $_{m}^{n}$ $_{m}^{n}$ 上的n个变元的m值逻辑函数, 即若x= (x₁, x₂, …, x_n) ∈Z $_{m}^{n}$ $_{m}^{n}$ , 则f (x) =f (x₁, x₂, …, x_n) ∈Z_m。

定义2 ^[7] 设x= (x₁, x₂, …, x_n) ∈Z $_{m}^{n}$ $_{m}^{n}$ , w= (w₁, w₂, …, w_n) ∈Z $_{m}^{n}$ $_{m}^{n}$ , 则x和w的点积定义为w·x=w₁x₁+w₂x₂+…+w_nx_n (mod m) , 则n元m值逻辑函数f (x) , x∈Z $_{m}^{n}$ $_{m}^{n}$ 的第二种Chrestenson变换定义为

$S_{(f)} (w) = \frac{1}{m^{n}} \sum_{x \in Ζ_{m}^{n}} u^{f (x) - w \ 5 x}, w \in Ζ_{m}^{n} ‚$ $S_{(f)} (w) = \frac{1}{m^{n}} \sum_{x \in Ζ_{m}^{n}} u^{f (x) - w \ 5 x}, w \in Ζ_{m}^{n} ‚$

称S_(f) (w) , w∈Z $_{m}^{n}$ $_{m}^{n}$ 为f (x) 的Chrestenson循环谱。

定义3 ^[6] 设f (x) , x∈Z $_{m}^{n}$ $_{m}^{n}$ 是m值逻辑函数, 对x= (x₁, x₂, …, x_n) ∈Z $_{m}^{n}$ $_{m}^{n}$ , s= (s₁, s₂, …, s_n) ∈Z $_{m}^{n}$ $_{m}^{n}$ 记x+s= (x₁+s₁, x₂+s₂, …, x_n+s_n) , 称

$r_{f} (s) = \frac{1}{m^{n}} \sum_{x \in Ζ_{m}^{n}} u^{f (x + s) - f (x)}$ $r_{f} (s) = \frac{1}{m^{n}} \sum_{x \in Ζ_{m}^{n}} u^{f (x + s) - f (x)}$

为f (x) 的自相关函数。

定义4 ^[7] 称m值逻辑函数f (x) , x∈Z $_{m}^{n}$ $_{m}^{n}$ 是满足严格雪崩准则的, 若f (x) 的自相关函数r_f满足r_f (s) =0, s∈Z $_{m}^{n}$ $_{m}^{n}$ , W (s) =1。

定义5 设n≥2, 1≤k<n, 称n元m值逻辑函数f (x₁, x₂, …, x_n) 是满足k阶严格雪崩准则的, 如果取定f (x₁, x₂, …, x_n) 的n个变元x₁, x₂, …, x_n中的任意k个后, 所得n-k元的m值逻辑函数都是满足严格雪崩准则的。

下设X= (X₁, X₂, …, X_n) 中的X₁, X₂, …, X_n是定义在同一概率空间 (Ω, F, P) 上相互独立且都具有均匀分布的m值随机变量, 即对任意的 (a₁, a₂, …, a_n) ∈Zⁿ_m, 都有

$\begin{array}{l} Ρ {X_{1} = a_{1}, X_{2} = a_{2}, \dots, X_{n} = a_{n}} = \\ Ρ {X_{1} = a_{1}} \cdot Ρ {X_{2} = a_{2}} \cdot \dots \cdot Ρ {X_{n} = a_{n}}, \end{array}$ $\begin{array}{l} Ρ {X_{1} = a_{1}, X_{2} = a_{2}, \dots, X_{n} = a_{n}} = \\ Ρ {X_{1} = a_{1}} \cdot Ρ {X_{2} = a_{2}} \cdot \dots \cdot Ρ {X_{n} = a_{n}}, \end{array}$

和P{X_i=a} =1/m, a∈Z_m , 1≤i≤n, 则易知对任一m值逻辑函数f (x₁, …, x_n) , f (X₁, …, X_n) 也为 (Ω, F, P) 上的m值随机变量。

在上述记号的意义下, 关于m值逻辑函数的自相关函数的概率表示式已有下面的结果:

定理1 ^[7] 对任一m值逻辑函数f (x) , x∈Z $_{m}^{n}$ $_{m}^{n}$ , 都有

$\begin{array}{l} r_{f} (s) = \sum_{r \in Ζ_{m}} u^{r} Ρ {f (X + s) - f (X) = r}, \\ s \in Ζ_{m}^{n} 。 \end{array}$ $\begin{array}{l} r_{f} (s) = \sum_{r \in Ζ_{m}} u^{r} Ρ {f (X + s) - f (X) = r}, \\ s \in Ζ_{m}^{n} 。 \end{array}$

定理2 ^[8] (反演公式) 对任一m值逻辑函数f (x) 与其Chrestenson循环谱的关系为

$u^{f (x)} = \sum_{w \in Ζ_{m}^{n}} S_{(f)} (w) \ 5 u^{w \ 5 x}, x \in Ζ_{m}^{n} 。$ $u^{f (x)} = \sum_{w \in Ζ_{m}^{n}} S_{(f)} (w) \ 5 u^{w \ 5 x}, x \in Ζ_{m}^{n} 。$

关于m值逻辑函数满足严格雪崩准则的Chrestenson谱判别条件, 又已有下面的结果:

定理3 ^[7]m值逻辑函数f (x) , x∈Z $_{m}^{n}$ $_{m}^{n}$ 满足严格雪崩准则的充分必要条件是对所有的1≤j≤n , 只要s_j∈Z_m0}, 就都成立

$\sum_{w \in Ζ_{m}^{n}} | S_{(f)} (w) |^{2} \ 5 u^{w_{j} \ 5 s_{j}} = 0 。$ $\sum_{w \in Ζ_{m}^{n}} | S_{(f)} (w) |^{2} \ 5 u^{w_{j} \ 5 s_{j}} = 0 。$

《2 主要结果》

2 主要结果

定理4 如果m值逻辑函数f (x) , x∈Z $_{m}^{n}$ $_{m}^{n}$ 满足k阶严格雪崩准则, 那么f (x) 必定满足k-1阶严格雪崩准则 (0阶严格雪崩准则即原来意义下的严格雪崩准则) 。

证明为记号简单, 只给出满足1阶严格雪崩准则必定满足严格雪崩准则的证明。

设m值逻辑函数f (x₁, x₂, …, x_n) 满足1阶严格雪崩准则, 根据定义知, 此时对任意的1≤i≤n和a∈Z_m, n-1元m值逻辑函数

$f_{i : a} (x (i)) = f (x_{1}, \dots, x_{i - 1}, a, x_{i + 1}, \dots, x_{n})$ $f_{i : a} (x (i)) = f (x_{1}, \dots, x_{i - 1}, a, x_{i + 1}, \dots, x_{n})$

都要满足严格雪崩准则, 再根据定理1, 即知对任意的a∈Z_m和

$\begin{array}{l} s^{*} = (s_{1}, \dots, s_{i - 1}, s_{i + 1}, \dots, s_{n}) \in Ζ_{m}^{n - 1} \\ 且 W (s^{*}) = 1 ‚ \\ r_{f i : a} (s_{1}, \dots, s_{i - 1}, s_{i + 1}, \dots, s_{n}) = \\ \sum_{r \in Ζ_{m}} u^{r} Ρ {f (X_{1} + s_{1}, \dots, X_{i - 1} + s_{i - 1}, \\ a, X_{i + 1} + s_{i + 1}, \dots, X_{n} + s_{n}) - f (X_{1}, \dots, \\ X_{i - 1}, a, X_{i + 1}, \dots, X_{n} + s_{n}) = r} = 0 \end{array}$ $\begin{array}{l} s^{*} = (s_{1}, \dots, s_{i - 1}, s_{i + 1}, \dots, s_{n}) \in Ζ_{m}^{n - 1} \\ 且 W (s^{*}) = 1 ‚ \\ r_{f i : a} (s_{1}, \dots, s_{i - 1}, s_{i + 1}, \dots, s_{n}) = \\ \sum_{r \in Ζ_{m}} u^{r} Ρ {f (X_{1} + s_{1}, \dots, X_{i - 1} + s_{i - 1}, \\ a, X_{i + 1} + s_{i + 1}, \dots, X_{n} + s_{n}) - f (X_{1}, \dots, \\ X_{i - 1}, a, X_{i + 1}, \dots, X_{n} + s_{n}) = r} = 0 \end{array}$

都成立。

今设s= (s₁, …, s_n) ∈Z $_{m}^{n}$ $_{m}^{n}$ 且W (s) =1, 即s中仅有一个分量不为0, 不妨设

$s_{1} \neq 0, 即 s = (s_{1}, 0, \dots, 0),$ $s_{1} \neq 0, 即 s = (s_{1}, 0, \dots, 0),$

于是有

$\begin{array}{l} r_{f} (s_{1}, 0, \dots, 0) = \\ \sum_{r \in Ζ_{m}} u^{r} Ρ {f (X_{1} + s_{1}, X_{2}, X_{3}, \dots, X_{n}) - \\ f (X_{1}, X_{2}, X_{3}, \dots, X_{n}) = r} = \\ \sum_{r \in Ζ_{m}} \sum_{a \in Ζ_{m}} u^{r} Ρ {f (X_{1} + s_{1}, a, X_{3}, \dots, X_{n}) - \\ f (X_{1}, a, X_{3}, \dots, X_{n}) = r, X_{2} = a} = 0 \\ \sum_{r \in Ζ_{m}} \sum_{a \in Ζ_{m}} u^{r} Ρ {f (X_{1} + s_{1}, a, X_{3}, \dots, X_{n}) - \\ f (X_{1}, a, X_{3}, \dots, X_{n}) = r} Ρ {X_{2} = a} = \\ \frac{1}{m} \sum_{r \in Ζ_{m}} [\sum_{a \in Ζ_{m}} u^{r} Ρ {f (X_{1} + s_{1}, a, X_{3}, \dots, X_{n}) - \\ f (X_{1}, a, X_{3}, \dots, X_{n}) = r}] = 0 ‚ \end{array}$ $\begin{array}{l} r_{f} (s_{1}, 0, \dots, 0) = \\ \sum_{r \in Ζ_{m}} u^{r} Ρ {f (X_{1} + s_{1}, X_{2}, X_{3}, \dots, X_{n}) - \\ f (X_{1}, X_{2}, X_{3}, \dots, X_{n}) = r} = \\ \sum_{r \in Ζ_{m}} \sum_{a \in Ζ_{m}} u^{r} Ρ {f (X_{1} + s_{1}, a, X_{3}, \dots, X_{n}) - \\ f (X_{1}, a, X_{3}, \dots, X_{n}) = r, X_{2} = a} = 0 \\ \sum_{r \in Ζ_{m}} \sum_{a \in Ζ_{m}} u^{r} Ρ {f (X_{1} + s_{1}, a, X_{3}, \dots, X_{n}) - \\ f (X_{1}, a, X_{3}, \dots, X_{n}) = r} Ρ {X_{2} = a} = \\ \frac{1}{m} \sum_{r \in Ζ_{m}} [\sum_{a \in Ζ_{m}} u^{r} Ρ {f (X_{1} + s_{1}, a, X_{3}, \dots, X_{n}) - \\ f (X_{1}, a, X_{3}, \dots, X_{n}) = r}] = 0 ‚ \end{array}$

由此即易知f (x) 满足严格雪崩准则。

定理4告知, m值逻辑函数满足k (≥1) 阶严格雪崩准则的一个必要条件是它必须满足通常意义下的严格雪崩准则。

根据m值逻辑函数满足k (≥1) 阶严格雪崩准则的定义不难得到如下引理:

引理1 m值逻辑函数f (x) , x∈Z $_{m}^{n}$ $_{m}^{n}$ 满足k阶严格雪崩准则的充分必要条件是对所有的正整数1≤i≤n和a∈Z_m, 取定x_i=a后所得n-1元函数f (x₁, …, x_i-1, a, x_i+1, …, x_n) 满足k-1阶严格雪崩准则。

注意: 对任意的1≤i≤n, n元m值逻辑函数f (x) , x∈Z $_{m}^{n}$ $_{m}^{n}$ 都可表示为

$\begin{array}{l} f (x_{1}, \dots, x_{i - 1}, x_{i}, x_{i + 1}, \dots, x_{n}) = \\ \sum_{r \in Ζ_{m}} Ι_{{a}} (x_{i}) f_{i : a} (x (i)), (x_{1}, x_{2}, \dots, x_{n}) \in Ζ_{m}^{n}, \end{array}$ $\begin{array}{l} f (x_{1}, \dots, x_{i - 1}, x_{i}, x_{i + 1}, \dots, x_{n}) = \\ \sum_{r \in Ζ_{m}} Ι_{{a}} (x_{i}) f_{i : a} (x (i)), (x_{1}, x_{2}, \dots, x_{n}) \in Ζ_{m}^{n}, \end{array}$

其中

f_i:a (x (i) ) =f (x₁, …, x_i-1, a, x_i+1, …, x_n) ,

$Ι_{{a}} (x_{i}) = {\begin{cases} 1, x_{i} = a ‚ \\ 0, x_{i} \neq a, \end{cases} x_{i} \in Ζ_{m}, a \in Ζ_{m} 。$ $Ι_{{a}} (x_{i}) = {\begin{cases} 1, x_{i} = a ‚ \\ 0, x_{i} \neq a, \end{cases} x_{i} \in Ζ_{m}, a \in Ζ_{m} 。$

又记

$w = (w_{1}, \dots, w_{i - 1}, k, w_{i + 1}, \dots, w_{n}) \in Ζ_{m}^{n}$ $w = (w_{1}, \dots, w_{i - 1}, k, w_{i + 1}, \dots, w_{n}) \in Ζ_{m}^{n}$

为 (k, w (i) ) , 而记

$\begin{array}{l} w (i) = (w_{1}, \dots, w_{i - 1}, w_{i + 1}, \dots, w_{n}), \\ X (i) = (X_{1}, \dots, X_{i - 1}, X_{i + 1}, \dots, X_{n}) 。 \end{array}$ $\begin{array}{l} w (i) = (w_{1}, \dots, w_{i - 1}, w_{i + 1}, \dots, w_{n}), \\ X (i) = (X_{1}, \dots, X_{i - 1}, X_{i + 1}, \dots, X_{n}) 。 \end{array}$

定理5 设f (x₁, …, x_n) 是任一m值逻辑函数, 则对任意的1≤i≤n, 当f表示为

$\begin{array}{l} f (x_{1}, \dots, x_{i - 1}, a, x_{i + 1}, \dots, x_{n}) = \\ \sum_{r \in Ζ_{m}} Ι_{{a}} (x_{i}) f_{i : a} (x (i)) \end{array}$ $\begin{array}{l} f (x_{1}, \dots, x_{i - 1}, a, x_{i + 1}, \dots, x_{n}) = \\ \sum_{r \in Ζ_{m}} Ι_{{a}} (x_{i}) f_{i : a} (x (i)) \end{array}$

时, 就有

$S_{(f_{i : a})} (w (i)) = \sum_{k \in Ζ_{m}} u^{a k} S_{(f)} (k, w (i)), a \in Ζ_{m} (1)$ $S_{(f_{i : a})} (w (i)) = \sum_{k \in Ζ_{m}} u^{a k} S_{(f)} (k, w (i)), a \in Ζ_{m} (1)$

证明根据m值逻辑函数Chrestenson谱定义式和反演公式可知, 对任意取定的a∈Z_m和 (k, w (i) ) ∈Z $_{m}^{n}$ $_{m}^{n}$ 都有

$\begin{array}{l} S_{(f_{i : a})} (w (i)) = \frac{1}{m^{n - 1}} \sum_{x^{″} \in Ζ_{m}^{n - 1}} u^{f_{i : a} (x (i))} u^{- w (i) \ 5 x^{″}} = \\ \frac{1}{m^{n - 1}} \sum_{x^{″} \in Ζ_{m}^{n - 1}} \sum_{k \in z_{m}, v (i) \in Ζ_{m}^{n - 1}} S_{(f) (} k, v (i)) u^{k a + v (i) \ 5 x^{″}} \cdot \\ u^{- w (i) \ 5 x^{″}} = \frac{1}{m^{n - 1}} \sum_{k \in z_{m}, v (i) \in Ζ_{m}^{n - 1}} u^{k a} S_{(f)} (k, v (i)) \cdot \\ \sum_{x^{″} \in Ζ_{m}^{n - 1}} u^{[v (i) - w (i)] x^{″}} = \sum_{k \in Ζ_{m}} u^{k a} S_{(f)} (k, w (i)) 。 \end{array}$ $\begin{array}{l} S_{(f_{i : a})} (w (i)) = \frac{1}{m^{n - 1}} \sum_{x^{″} \in Ζ_{m}^{n - 1}} u^{f_{i : a} (x (i))} u^{- w (i) \ 5 x^{″}} = \\ \frac{1}{m^{n - 1}} \sum_{x^{″} \in Ζ_{m}^{n - 1}} \sum_{k \in z_{m}, v (i) \in Ζ_{m}^{n - 1}} S_{(f) (} k, v (i)) u^{k a + v (i) \ 5 x^{″}} \cdot \\ u^{- w (i) \ 5 x^{″}} = \frac{1}{m^{n - 1}} \sum_{k \in z_{m}, v (i) \in Ζ_{m}^{n - 1}} u^{k a} S_{(f)} (k, v (i)) \cdot \\ \sum_{x^{″} \in Ζ_{m}^{n - 1}} u^{[v (i) - w (i)] x^{″}} = \sum_{k \in Ζ_{m}} u^{k a} S_{(f)} (k, w (i)) 。 \end{array}$

特别在m=2, i=n时, 注意到u=-1, 定理5中的式 (1) 即是布尔函数性质研究中发挥了重要作用的那个著名公式

$\begin{array}{l} S_{f_{i : 1}} (w (n)) = S_{(f)} (0, w (n)) - S_{(f)} (1, w (n)), \\ S_{f_{i : 0}} (w (n)) = S_{(f)} (0, w (n)) + S_{(f)} (1, w (n)) 。 \end{array}$ $\begin{array}{l} S_{f_{i : 1}} (w (n)) = S_{(f)} (0, w (n)) - S_{(f)} (1, w (n)), \\ S_{f_{i : 0}} (w (n)) = S_{(f)} (0, w (n)) + S_{(f)} (1, w (n)) 。 \end{array}$

对任一w= (w₁, …, w_i-1, w_i, w_i+1, …, w_n) ∈Z $_{m}^{n}$ $_{m}^{n}$ 再记

$\begin{array}{l} w_{i_{1}, a_{1}, \dots, i_{k}, a_{k}} = (w_{1}, \dots, w_{i_{1} - 1}, w_{i_{1}} + a_{1}, w_{i_{1} + 1}, \dots, \\ w_{i_{k} - 1}, w_{i_{k}} + a_{k}, w_{i_{k} + 1}, \dots, w_{n}) \in Ζ_{m}^{n} 。 \end{array}$ $\begin{array}{l} w_{i_{1}, a_{1}, \dots, i_{k}, a_{k}} = (w_{1}, \dots, w_{i_{1} - 1}, w_{i_{1}} + a_{1}, w_{i_{1} + 1}, \dots, \\ w_{i_{k} - 1}, w_{i_{k}} + a_{k}, w_{i_{k} + 1}, \dots, w_{n}) \in Ζ_{m}^{n} 。 \end{array}$

根据定理5和引理1, 可以得到m值逻辑函数满足k阶严格雪崩准则的如下谱判别条件:

定理6 m值逻辑函数f (x) , x∈Z $_{m}^{n}$ $_{m}^{n}$ 满足k阶严格雪崩准则的充分必要条件是对所有的1≤i₁<…<i_k≤n, 1≤j≤n且{j}⊂{1, 2, …, n}i₁, …, i_k}, s_j∈Z_m0}和对任意的 (a₁, …, a_k) ∈Z $_{m}^{k}$ $_{m}^{k}$ ,

$\sum_{w \in Ζ_{m}^{n}} [S_{(f)} (w) \bar{S}_{(f)} (w_{i_{1}, a_{1}, \dots, i_{k}, a_{k}})] u^{w_{j} s_{j}} = 0$ $\sum_{w \in Ζ_{m}^{n}} [S_{(f)} (w) \bar{S}_{(f)} (w_{i_{1}, a_{1}, \dots, i_{k}, a_{k}})] u^{w_{j} s_{j}} = 0$

都成立。

特别当k=1时, m值逻辑函数f (x) , x∈Z $_{m}^{n}$ $_{m}^{n}$ 满足1阶严格雪崩准则的充分必要条件是对所有的i, j∈{1, 2, …, n}且i≠ j, s_j∈Z_m0}和对任意的a∈Z_m,

$\sum_{w \in Ζ_{m}^{n}} S_{(f)} (w) \bar{S}_{(f)} (w_{i, a}) u^{w_{j} s_{j}} = 0$ $\sum_{w \in Ζ_{m}^{n}} S_{(f)} (w) \bar{S}_{(f)} (w_{i, a}) u^{w_{j} s_{j}} = 0$

都同时成立。

证明为记号简单, 只就k=1的情况给出m值逻辑函数满足k阶严格雪崩准则的主要证明, 一般结论可再根据引理1由数学归纳法得到。

由定义5和定理3可知, f (x) 满足1阶严格雪崩准则的充分必要条件, 是对所有的i, j∈{1, 2, …, n}且i≠j, s_j∈Z_m0}和对任意的a∈Z_m, 都有

$\sum_{w (i) \in Ζ_{m}^{n - 1}} | S_{(f_{i} : a)} (w (i)) |^{2} u^{w_{j} s_{j}} = 0 。$ $\sum_{w (i) \in Ζ_{m}^{n - 1}} | S_{(f_{i} : a)} (w (i)) |^{2} u^{w_{j} s_{j}} = 0 。$

而根据定理5, 在上述记号的意义下, 对所有的a∈Z_m, 就有

《图1》

则对所有的a∈Z_m, 式 (2) 就是

$\begin{array}{l} \sum_{w (i) \in Ζ_{m}^{n - 1}} | S_{(f_{i : a})} (w (i)) |^{2} u^{w_{j} s_{j}} = \\ S_{0} + u^{a} S_{1} + \dots + u^{a (m - 1)} S_{m - 1} (3) \end{array}$ $\begin{array}{l} \sum_{w (i) \in Ζ_{m}^{n - 1}} | S_{(f_{i : a})} (w (i)) |^{2} u^{w_{j} s_{j}} = \\ S_{0} + u^{a} S_{1} + \dots + u^{a (m - 1)} S_{m - 1} (3) \end{array}$

因而, 若S₀=S₁=…=S_m-1=0, 则由式 (3) 即知对所有的a∈Z_m, 都有

$\sum_{w (i) \in Ζ_{m}^{n - 1}} | S_{(f_{i : a})} (w (i)) |^{2} \ 5 u^{w_{j} s_{j}} = 0 。$ $\sum_{w (i) \in Ζ_{m}^{n - 1}} | S_{(f_{i : a})} (w (i)) |^{2} \ 5 u^{w_{j} s_{j}} = 0 。$

反之, 若对所有的a∈Z_m, 式 (3) 都成立, 则在式 (3) 中取遍a∈Z_m, 就得到关于S₀, S₁, …, S_m-1的方程组

${\begin{cases} S_{0} + S_{1} + \dots + S_{m - 1} = 0, \\ S_{0} + u S_{1} + \dots u^{m - 1} S_{m - 1} = 0, \\ ⋮ \\ S_{0} + u^{m - 1} S_{1} + \dots + u^{(m - 1) (m - 1)} S_{m - 1} = 0, \end{cases}$ ${\begin{cases} S_{0} + S_{1} + \dots + S_{m - 1} = 0, \\ S_{0} + u S_{1} + \dots u^{m - 1} S_{m - 1} = 0, \\ ⋮ \\ S_{0} + u^{m - 1} S_{1} + \dots + u^{(m - 1) (m - 1)} S_{m - 1} = 0, \end{cases}$

解之即得

$S_{0} = S_{1} = \dots = S_{m - 1} = 0 。$ $S_{0} = S_{1} = \dots = S_{m - 1} = 0 。$

特别在m=2时, 注意到u=1及对任意的w∈Z $_{2}^{n}$ $_{2}^{n}$ , S_(f) (w) 都为实数, 定理6中结论为: 布尔函数f (x) , x∈Z $_{2}^{n}$ $_{2}^{n}$ 满足k阶严格雪崩准则的充分必要条件, 是对所有的1≤i₁<…<i_k≤n, 1≤j≤n且{j}⊂{1, 2, …, n}i₁, …, i_k}, s_j∈Z₂0}和对任意的 $(a_{1}, \dots, a_{k}) \in Ζ_{2}^{k}, \sum_{w \in Ζ_{2}^{n}} [S_{(f)} (w) S_{(f)} (w_{i_{1}, a_{1}, \dots, i_{k}, a_{k}})] \ 5 (- 1)^{w_{j}} = 0$ $(a_{1}, \dots, a_{k}) \in Ζ_{2}^{k}, \sum_{w \in Ζ_{2}^{n}} [S_{(f)} (w) S_{(f)} (w_{i_{1}, a_{1}, \dots, i_{k}, a_{k}})] \ 5 (- 1)^{w_{j}} = 0$ 都成立。这是文献[2]中的主要结果。

《3 结语》

3 结语

在剩余类环Z_m上给出了m值逻辑函数的k阶严格雪崩准则 (SAC) 的概念, 并借助Chrestenson谱给出了m值逻辑函数满足k阶严格雪崩准则的一个充分必要条件, 此外, 依据定理6的结论, 还可以给出满足k阶严格雪崩准则的m值逻辑函数的更多的递归构造方法, 用变元个数少的逻辑函数构造变元个数多且满足k阶严格雪崩准则的逻辑函数, 更好地在密码设计中使用逻辑函数的资源, 因而是有实际意义的。

Show More