💻 computer science

Lower Bounds on Black-Box Constructions of Pseudorandom Functions

本文证明了，从伪随机生成器（PRG）构造全黑盒形式的伪随机函数（PRF）时，即使是针对输出为 1 位的弱 PRF，也无法实现 $o(n/\log n)$ 次非自适应调用 PRG，从而为这类构造的效率提供了强下界，并使得实现单次调用构造的可能性成为了一个重大的开放性挑战。

原作者： Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam

发布于 2026-08-17

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

数字锁匠的困境

想象一下，你是一位试图打造一把无敌保险库门的顶级锁匠。在数字安全的世界里，这个“保险库”就是一个伪随机函数 (Pseudorandom Function, PRF)。你可以把 PRF 想象成一台神奇的机器：你输入一个秘密密钥和一个特定的输入（比如房间号），它就会吐出一串看起来对任何观察者来说都完全随机的数字。然而，如果你再次使用同一个秘密密钥，它总是会产生完全相同的“随机”字符串。这种一致性使其在锁定你的电子邮件、保护银行交易和确保密码安全方面发挥着重要作用。

为了制造这台神奇的机器，密码学家通常从一种更简单的工具开始，即伪随机生成器 (Pseudorandom Generator, PRG)。PRG 就像是一个微小且高效的种子，它能长成一片巨大的、看似随机的森林。它将一个简短的秘密字符串拉伸成一个更长的、对于任何计算机程序来说看起来都像随机的字符串。一个重大的问题在于：我们需要使用这个“种子拉伸”机器多少次，才能构建出我们的“保险库门”？

几十年来，标准的配方（被称为 GGM 构造）是使用这个种子拉伸机器，以树状结构重复使用它，大约 $\omega(\log n)$ 次（其中 $n$ 是种子的规模）。它运行得很好，但感觉有点笨重。是否存在捷径？我们能否仅通过使用一次种子拉伸机器就构建出一个完美的保险库门？或者仅仅使用几次？这篇论文深入探讨了这个问题，扮演着一名侦探的角色，试图证明无论你多么聪明，只要你使用的种子拉伸次数太少，你就根本无法构建出一个安全的保险库门。

论文的大发现：“太少”的问题

由 Bar Alon、Itai Dinur 和 Muthuramakrishnan Venkitasubramaniam 撰写的这篇论文，解决了一个基本问题：我们究竟必须调用多少次伪随机生成器 (PRG)，才能构建出一个伪随机函数 (PRF)？

作者证明了，对于一种特定且非常合理的构造类型，答案是“比你预想的要多得多”。具体而言，他们表明，如果你只调用极少数次的 PRG（具体来说，少于大约 $n / \log n$ 次，其中 $n$ 是 PRG 输入的长度），你就无法通过“全黑盒”方法构建出一个安全的 PRF。

为了理解他们的证明，请想象一场“识破伪装”的游戏：

设定： 一个“归约”（构建者）试图利用 PRG 来创建一个 PRF。他们还有一个“对手”（黑客），试图分辨这个 PRF 是真实的还是随机函数。
诡计： 作者设想了一种场景，在这种场景下，构建者是“查询受限”的。这意味着构建者可以请求黑客提供帮助，但请求次数是有限的，不会随着黑客提出的问题数量而爆炸式增长。
反击： 作者构造了一个“真实对手”和一个“理想对手”。
- 理想对手是一个超级强大的、运行缓慢的计算机，它可以检查所有可能的秘密密钥，看看是否符合给定的数据。它可以轻易地分辨出一个函数是 PRF 还是随机函数。
- 真实对手是构建者实际使用的那个。它没有超能力；它只能看到构建者向 PRG 发出的有限次询问。
揭晓： 作者证明，如果构建者调用 PRG 的次数太少，那么“真实对手”就可以完美地模仿“理想对手”，而无需真正破解 PR克的安全性。这创造了一个悖论：如果构建者能用这么少的调用次数构建出安全的 PRF，那么他们也将能够使用一种在实际中过于缓慢的方法来破解 PRG 本身，这与 PRG 是安全的这一假设相矛盾。

主要结果：
论文证明，对于非自适应 (non-adaptive) 构造（即构建者在看到任何答案之前就决定了所有的 PRG 查询），使用少于 $o(n / \log n)$ 次调用来构建 PRF 是不可能的。即使该 PRF 仅输出一个比特（0 或 1），甚至即使黑客被限制在提出简单的随机问题，这一结论依然成立。

