该论文研究黑盒构造伪随机函数（PRF）的下界问题。Goldreich、Goldwasser 和 Micali 在 1984 年首次利用伪随机生成器（PRG）的黑盒访问构造出 PRF（即 GGM 构造），结合 Levin 的域扩展技术后，该构造需要对 PRG 调用 ω(log n) 次（n 为 PRG 输入长度）。至今仍没有已知的黑盒构造能用更少的调用次数实现 PRF。Beimel、Malkin 和 Mazor 在 2024 年证明，对一类称为“树构造”的特定构造族，GGM 构造已达到最优，但能否仅用一次 PRG 调用构造 PRF 这一基本问题仍然开放。本文考虑完全黑盒构造（构造和归约都是黑盒的），并限制归约与对手的交互次数独立于对手在每次交互中对其底层函数的预言机调用次数。主要结果是：不存在这样的构造，其对 PRG 的非自适应调用次数为 o(n/log n) 且同时为 o(in/log in)，其中 in 是 PRF 的输入长度。该不可能性结果即使对输出仅 1 比特的弱 PRF 也成立，且对手被限制只能进行独立同分布的均匀随机查询。此外，对于输出足够长的弱 PRF，作者还证明了一个下界，该下界即使在构造允许对 PRG 进行自适应查询的情况下也成立。这项工作深化了对 PRF 与 PRG 之间黑盒归约复杂性的理解，回答了关于最小调用次数的开放问题的一部分，并为后续研究提供了新的下界技术。适合密码学理论、复杂性理论和安全归约相关领域的研究者阅读。