有种子随机性提取器

形式陈述 ​

一个有种子随机性提取器是确定性函数

$$\mathrm{Ext}:\{0,1{\}}^n\times \{0,1{\}}^d⟶\{0,1{\}}^m.$$

若对每个满足 $H_{\mathrm{\infty }}(X)\ge k$ 的 $n$ bit 随机变量 $X$，以及与 $X$ 独立的均匀种子 $S\leftarrow U_d$，都有

$$\mathrm{\Delta }(\mathrm{Ext}(X,S),U_m)\le \epsilon ,$$

则称 $\mathrm{Ext}$ 是 $(k,\epsilon )$ seeded extractor。这里的距离采用带 $1/2$ 的总变差距离公理库总变差距离Total variation distance · TV distance两个概率分布对最优可测事件所赋概率之差的最大值。约定，结论覆盖计算无界观察者；它不是“通过若干随机性测试”的经验性质。最关键的量词是对所有最小熵至少为 $k$ 的源成立，而不是只对设计者预先挑选的噪声模型成立。

若进一步满足

$$\mathrm{\Delta }((S,\mathrm{Ext}(X,S)),(S,U_m))\le \epsilon ,$$

则称为强提取器。强性质意味着种子可以与输出一起公开，观察者知道究竟选了哪种提取方式后，输出仍接近独立均匀串。普通提取器只保证丢掉种子后的边缘输出接近均匀，不能自动把 $S$ 暴露给后续协议。

参数 $d$ 是 seed length，$m$ 是 output length，$k-m$ 常称 entropy loss，$\epsilon$ 是统计误差。对一族提取器，这些量可随输入长度或安全参数变化；若要得到统计密码安全，通常要求 $\epsilon$ 可忽略。输出不可能无代价地超过源所含的可预测熵，构造的目标是在短种子和小误差下让 $m$ 尽量接近 $k$。

独立均匀种子不是附带便利，而是定义的资源。对一般弱源，确定性净化不可能：例如任何输出一 bit 的确定函数都有一个大小至少 $2^{n-1}$ 的同值纤维，取在该纤维上均匀的源便有至少 $n-1$ bit 最小熵，输出却恒定。随机种子让提取器从一族观察方式中抽取一个，避免同一个坏源同时落入每种方式的坏纤维。

直觉 ​

弱源的随机性像一团位置未知的墨：总量不少，却可能集中在任意坐标和相关结构中。种子不是把 $d$ 个随机 bit “扩张”为 $m$ bit，而是随机选择一副滤镜，把源中已有但分布不整齐的随机性摊平到输出。因为选择可以公开，强提取器尤其适合作为协议中的随机性净化器。

这也解释了提取器与伪随机生成器公理库伪随机生成器Pseudorandom generator · PRG把短均匀种子扩展为计算上不可与均匀串区分的长输出。的方向相反。PRG 从短而完全均匀的秘密种子出发，输出更长但只对高效观察者像随机；提取器读取较长的弱源和额外短种子，输出通常更短，却对无界观察者都统计接近真正均匀。

例子与边界 ​

二通用哈希族给出强提取器的核心实例。把种子 $S$ 解释为随机哈希函数 $h_S:\{0,1{\}}^n\to \{0,1{\}}^m$ 的描述，并令 $\mathrm{Ext}(x,S)=h_S(x)$。当 $X$ 具有至少 $k$ bit 最小熵且 $m$ 比 $k$ 留出与 $\log \left(1/\epsilon \right)$ 相称的余量时，剩余哈希引理保证 $(S,h_S(X))$ 接近 $(S,U_m)$。关键性质是函数族对不同输入的碰撞受控，不是现实哈希的抗碰撞安全口号。

种子若与源相关，保证可能完全消失。设有人先看到 $X$，再专门选择使 $\mathrm{Ext}(X,S)=0^m$ 的种子；即使每个边缘分布看似有随机性，联合分布也违反独立条件。类似地，从同一物理噪声中同时导出 $X$ 和 $S$，不能只检查两者各自近似均匀，而应证明联合独立或使用适合相关种子的另一类提取模型。

强提取器允许公开一次种子，但不自动允许在任意相关输入上无限复用同一 $S$。多次输出会形成联合分布，前一次输出、源之间的相关性和累计误差都可能泄露结构。若各源具有相对既有 transcript 的足够条件最小熵，可用混合或链式论证证明复用；没有这项条件时，单次定义不能替代组合分析。

输出长度同样有边界。把 $m$ 设得接近或超过 $k$ 会迫使统计误差变大；把一个普通哈希函数应用到弱源，也不会仅因摘要“看起来杂乱”就成为 extractor。必须给出对所有 $k$-source 的定理、种子分布和明确的 $\epsilon$ 界。

推论与应用 ​

有种子提取器用于隐私放大、设备随机数净化、密码密钥生成、去随机化和复杂性理论。强提取器可以把公开种子与接近均匀的输出一同交给后续算法；总变差的数据处理性质保证任何后处理把真实输出换成均匀输出时，事件概率最多改变 $\epsilon$。

提取安全落地时还需把熵估计与协议接口接起来：声明 $X$ 相对攻击者旁信息的条件最小熵，确保种子独立并认证相关上下文，选取满足目标输出长度与误差的构造，再累计所有调用的统计损失。少任何一环，“使用了 extractor”都不足以推出最终密钥安全。

参考资料

• Noam Nisan and David Zuckerman, “Randomness is Linear in Space,” Journal of Computer and System Sciences 52(1), 1996，seeded extractors。
• Luca Trevisan, “Extractors and Pseudorandom Generators,” Journal of the ACM 48(4), 2001。
• Salil P. Vadhan, Pseudorandomness, Foundations and Trends in Theoretical Computer Science 7(1–3), 2012，Chs. 3–6。