“长输出”结果：
作者还研究了产生长字符串数据（而不只是一个比特）的 PRF。他们证明，即使构建者可以是“自适应”的（即一个接一个地提出问题，并根据答案决定下一个问题），仍然存在一个硬性限制。如果 PRG 将输入拉伸的幅度较小，那么你至少需要大约 $out / \log n$ 次调用。如果 PRG 拉伸的幅度较大，则至少需要 $out / r$ 次调用。

这对“单次调用”梦想意味着什么

长期以来，密码学家一直在思考是否可能实现“单次调用”构造——即通过拉伸一次种子来构建一个完美的 PRF。

对于非自适应方法： 这篇论文实际上排除了这种可能性。如果输入规模不断增长，你无法通过常数次调用（比如 1 次、2 次或 10 次）来构建一个安全的 PRF。数学逻辑上并不允许这样做。
对于自适应方法： 论文并没有排除所有自适应场景下的单次调用构造。相反，它表明对于具有长输出的 PRF，调用的次数必须随输出规模而变化。如果输出很大，你不能只靠极少数的固定调用次数就完成一个庞大的保险库门。至于是否存在针对短输出 PRF 的单次调用自适应构造，目前仍是一个开放性问题。

“查询受限”的注意事项

作者非常谨慎地说明了他们的假设。他们专注于一类被称为**“查询受限 (query-bounded)”**的归约。简单来说，这意味着构建者与黑客的交互受到限制，这种限制并不取决于黑客提出了多少个问题。作者认为，历史上几乎所有的密码学构造都符合这一描述。他们承认，如果有人发明了一种奇特的、非标准的构建 PRF 的方法，使得构建者仅仅因为黑客问了一个问题就向黑客询问数百万次，那么他们的证明可能就不适用。但对于所有实际的、标准的密码学设计，他们发现的下界是稳固的。

总结

这篇论文不仅仅是提出了一个限制，它还提供了一个数学证明，证明了构建 PRF 的“捷径”是一条死路。如果你想要一个安全的、黑盒形式的 PRF，你不能跳过步骤。你必须支付足够的调用 PRG 的代价，以确保“熵”（随机性和不可预测性）足够高，从而骗过任何黑客。著名的 GGM 构造使用了大约 $\omega(\log n)$ 次调用，事实证明它几乎是最优的。用“一砖一瓦”去建造一座堡垒的梦想，在这样的语境下，在数学上是不可能的。

技术摘要：黑盒构造伪随机函数的下界

问题陈述

本文探讨了密码学中的一个基本开放问题：通过全黑盒构造（fully black-box construction）构建伪随机函数（PRF）时，至少需要调用多少次伪随机生成器（PRG）？

由 Goldreich, Goldwasser, 和 Micali (GGM) 提出的开创性工作确立了可以通过基于树的方法，利用 PRG 来构造 PRF。当结合 Levin 的领域扩展技术时，该构造需要 $\omega(\log n)$ 次 PRG 调用，其中 $n$ 是 PRG 的输入长度。虽然 Beimel, Malkin, 和 Mazor 最近的工作证明了 GGM 在特定类别的“树状构造”中的最优性，但一般情况仍未解决。具体而言，目前尚不清楚是否可以使用更少的调用次数（甚至仅需一次调用）通过通用的黑盒技术来构建 PRF。

本研究在全黑盒构造的框架下调查这一问题，其中构造过程和安全性归约（security reduction）均为黑盒。作者特别关注被称为**查询有界归约（query-bounded reductions）**的一类归约，即归约与对手之间的交互次数被限制为一个与对手查询复杂度无关的多项式（前提是对手足够成功）。

方法论

作者采用**元归约范式（meta-reduction paradigm）**来建立其下界。这种技术涉及构造一个低效的“真实”对手，该对手可以在不直接访问底层 PRG 的情况下模拟一个“理想”对手（后者会破坏 PRF），从而以少于允许的查询次数破坏 PRG 的安全性。

关键技术组件：

