扩散特性
严格雪崩特性和扩散特性用于衡量S盒的输入改变量和输出改变量之间的随机性，是S盒设计的重要指标之一。
布尔函数的扩散准则
定义:设\(f(x): F_{2}^{n} → F_{2}\)，如果\(f(x⊕\alpha)⊕f(x)\)是一个平衡函数，称\(f(x)\)关于非零向量\(\alpha \in F_{2}^{n}\)满足扩散准则。
如果对所有的向量\(\alpha \in F_{2}^{n}: 1≤W_H(\alpha)<k，f(x)\)满足扩散准则，称\(f(x)\)满足k次扩散准则。
S盒的扩散准则
定义2 如果S盒的各分量函数\(f_i\)关于\(\alpha\)满足扩散准则，称n×m代换盒\(S=(f_{1},⋯,f_m)\)关于元素\(\alpha \in GF(2)^{n}\)满足扩散准则。进一步，如果F关于所有\(\alpha \in GF(2)^{n}，1≤W_H(\alpha)<k\)均满足扩散准则，则称S满足k次扩散准则。
雪崩特性
雪崩效应
雪崩效应是扩散性的一个具体表现，描述输入发生微小变化时输出发生巨大变化的现象，就像山坡上的小雪球引发大规模雪崩一样。理想情况下：
- 改变1个输入比特 → 平均改变50%的输出比特
- 这种变化应该是不可预测的、随机的
定义:\(S=(f_{1},⋯,f_m): F_{2}^{n} → F_{2}^{m}\)满足雪崩效应，是指改变输入的1比特，大约有一半输出比特改变。
若对任意\(e \in GF(2)^{n}，W_H(e)=1\)，有：
\(∑(S(x)⊕S(x⊕e)) = (∑(f_{1}(x)⊕f_{1}(x⊕e)),⋯,∑(f_m(x)⊕f_m(x⊕e))) = (2^{n-1},⋯,2^{n-1})\)
均成立，则称S盒满足严格雪崩准则(SAC)
例1
例：函数\(f(x_{1},x_{2},x_{3})=x_{1}x_{2}+x_{3}\)不满足严格雪崩准则，因为：
- \(f(x_{1}+1,x_{2},x_{3})+f(x_{1},x_{2},x_{3})=x_{2}\) 平衡
- \(f(x_{1},x_{2}+1,x_{3})+f(x_{1},x_{2},x_{3})=x_{1}\) 平衡
- 但\(f(x_{1},x_{2},x_{3}+1)+f(x_{1},x_{2},x_{3})=1\) 不平衡
例2
检测函数\(f(x_{1},x_{2},x_{3})=x_{1}x_{2}+x_{2}x_{3}+x_{1}x_{3}\)是否满足严格雪崩准则
检查当改变输入的每个比特时，输出是否满足严格雪崩准则(SAC)
- 改变\(x_{1}\)：
\(f(x_{1}+1,x_{2},x_{3})+f(x_{1},x_{2},x_{3}) = (x_{1}+1)x_{2}+x_{2}x_{3}+(x_{1}+1)x_{3} + (x_{1}x_{2}+x_{2}x_{3}+x_{1}x_{3}) = x_{1}x_{2}+x_{2}+x_{2}x_{3}+x_{1}x_{3}+x_{3} + x_{1}x_{2}+x_{2}x_{3}+x_{1}x_{3} = x_{2}+x_{3}\) (不恒为1，因此不平衡) - 改变\(x_{2}\)：
\(f(x_{1},x_{2}+1,x_{3})+f(x_{1},x_{2},x_{3}) = x_{1}(x_{2}+1)+x_{2}x_{3}+x_{3} + (x_{1}x_{2}+x_{2}x_{3}+x_{1}x_{3}) = x_{1}x_{2}+x_{1}+x_{2}x_{3}+x_{3} + x_{1}x_{2}+x_{2}x_{3}+x_{1}x_{3} = x_{1}+x_{3}\) (不恒为1，因此不平衡) - 改变\(x_{3}\)：
\(f(x_{1},x_{2},x_{3}+1)+f(x_{1},x_{2},x_{3}) = x_{1}x_{2}+(x_{2}+1)(x_{3}+1)+x_{1}(x_{3}+1) + (x_{1}x_{2}+x_{2}x_{3}+x_{1}x_{3}) = x_{1}x_{2}+x_{2}x_{3}+x_{2}+x_{3}+1+x_{1}x_{3}+x_{1} + x_{1}x_{2}+x_{2}x_{3}+x_{1}x_{3} = x_{2}+x_{3}+x_{1}+1\) (不恒为1，因此不平衡)
由于改变任意一个输入比特时，输出都不满足严格雪崩准则(SAC)，因此函数\(f(x_{1},x_{2},x_{3})=x_{1}x_{2}+x_{2}x_{3}+x_{1}x_{3}\)不满足严格雪崩准则
测试严格雪崩准则的计算复杂度为O(n·2^{n})，其中n是输入比特数。这是因为需要：
- 对于每个输入比特(共n个)，需要测试改变该比特的情况
- 对于每种情况，需要遍历所有可能的输入(共2^{n}种)
- 对于每种输入组合，计算输出并验证是否满足SAC条件