布尔函数的自相关系数与相关性免疫

### 布尔函数的自相关系数与相关性免疫性解读 #### 1. 引言 在密码学领域，布尔函数有着广泛的应用。基于线性反馈移位寄存器（LFSR）的流密码会将布尔函数用作非线性组合器或非线性滤波器，而分组密码则在替换盒中使用布尔函数。为了抵抗各种攻击，用于密码学的布尔函数必须具备特定的属性。 在LFSR流密码中，相关性免疫性是布尔函数的一个重要属性，它由Siegenthaler引入。此外，非线性性、代数次数等也是重要属性。对于分组密码使用的布尔函数，非线性性和基于自相关系数的差分（或自相关）特性（如传播度、雪崩准则、绝对指标等）尤为关键，而且近年来的研究表明，差分特性对于流密码也很重要。 相关性免疫性（或弹性）不仅在流密码中重要，在其他场景中也有重要意义。如果我们希望已知某些输入位不会提供关于输出位的（统计）信息，那么具有相关性免疫性的函数就很有用。虽然许多研究表明相关性免疫性和自相关特性存在强烈的矛盾，但自相关系数仍然是研究相关性免疫性和其他属性的有力工具。 #### 2. 预备概念和定义 - **向量空间与布尔函数**：考虑 $F_2^n$，即由 $F_2$ 元素组成的 $n$ 元组向量空间。一个 $n$ 变量的布尔函数是从 $F_2^n$ 到 $F_2$ 的映射。向量 $x$ 的权重是 $x$ 中 1 的个数，记为 $|x|$。若对于每个 $i = 1, 2, \ldots, n$ 都有 $x_i \leq y_i$，则称向量 $x$ 先于向量 $y$，记为 $x \preceq y$。向量 $x$ 和 $u$ 的标量积定义为 $\langle x, u \rangle = \sum_{i = 1}^{n} x_i u_i$。 - **函数的权重与平衡性**：函数 $f$ 在 $F_2^n$ 上的权重 $wt(f)$ 是使得 $f(x) = 1$ 的向量 $x$ 的个数。若 $wt(f) = wt(f \oplus 1) = 2^{n - 1}$，则称函数 $f$ 是平衡的。布尔函数 $f$ 的子函数 $f'$ 是通过将 $f$ 中的某些变量替换为常量得到的。 - **代数表示**：一个在 $F_2^n$ 上的函数 $f$ 可以唯一地表示为一个 $F_2$ 上的多项式，其中每个变量在每一项中的次数最多为 1，即 $f(x_1, \ldots, x_n) = \sum_{(a_1, \ldots, a_n) \in F_2^n} g(a_1, \ldots, a_n) x_1^{a_1} \ldots x_n^{a_n}$，这称为函数的代数范式（ANF），每一项 $x_1^{a_1} \ldots x_n^{a_n}$ 称为 ANF 中的一个项。函数 $f$ 的代数次数 $deg(f)$ 定义为 $f$ 中最长项的变量个数，变量 $x_i$ 在 $f$ 中的代数次数 $deg(f, x_i)$ 是包含 $x_i$ 的最长项的变量个数。若 $deg(f, x_i) = 1$，则称 $f$ 线性依赖于 $x_i$；若 $deg(f, x_i) \neq 1$，则称 $f$ 非线性依赖于 $x_i$。长度为 1 的项称为线性项。若 $deg(f) \leq 1$，则称 $f$ 为仿射函数；若 $f$ 是仿射函数且 $f(0) = 0$，则称 $f$ 为线性函数。 - **二次函数**：若函数 $f$ 中每个变量的代数次数都是 2，即对于每个 $i = 1, 2, \ldots, n$ 都有 $deg(f, x_i) = 2$，则称布尔函数 $f$ 为二次函数。 - **汉明距离与非线性性**：两个向量 $x_1$ 和 $x_2$ 之间的汉明距离 $d(x_1, x_2)$ 是它们不同分量的个数。对于两个在 $F_2^n$ 上的布尔函数 $f_1$ 和 $f_2$，它们之间的距离定义为 $d(f_1, f_2) = \#\{x \in F_2^n | f_1(x) \neq f_2(x)\}$，且 $d(f_1, f_2) = wt(f_1 \oplus f_2)$。$f$ 与所有仿射函数集合之间的最小距离称为 $f$ 的非线性性，记为 $nl(f)$。 - **沃尔什变换**：布尔函数 $f$ 的沃尔什变换是一个在 $F_2^n$ 上的整数值函数，定义为 $W_f(u) = \sum_{x \in F_2^n} (-1)^{f(x) + \langle u, x \rangle}$。沃尔什系数满足帕塞瓦尔方程 $\sum_{u \in F_2^n} W_f^2(u) = 2^{2n}$。 - **相关性免疫性与弹性**：一个在 $F_2^n$ 上的布尔函数 $f$ 若其输出和任意 $m$ 个输入变量统计独立，则称 $f$ 为 $m$ 阶相关性免疫函数。等价的非概率性表述是，对于 $f$ 的任意 $n - m$ 变量子函数 $f'$，有 $wt(f') = wt(f) / 2^m$。一个平衡的 $m$ 阶相关性免疫函数称为 $m$ - 弹性函数，即对于 $f$ 的任意 $n - m$ 变量子函数 $f'$，有 $wt(f') = 2^{n - m - 1}$。相关性免疫函数可以通过沃尔什系数来刻画： - 定理 1：一个在 $F_2^n$ 上的布尔函数 $f$ 是 $m$ 阶相关性免疫的，当且仅当对于所有满足 $1 \leq |u| \leq m$ 的向量 $u \in F_2^n$，有 $W_f(u) = 0$。 - 定理 2：若 $f$ 是 $F_2^n$ 上的 $m$ 阶相关性免疫函数，且 $m \leq n - 1$，则 $W_f(u) \equiv 0 \pmod{2^{m + 1}}$。若 $f$ 是 $m$ - 弹性函数，且 $m \leq n - 2$，则 $W_f(u) \equiv 0 \pmod{2^{m + 2}}$。 - **自相关系数与绝对指标**：对于一个在 $F_2^n$ 上的布尔函数 $f$，其在向量 $u$ 处的自相关系数定义为 $\Delta_f(u) = \sum_{x \in F_2^n} (-1)^{f(x) + f(x + u)}$。绝对指标定义为 $\Delta_f = \max_{x \in F_2^n \setminus \{0\}} |\Delta_f(x)|$。 #### 3. 弹性函数绝对指标的新下界 首先建立一个重要的技术公式： - 定理 3：$\Delta_f(u) = -2^n + 2^{1 - n} \sum_{x \in F_2^n, \langle x, u \rangle \equiv 0 \pmod{2}} W_f^2(x)$。 然后给出弹性函数绝对指标的下界： - 引理 2：设 $f$ 是 $F_2^n$ 上的 $m$ - 弹性布尔函数，则 $\Delta_f \geq \frac{2m - n + 2}{n} 2^n$。 - 证明：构造矩阵 $B$，将每个二进制向量 $u \in F_2^n$ 以 $W_f^2(u)$ 次写入 $B$ 的行中。根据帕塞瓦尔方程，矩阵 $B$ 包含 $2^{2n}$ 行。由 Xiao Guo - Zhen–Massey 谱特征可知，矩阵 $B$ 的每一行最多包含 $n - m - 1$ 个零。因此，$B$ 中零的总数最多为 $(n - m - 1)2^{2n}$。所以，存在某一列 $i$，其中零的个数最多为 $\frac{(n - m - 1)2^{2n}}{n}$。根据构造可知 $\sum_{x \in F_2^n, x_i = 0} W_f^2(x) \leq \frac{(n - m - 1)2^{2n}}{n}$。再由定理 3 可得 $\Delta_f(e_i) = -2^n + 2^{1 - n} \sum_{x \in F_2^n, x_i = 0} W_f^2(x) \leq -2^n + \frac{n - m - 1}{n} 2^{n + 1} \leq \frac{n - 2m - 2}{n} 2^n$，从而 $\Delta_f \geq \frac{2m - n + 2}{n} 2^n$。 - 定理 4：设 $f$ 是 $F_2^n$ 上的 $m$ - 弹性布尔函数，则 $\Delta_f \geq \frac{2m - n + 3}{n + 1} 2^n$。 - 证明：假设在引理 2 的证明中，矩阵 $B$ 包含 $h2^{2n}$ 行，其中零的个数少于 $n - m - 1$。重复引理 2 的证明过程，可得 $\Delta_f \geq \frac{2m - n + 2 + 2h}{n} 2^n$。同时，$\Delta_f(1 \ldots 1) = -2^n + 2^{1 - n} \sum_{x \in F_2^n, |x| \equiv 0 \pmod{2}} W_f^2(x)$，且 $\Delta_f \geq |\Delta_f(1 \ldots 1)| \geq (1 - 2h)2^n$。当 $h = \frac{n - m - 1}{n + 1}$ 时，上述两个不等式的右边相等，因此 $\Delta_f \geq \frac{2m - n + 3}{n + 1} 2^n$。 这个结果在 $m > (n - 3) / 2$ 时显著改进了之前的结果。 #### 4. 高阶弹性函数非线性变量数量的上界 - 引理 3：设 $f$ 是 $F_2^n$ 上的布尔函数，且 $deg(f) \geq 1$，则 $2^{n - deg(f)} \leq wt(f) \leq 2^n - 2^{n - deg(f)}$。 - 引理 4：设 $f$ 是 $F_2^n$ 上的布尔函数，且 $deg(f) \geq 1$，则 $deg(f(x) \oplus f(x + e_i)) \leq deg(f(x)) - 1$。 - 引理 5：设 $f$ 是 $F_2^n$ 上的布尔函数，且 $deg(f, x_i) \geq 2$，则 $\sum_{u \in F_2^n, u_i = 0} W_f^2