剩余哈希引理

形式陈述 ​

设 $X$ 是有限集合 $\mathcal{X}$ 上的随机变量，满足最小熵公理库最小熵Min-entropy · Rényi min-entropy由最可能结果的概率定义、直接刻画单次最优猜测成功率的信息量。 $H_{\mathrm{\infty }}(X)\ge k$。令 $\mathcal{H}$ 是从 $\mathcal{X}$ 到 $\{0,1{\}}^{\ell }$ 的二通用函数族：对任意 $x\ne x^{\prime }$，均匀采样 $H\leftarrow \mathcal{H}$ 时都有

$$\text{Pr}[H(x)=H(x^{\prime })]\le 2^{-\ell }.$$

要求 $H$ 与 $X$ 独立。剩余哈希引理在本库带 $1/2$ 的总变差距离公理库总变差距离Total variation distance · TV distance两个概率分布对最优可测事件所赋概率之差的最大值。规范下断言

$$\mathrm{\Delta }((H,H(X)),(H,U_{\ell }))\le \frac{1}{2}\sqrt{2^{\ell -k}}.$$

联合分布把哈希函数描述 $H$ 一并交给观察者，因而这是强有种子提取器公理库有种子随机性提取器Seeded randomness extractor · Seeded extractor用独立均匀短种子把任意高最小熵弱源映为统计上接近均匀的输出。结论：seed 可以公开，输出仍接近独立均匀串。结论是信息论的，允许观察者计算无界；误差来自源熵、输出长度和随机函数选择，而不是某个计算困难假设。

常数可直接从公式换算。若目标距离至多 $\epsilon$，取

$$\ell \le k-2{\log }_2\frac{1}{2\epsilon }=k-2{\log }_2\frac{1}{\epsilon }+2$$

即可让右侧不超过 $\epsilon$。常见的更整洁参数 $\ell \le k-2{\log }_2(1/\epsilon )$ 会得到更强的 $\epsilon /2$ 上界，当然也蕴含距离至多 $\epsilon$。文献若使用不带 $1/2$ 的 $L_1$ 规范，常数会相应改变；引用时必须同时核对距离定义。

证明从碰撞概率出发。记 $M=2^{\ell }$，对固定 $h$ 令 $p_h(y)=\text{Pr}[h(X)=y]$。Cauchy–Schwarz 给出

$$\mathrm{\Delta }(h(X),U_{\ell })\le \frac{1}{2}\sqrt{M(\sum _y{p}_h(y{)}^2-\frac{1}{M})}.$$

对 $H$ 取平均并使用平方根的凹性，联合分布的距离至多

$$\frac{1}{2}\sqrt{M({\mathbb{E}}_H\sum _y{p}_H(y{)}^2-\frac{1}{M})}.$$

取独立同分布副本 $X^{\prime }$，中间的碰撞项就是 $\text{Pr}[H(X)=H(X^{\prime })]$。当 $X=X^{\prime }$ 时必然碰撞；当 $X\ne X^{\prime }$ 时，二通用性把概率控制在 $1/M$。于是括号经整理至多为 $\mathrm{Col}(X)=\sum _x\text{Pr}[X=x{]}^2$，而

$$\mathrm{Col}(X)\le \underset{x}{max}\text{Pr}[X=x]\sum _x\text{Pr}[X=x]\le 2^{-k}.$$

代回即得 $\frac{1}{2}\sqrt{M{2}^{-k}}$。这里用碰撞概率作为证明桥梁，却最终只假设 min-entropy；不能把结论误写成输入必须恰有某个 collision entropy。

直觉 ​

弱源可能把概率质量不规则地堆在许多点上。随机选择二通用哈希，相当于随机把这些点分到 $2^{\ell }$ 个桶；任意两点一同落桶的概率受控，因此没有哪个输出桶能在平均意义上吸收过多质量。压缩留下足够熵余量后，桶质量接近均匀。

哈希函数本身可以公开，因为随机性只负责在看到源之前选定分桶方式。引理比较的是 $(H,H(X))$ 与 $(H,U_{\ell })$，不是把 seed 藏起来后的边缘分布；这正是它能用于隐私放大和公开随机种子的原因。

例子与边界 ​

令 $X$ 在 ${\mathbb{F}}_2^n$ 的某个 $k$ 维仿射子空间上均匀，因此 $H_{\mathrm{\infty }}(X)=k$。从所有线性映射 $h_A(x)=Ax$ 中均匀选择一个 $\ell \times n$ 二进制矩阵 $A$；对任意 $x\ne x^{\prime }$，$A(x-x^{\prime })=0$ 的概率为 $2^{-\ell }$，所以该族二通用。引理说明，即使公开 $A$，只要输出长度比 $k$ 留出足够余量，$AX$ 仍与均匀 $\ell$ bit 串统计接近。少数在源子空间上降秩的矩阵正是误差来源，而不是被定义悄悄排除。

当 $\ell =k$ 时，通用上界只有 $1/2$，不能支持很小的统计误差；当 $\ell >k$ 时界更差。某些特殊源和函数当然可能输出更多均匀 bit，但对所有 min-entropy 至少 $k$ 的源作统一保证时，不能忽略 entropy loss。

普通密码哈希的抗碰撞性不等于二通用性。抗碰撞要求已知函数后，PPT 攻击者难以找到一对碰撞输入；二通用性要求随机函数种子下，每一对预先固定的不同输入以至多 $2^{-\ell }$ 的概率碰撞。一个固定 SHA 实例没有这里的随机族量词，不能仅凭“密码学安全”获得 LHL 的信息论结论。

种子相关性也会破坏引理。如果先观察 $X$ 再选择一个让该值落入特殊桶的 $H$，二通用族的边缘抽样看似正确，联合分布却不再是独立的 $H\leftarrow \mathcal{H}$。重复使用同一 $H$ 处理相关源时，则要证明每个源相对已有输出仍保有足够条件最小熵，并累计各次距离。

带旁信息的剩余哈希引理使用条件或平滑最小熵；量子旁信息版本把总变差替换为相应 trace distance，并需要单独证明。本页公式只覆盖无旁信息的经典离散源，不能直接把 $k$ 换成未经说明的条件熵数值。

推论与应用 ​

剩余哈希引理把通用哈希公理库通用哈希Universal hashing · Universal hash family从函数族随机选择哈希函数，使任意预先固定的不同键对以至多 1/m 的概率碰撞。从数据结构中的碰撞控制工具连接到随机性提取。它给出构造简单、seed 可公开的强提取器，并把输出长度、min-entropy 与统计误差写成可直接用于协议参数的关系。

隐私放大、密钥派生、模糊提取器与泄漏后随机性恢复都使用这一桥梁。落地时仍需证明输入相对攻击者视图的熵下界、独立生成并认证 seed、无歧义编码哈希域，并按调用次数累计误差；普通哈希 API 或经验随机性测试不能替代这些条件。

参考资料

• Russell Impagliazzo, Leonid A. Levin, and Michael Luby, “Pseudo-Random Generation from One-Way Functions,” STOC 1989，leftover-hash technique。
• Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby, “A Pseudorandom Generator from any One-way Function,” SIAM Journal on Computing 28(4), 1999。
• Yevgeniy Dodis, Leonid Reyzin, and Adam Smith, “Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data,” EUROCRYPT 2004。
• Salil P. Vadhan, Pseudorandomness, Foundations and Trends in Theoretical Computer Science 7(1–3), 2012，extractors and the leftover hash lemma。