小偏分布与线性测试

单独看每一位都均匀，只检查了 $n$ 个方向。小偏分布检查的是全部 $2^n-1$ 个非零奇偶方向，包括涉及所有坐标的全局关系。

要求这么多线性检查都过关，仍不等于整个分布接近均匀：一种分布可以具有很小的支持集，却把质量安排得让每个奇偶方向都近似平衡。观察者若使用非线性方法识别这个支持集，仍可轻易区分它。

图取 $P(t)=t+t^2$：在 ${\mathbb{F}}_4$ 中仅 $0,1$ 为根，因此条件字符期望一半为1、一半为0。

所有短边缘均匀仍可能有一个全局漏洞 ​

在所有满足 $x_1\oplus \cdots \oplus x_n=0$ 的串上均匀取样。任意少于 $n$ 个坐标的联合分布都是均匀的：先指定这些坐标，剩余坐标中至少有一位可以唯一补足总奇偶，其余任取。

但取 $a=(1,\dots ,1)$，总有 ${\chi }_a(X)=1$，偏差达到一。因此高度独立的局部边缘也不能替代全部线性测试的小偏条件。

一个可实际生成的小偏分布 ​

选有限域公理库有限域Finite field · Galois field底层集合有限的域。 ${\mathbb{F}}_q$，其中 $q=2^r$。固定一组 ${\mathbb{F}}_2$ 基，把每个域元素 $z$ 写成 $r$ 位向量 $\mathrm{vec}(z)$。独立均匀选 $A\in {\mathbb{F}}_q$ 和 $B\in \{0,1{\}}^r$，输出 $n$ 位

其中 $A^0$ 是恒为一的常数单项式，包括 $A=0$ 时。种子只有 $2r$ 位。

在给定域的表示及上述基后，从 $1$ 开始逐次乘以 $A$，生成这些幂至多需要 $n-1$ 次域乘法，再做 $n$ 次 $r$ 位内积；内积部分共需 $O(nr)$ 位运算。流式输出时，保存 $A,B$ 和当前幂共需 $O(r)$ 位，循环计数另需 $O(\log (n+1))$ 位；若保留整个输出，还需 $n$ 位。构造有限域表示的成本，以及域乘法实现的时间和工作空间，均另行计入。

对任意非零系数串 $c=(c_0,\dots ,c_{n-1})$，令

这是一个非零多项式，次数至多 $n-1$。输出的对应奇偶为

固定 $A$。若 $P_c(A)\ne 0$，向量 $\mathrm{vec}(P_c(A))$ 非零，与均匀 $B$ 的内积恰好一半为零、一半为一，所以字符期望为零。若 $P_c(A)=0$，内积恒零，字符期望为一。因此

最后一步只用非零域上多项式的根数不超过次数。给定 $0<\epsilon \le 1$，选二的幂 $q\ge max\{2,(n-1)/\epsilon \}$，即可得到所需小偏，种长为 $O(1+\log n+\log \left(1/\epsilon \right))$。式 (2) 在 $q$ 太小时可能只给一个大于一的无用界，并非所有参数都带来伸长。

四元素域上的验算 ​

取 ${\mathbb{F}}_4={\mathbb{F}}_2[\alpha ]/({\alpha }^2+\alpha +1)$，基为 $(1,\alpha )$，输出三位。若 $A=\alpha$、$B=(1,0)$，则 $1,A,A^2$ 的第一坐标依次为 $1,0,1$，输出 $101$。

对字符 $c=(0,1,1)$，多项式为 $P_c(t)=t+t^2$。它在四元素域中恰有根 $0,1$，所以该奇偶字符期望为 $2/4=1/2$，达到式 (2) 的上界。这个例子需四个种子位才产生三个输出位，只用来检查代数。

较大参数会真正节省随机性。例如 $n=64$、目标 $\epsilon =0.1$，取 $q=1024$，种长 $20$ 位，偏差上界 $63/1024<0.1$，输出则有 $64$ 位。

用 $u_i=(-1{)}^{x_i}$ 将 $0/1$ 坐标换成 $\pm 1$，本页的 ${\chi }_a$ 就是Fourier–Walsh 展开公理库Fourier–Walsh 展开与影响度Fourier-Walsh expansion · Boolean Fourier analysis在均匀布尔立方体上用字符正交基展开函数，把方差和坐标影响写成 Fourier 系数的平方和。中指标集 $S=\{i:a_i=1\}$ 的字符。该正交基展开适用于立方体上的任意实值函数 $h$，因此

所以小偏分布还能骗过 Fourier 一范数受控的测试；若右侧系数总和很大，结论就很弱。不能从“所有线性测试都通过”直接跳到“所有布尔测试都通过”。

式 (1) 的支持至多有 $q^2$ 个点。在 $64$ 位例中，总变差距离公理库总变差距离Total variation distance · TV distance两个概率分布对最优可测事件所赋概率之差的最大值。甚至至少为 $1-2^{20}/2^{64}=1-2^{-44}$：事件“落在生成器支持集”在输出分布中概率一，在均匀分布中极小。若 $\epsilon$ 为逆多项式，枚举全部 $q^2$ 个种子本身就是多项式工作，给出一种高效的非线性区分方法。

因此小偏空间适合需要奇偶或受控 Fourier 测试的去随机化与校验。密码学长串安全则需要面对任意允许的高效区分器，必须使用不同的假设和证明。