查询有界归约： 作者定义，如果归约对区分对手的查询次数被多项式 $d(n)$ 所限制，且无论对手对其预言机（oracle）进行多少次查询，该归约即为查询有界的。这类归约涵盖了文献中大多数已知的归约，包括 GGM 和 Goldreich-Levin 构造。
理想对手与真实对手：
- 理想对手 ( $A_{ideal}$ ): 一个低效的对手，拥有对 PRG 预言机的指数级访问权限。它试图通过寻找与大量输入-输出对一致的密钥来破坏 PRF。
- 真实对手 ( $A_{real}$ ): 一个低效的对手，它没有访问 PRG 的权限。相反，它接收归约与 PRG 交互过程中生成的查询-回答对。它试图通过估计一个密钥与观测到的输出一致的概率来模拟 $A_{ideal}$ 。
评分函数与独立性：
- 核心挑战在于，如果不同的输入共享 PRG 种子，那么 PRF 在不同输入上的输出可能会存在依赖关系。
- 作者引入了一种程序来识别“频繁种子”（被许多输入使用的种子）并将其输出替换为固定值。这减少了活跃的 PRG 调用次数。
- 对于剩余的输入，他们利用一个组合性断言（Claim 3/6）来表明：要么一组大的输入集合使用相互不相交的 PRG 种子（从而允许通过 Hoeffding 不等式进行独立性论证），要么此类密钥的数量是微不足道的。
- 为了处理理想对手与真实对手之间的统计距离，作者使用了随机阈值（从 $[0.8, 1]$ 中均匀采样）而非固定阈值。这平滑了决策边界，确保只要输入数量 $m$ 相对于归约查询次数 $d$ 足够大，真实对手的输出分布就与理想对手的输出分布在统计上接近。
长输出的熵论证： 对于第二个结果（定理 2），作者使用了基于熵的论证。他们构造了一个特定的 PRG，该 PRG 仅对种子的一个微小前缀应用随机性。这限制了 PRF 输出的熵，使其显著低于真正随机函数的熵，从而使得区分器可以在调用次数过少时破坏该构造。

核心贡献与结果

1. 非自适应调用的下界 (定理 1)

本文证明，如果调用次数 $c$ 满足：
$c = o\left(\frac{n}{\log n}\right) \quad \text{且} \quad c = o\left(\frac{in}{\log in}\right)$
其中 $n$ 是 PRG 输入长度，$in$ 是 PRF 输入长度，则不存在使用非自适应调用和查询有界归约的完全黑盒 PRF 构造。

范围： 该结果甚至适用于弱 PRF（即对手被限制进行 i.i.d. 均匀查询）以及单比特输出的 PRF。
意义： 这排除了对于输入长度 $in = \omega(\log n)$ 的 PRF，使用常数次非自适应调用（例如仅一次调用）来构建的可能性，解决了查询有界归约下的特定开放问题。

2. 长输出的下界 (定理 2)

本文为具有长输出 ($out$) 的 PRF 建立了下界，该下界对于自适应构造同样成立，且不需要归约是查询有界的。

结果： 不存在使用少于 $\frac{out}{\max(r, \omega(\log n))}$ 次调用的、从具有延展度 $r$ 的 PRG 构造长度为 $out$ 的 PRF 的完全黑盒构造。
与 GGM 的比较： GGM 构造（结合 Levin's trick）使用 $\omega(\log n)$ 次对 $n$ 比延展度 PRG 的调用来产生 $n$ 比输出。通过将此构造与 1 比特延展度 PRG 组合（需要 $O(n/\log n)$ 次调用），对 1 比特延展度 PRG 的总调用次数为 $\omega(n)$ 。定理 2 意味着一个 $\Omega(n / \omega(\log n))$ 的下界，表明 GGM 在 $\omega(\log n)$ 因子范围内是最优的。

重要性与主张

本文声称在解决 PRG 构造 PRF 的最优性这一长期问题上取得了显著进展。

GGM 的最优性： 虽然之前的研究局限于“树状构造”，但这项工作在特定但自然的假设（查询有界归约）下，为通用的黑盒构造提供了下界。
解决单次调用问题： 作者明确指出，其结果解决了在查询有界归约类下，是否可以用单次调用来构建 PRF 的问题。他们证明了对于输入长度 $in = \omega(\log n)$ 的 PRF，这种构造是不可能的。
鲁棒性： 这些不可能结果即使对于弱 PRF 以及（在长输出情况下）对于自适应构造也依然成立。
局限性： 作者谦虚地承认，其主要结果（定理 1）依赖于“查询有界”这一假设。他们指出，这些下界是否能扩展到所有黑盒归约仍是一个开放问题，因为其证明依赖于归约的交互次数与对手查询复杂度相互独立。

总之，本文通过利用元归约技术和精细的熵分析，证明了 GGM 构造在调用次数方面（特别是在非自适应构造和长输出构造方面）是近乎最优的。