有种子随机性提取器

弱源的随机性像一团位置未知的墨：总量不少，却可能集中在任意坐标和相关结构中。种子不是把 $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)$ 相称的余量时，剩余哈希引理理路剩余哈希引理Leftover hash lemma · LHL二通用哈希把弱随机源压缩为公开种子和经典旁信息后仍接近均匀的输出，误差由平均条件最小熵控制；条件化与 Jensen 不等式给出证明，三比特例子精确算出联合距离。保证 $(S,h_S(X))$ 接近 $(S,U_m)$。对经典旁信息 $Z$，该构造还满足以平均条件最小熵控制的强提取界，前提是种子独立于整个 $(X,Z)$。关键性质是函数族对不同输入的碰撞受控，不是现实哈希的抗碰撞安全口号。

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

强提取器允许公开一次种子，但不自动允许在任意相关输入上无限复用同一 $S$。多次输出会形成联合分布，前一次输出、源之间的相关性和累计误差都可能泄露结构。即使新源相对既有 transcript 仍有足够条件最小熵，旧种子也可能与它们相关，因此还要单独证明所需的复用性质。若每一步改用独立于当前源及既有记录的新种子，则可以在适用的条件提取定理下另行累计距离。

输出长度的边界要区分是否公开种子。普通提取器 $\mathrm{Ext}(x,s)=s$ 对任意源都输出均匀的 $d$ 位，误差为零，即使 $d>k$；它只是花掉了种子随机性。把种子一起公开时，联合分布变为 $(S,S)$，与 $(S,U_d)$ 的距离为 $1-2^{-d}$，所以它不是小误差强提取器。

一个直接的计数边界是：取整数 $0\le k\le n$，让源在 $2^k$ 个点上均匀。普通输出的支撑至多有 $2^{k+d}$ 个点，因而与 $U_m$ 的距离至少为 $max\{0,1-2^{k+d-m}\}$。强版本中，固定每个种子后输出支撑至多有 $2^k$ 个点；对公开种子平均，联合距离至少为 $max\{0,1-2^{k-m}\}$。后一个界说明 $m>k$ 时不可能得到很小的强提取误差，却不表示 $m=k$ 总有误差：当 $k=n$ 时，唯一的 $n$ bit 源就是均匀源，$\mathrm{Ext}(x,s)=x$ 以 $m=n$ 给出零误差强提取。

一般参数下的最优种子长度和熵损失还需更精细的构造与下界。普通哈希不会仅因摘要“看起来杂乱”就成为 extractor；仍必须给出对所有 $k$-source 的定理、种子分布和明确误差。

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

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