剩余哈希引理 | Codeboy's Blog

形式陈述

无旁信息的基本界

设 $X$ 是有限集合 $\mathcal X$ 上的随机变量，满足最小熵 $H_\infty(X)\ge k$ 。令 $\mathcal H$ 是一个从 $\mathcal X$ 到 $\{0,1\}^\ell$ 的非空有限二通用函数族：对任意 $x\ne x'$ ，均匀采样 $H\leftarrow\mathcal H$ 时都有

\Pr[H(x)=H(x')]\le2^{-\ell}.

要求 $H$ 与 $X$ 独立。剩余哈希引理在本库带 $1/2$ 的总变差距离规范下断言

\Delta\bigl((H,H(X)),(H,U_\ell)\bigr) \le\frac12\sqrt{2^{\ell-k}}.

联合分布把哈希函数描述 $H$ 一并交给观察者，因而这是公开种子后仍成立的强提取性质：seed 可以公开，输出仍接近独立均匀串。一般有限键域和有限随机函数描述给出这一性质的相应版本；当键域为 $\{0,1\}^n$ ，且哈希函数由均匀 $d$ 位串索引时，才直接得到有种子提取器页所定义的二进制固定种子长度形式。结论是信息论的，允许观察者计算无界；误差来自源熵、输出长度和随机函数选择，而不是某个计算困难假设。

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

\ell\le k-2\log_2\frac1{2\varepsilon} =k-2\log_2\frac1\varepsilon+2

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

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

\Delta(h(X),U_\ell) \le\frac12 \sqrt{M\left(\sum_y p_h(y)^2-\frac1M\right)}.

对 $H$ 取平均并对凹函数平方根使用Jensen 不等式，联合分布的距离至多

\frac12\sqrt{ M\left( \mathbb E_H\sum_y p_H(y)^2-\frac1M \right)}.

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

\operatorname{Col}(X) \le\max_x\Pr[X=x]\sum_x\Pr[X=x] \le2^{-k}.

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

输出不必是比特串

同一证明适用于任意非空有限输出集 $\mathcal Y$ ，记 $M=|\mathcal Y|\ge1$ 。具体地， $X$ 仍在有限输入集上且 $H_\infty(X)\ge k$ ； $H$ 从非空有限函数族中均匀抽取，独立于 $X$ ，并满足对每对 $x\ne x'$ ，

\Pr[H(x)=H(x')]\le1/M.

令 $U_{\mathcal Y}$ 独立均匀取值于 $\mathcal Y$ ，则在同一带 $1/2$ 的总变差规范下，

\Delta((H,H(X)),(H,U_{\mathcal Y})) \le\frac12\sqrt{M\,2^{-k}}.

上面的碰撞概率与 Cauchy–Schwarz 推导只用到输出点数 $M$ ，没有使用其二进制表示。 $M=1$ 时两世界实际完全相同。取 $\mathcal Y=\mathbb Z_q^{n+1}$ 、 $X=U(\{0,1\}^m)$ ，就得到 $\frac12\sqrt{q^{n+1}/2^m}$ ；这并不要求 $q$ 或 $M$ 是二的幂。若要称为固定二进制输出长度的提取器，仍须回到 $\mathcal Y=\{0,1\}^\ell$ 的原接口。

公开经典旁信息后的界

现在允许观察者还知道一个有限经典变量 $Z$ ，它可以与 $X$ 任意相关。记

q_z=\max_x\Pr[X=x\mid Z=z],\qquad \widetilde H_\infty(X\mid Z) =-\log_2\sum_z\Pr[Z=z]q_z.

求和只取正概率的 $z$ 。这是平均条件最小熵：先对每个已知 $z$ 选择最佳猜测，再平均成功率，最后取负对数。它不是条件最小熵数值本身的平均。

要求种子 $H$ 独立于整个联合变量 $(X,Z)$ ，并仍从同一二通用族均匀选取。若 $\widetilde H_\infty(X\mid Z)\ge k$ ，则

\boxed{\Delta\bigl((H,Z,H(X)),(H,Z,U_\ell)\bigr) \le\frac12\sqrt{2^{\ell-k}}.}

理想世界中的 $U_\ell$ 独立于 $(H,Z)$ ；两世界保留完全相同的种子与旁信息边缘。结论因此保证输出与它们联合接近独立均匀，而不只保证丢掉旁信息后的边缘分布均匀。无旁信息版本是 $Z$ 为常量的特例。

这是联合分布的平均保证。若改用更强的最坏条件熵下界 $\min_z H_\infty(X\mid Z=z)\ge k$ ，相同的距离界会对每个正概率 $z$ 单独成立；平均条件熵下界允许某些少见的 $z$ 泄漏更多。条件版的完整证明见“推论与应用”。

直觉

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

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

旁信息把原来的源分成许多条件分布。某个条件下可能只剩一个确定值，另一些条件下仍有许多可能值。条件版逐份计算可预测程度，再按这些条件出现的概率合并，因而能同时记录泄漏严重程度与发生频率。

例子与边界

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

当 $\ell=k$ 时，通用上界只有 $1/2$ ，不能支持很小的统计误差；当 $\ell>k$ 时界更差。对这里恰在 $2^k$ 个点上均匀的源，固定任一种子后输出支撑至多有 $2^k$ 个点；若 $\ell>k$ ，公开种子的联合距离至少为 $1-2^{k-\ell}$ 。若 $k$ 只是一个较弱下界而实际源熵更大，特殊源可能允许更多输出，但这不能替代对所有 $k$ -source 的统一保证。

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

种子相关性也会破坏引理。如果先观察 $X$ 再选择一个让该值落入特殊桶的 $H$ ，二通用族的边缘抽样看似正确，联合分布却不再是独立的 $H\leftarrow\mathcal H$ 。重复使用同一 $H$ 时，已有输出通常已与它相关；仅给出新源相对旧记录的条件熵下界，不能恢复本定理要求的种子独立性。复用需要单独的组合证明。

三个公平 bit，泄漏一个零值标志

取 $X$ 在八个三比特串上均匀，公开 $Z=\mathbf1[X=000]$ 。这个标志不告诉观察者所有输入，却会在恰好抽中零串时暴露完整输入：

标志	出现概率	条件下的源	最佳猜测成功率	条件最小熵
$Z=1$	$1/8$	确定的 $000$	$1$	$0$
$Z=0$	$7/8$	七个非零串上均匀	$1/7$	$\log_2 7$

最坏条件最小熵是零，平均猜测概率却是

\frac18\cdot1+\frac78\cdot\frac17=\frac14, \qquad \widetilde H_\infty(X\mid Z)=2.

若错误地平均表中最右列，就会得到 $\frac78\log_2 7\approx2.45644$ ，与正确的 $2$ 不同。由平均条件最小熵控制的，是攻击者看到标志后实际能够达到的平均猜测率。

独立选均匀三比特种子 $A$ ，令 $h_A(x)=A\cdot x\pmod2$ ，输出一 bit。零种子也在函数族中。对任意非零差值 $v$ ，取一个 $v$ 为一的坐标，翻转种子的这个坐标就会翻转 $A\cdot v$ ；八个种子因而恰有四个使其为零，证明二通用性。

固定 $Z=0$ 后，逐个种子的输出计数为：

种子	七个非零输入中的输出 $0,1$ 计数	与公平 bit 的距离
$A=000$	$(7,0)$	$1/2$
任一非零 $A$	$(3,4)$	$1/14$

非零线性泛函在全部八个输入上各取四次零和一；去掉的 $000$ 总输出零，因此剩下 $(3,4)$ 。记 $X_0$ 为七个非零串上的均匀变量，独立于种子。公开种子后必须按种子平均距离，不能先把输出概率混在一起：

d_0=\Delta((A,h_A(X_0)),(A,U_1)) =\frac18\left(\frac12+7\cdot\frac1{14}\right)=\frac18.

当 $Z=1$ 时，所有种子的输出都为零，故 $d_1=1/2$ 。再按标志概率合并，得到完整联合距离

\boxed{\Delta((A,Z,h_A(X)),(A,Z,U_1)) =\frac78\cdot\frac18+\frac18\cdot\frac12 =\frac{11}{64}.}

引理的通用上界为 $\frac12\sqrt{2^{1-2}}=1/(2\sqrt2)\approx0.353553$ ，实际距离是 $0.171875$ 。上界无需知道每个哈希函数在条件源上的全部计数，因此不必与此小例的精确值相等。

对任何非零种子， $h_A(X)$ 的无条件边缘都是公平 bit；可是在 $Z=1$ 的条件下它一定为零。这个对照说明，边缘均匀不保证与公开记录独立，联合距离不能省略 $Z$ 。

推论与应用

条件化之后，为什么还能用平均最小熵

对每个正概率 $z$ ，写 $X_z\sim(X\mid Z=z)$ ，令 $C_z=\sum_x\Pr[X_z=x]^2$ 。种子与 $(X,Z)$ 独立，保证条件于 $z$ 后它仍按原分布选择，并独立于 $X_z$ ，所以基本版证明可以逐个条件使用。

还可保留碰撞计算中稍强的一步。若 $M=2^\ell$ ，两份条件独立样本相同的概率为 $C_z$ ，不同时哈希碰撞至多 $1/M$ ，故

\mathbb E_H\sum_y\Pr[H(X_z)=y\mid H]^2 \le C_z+\frac{1-C_z}{M} =\frac1M+\left(1-\frac1M\right)C_z.

代入 Cauchy–Schwarz 与平方根凹性，得到

d_z:=\Delta((H,H(X_z)),(H,U_\ell)) \le\frac12\sqrt{(M-1)C_z} \le\frac12\sqrt{M q_z},

最后用 $C_z\le q_z$ 。现在两世界有同一个 $Z$ 边缘，在总变差绝对值求和中可把共同的非负权重 $P_Z(z)$ 提出来，得到等式

\Delta((H,Z,H(X)),(H,Z,U_\ell))=\sum_zP_Z(z)d_z.

于是再次使用平方根的凹性：

\begin{aligned} \sum_zP_Z(z)d_z &\le\frac12\sqrt M\sum_zP_Z(z)\sqrt{q_z}\\ &\le\frac12\sqrt{M\sum_zP_Z(z)q_z}\\ &=\frac12\sqrt{2^{\ell-\widetilde H_\infty(X\mid Z)}}. \end{aligned}

这完成了经典条件版证明。先平均猜测率再取负对数，正好与最后一行匹配；平均条件熵数值不具有这个代入形式。若保留较强碰撞项，同样的论证给出 $\frac12\sqrt{(M-1)\mathbb E_Z C_Z}$ ；三比特例中 $\mathbb E_Z C_Z=1/4$ ，这个界为 $1/4$ ，仍高于精确值 $11/64$ 。

从误差预算反算输出长度

假设一个应用已经证明源相对全部公开记录的平均条件最小熵至少为 $256$ bit，且新种子满足独立性。要让公开种子后的距离至多 $2^{-40}$ ，可选

\ell\le256-2\log_2\frac1{2\cdot2^{-40}}=178.

代回可见 $\frac12\sqrt{2^{178-256}}=2^{-40}$ 。这用的是泄漏后的熵下界，而不是原始输入长度；源有 $256$ 个存储 bit 并不能代替这项假设。

证明中的 $Z$ 是可条件化为普通概率分布的经典记录。量子旁信息不能用这份逐标签求和处理，需要量子条件最小熵及迹距离版本的独立定理。平滑版本也必须指定平滑距离和附加误差预算；本页的两个公式不含这项放宽。

剩余哈希引理把通用哈希从数据结构中的碰撞控制工具连接到随机性提取。它给出构造简单、seed 可公开的强提取器，并把输出长度、min-entropy 与统计误差写成可直接用于协议参数的关系。

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

终点自测：解释零标志例子中 $0$ 、 $2$ 与 $\frac78\log_2 7$ 分别是什么，枚举八个种子对应的两类输出计数，再算出 $11/64$ 。最后指出条件证明中哪一步使用种子与整个 $(X,Z)$ 独立。

参考资料

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, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith, “Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data”, SIAM Journal on Computing 38(1), 2008, pp. 97–139；作者稿日期 2008-01-20，§2.3–2.5，稿内 pp. 8–11。Lemma 2.1 为基本 LHL；平均最小熵定义在 §2.4；Lemma 2.4 及其证明给出经典旁信息下的强提取界。该四作者版本不同于三作者的 EUROCRYPT 2004 初稿。
Salil P. Vadhan, Pseudorandomness, Foundations and Trends in Theoretical Computer Science 7(1–3), 2012，extractors and the leftover hash lemma。

形式陈述 ​

无旁信息的基本界 ​

输出不必是比特串 ​

公开经典旁信息后的界 ​

三个公平 bit，泄漏一个零值标志 ​

条件化之后，为什么还能用平均最小熵 ​

从误差预算反算输出长度 ​

反向链接