← 返回 PaperDaily
大模型与智能体
40年悬案新突破：从PRG构造PRF，调用次数下界被证实
从PRG构造PRF，最少要调用几次底层生成器？这个问题悬了40年。本文用元归约范式给出了两个新下界：查询有界归约下，非自适应构造省不掉ω(n/log n)次调用；长输出PRF无论自不自适应都无处可躲。理论密码学爱好者，这篇值得细读。
龙哥读论文
阅读 2
查看原文
原论文信息如下：
PRF构造的极限：黑盒下界新突破
伪随机函数（PRF）是现代密码学的“万能积木”，加密、消息认证、零知识证明等基础协议都离不开它。PRF由密钥索引，密钥随机时，任何高效算法都无法将其输出与真随机函数区分。这种“确定性中透着随机”的特性，使其能支撑各种安全证明。PRF同时具备两个看似冲突的性质：给定密钥和输入，输出完全确定，保证可验证性；对不知密钥的观察者，输出序列又与真随机序列不可区分。正是这种双重性格，让PRF能充当流密码、消息认证码和承诺方案。可以说，没有PRF，现代密码学的许多理论构造都将失去根基。
PRG（伪随机生成器）给一个小种子，吐出一长串“看似随机”的比特，任何高效算法都分不清其输出和真随机串。PRG是许多密码学构造的起点，其安全性依赖于：虽然输出远长于种子，但每个输出比特都受种子中所有比特的复杂影响。PRG的存在性等价于单向函数的存在性，这是密码学中最低层级的假设之一。因此，从PRG构造PRF的研究，本质是在探索如何用最基础的假设构建最强大的工具。
1984年，Goldreich、Goldwasser和Micali给出了GGM构造——只需黑盒调用PRG就能构造PRF。用二叉树理解最直观：密钥k作根，每层用PRG扩展左右孩子，输入x的比特决定走向，叶子即输出。每次计算需走完整棵树，调用次数等于输入长度|x|。后来Levin的域扩展技巧把次数压到ω(log n)。但根本问题始终悬而未决：最少到底需要多少次调用？能否只用一次？GGM构造的优雅在于用树形结构将PRG的“局部随机性”扩展为PRF的“全局随机性”，但树形结构可能并非最优——也许存在更巧妙的非树形构造。本文的结果正是要排除这种可能性（至少在查询有界归约框架下）。
直到2024年，Beimel、Malkin和Mazor在CRYPTO上才有了局部突破：他们证明了在“树构造”这一受限类中，GGM已是最优。但树之外的一般情况依然开放，甚至没有结果能排除“只调用一次PRG就构造出PRF”的可能性。Beimel等人的工作提供了重要启示：在受限类别中证明最优性，可能是通往一般性结论的必经之路。一般构造中，多个输入可能共享同一个PRG种子，这大大增加了分析复杂性。本文的贡献之一，正是发展了一套能处理这种共享种子的技术工具。
本文三位作者——特拉维夫大学的Bar Alon、本-古里安大学/乔治城大学的Itai Dinur以及乔治城大学的Muthuramakrishnan Venkitasubramaniam——给出了两个新下界。第一，在查询有界归约框架下，非自适应构造至少需要c = ω(n/log n)次PRG调用（同时满足c = ω(in/log in)）。第二，对于输出长度为out的长输出PRF，无论构造是否自适应，调用次数下界均为out / max(r, ω(log n))，其中r是PRG拉伸量。这两个结果把“最少调用次数”问题的已知边界大幅推进。两个下界本质不同：第一个依赖查询有界归约模型，第二个则完全不需要归约模型限制，具有更强普适性。这种“双管齐下”策略使本文结论覆盖面更广。
查询有界归约：一个更精细的黑盒模型
要读懂这篇论文，必须分清“黑盒构造”的概念。构造PRF时只允许把PRG当“黑盒子”调用——输入种子，拿回输出，完全不关心内部实现。安全归约也一样：证明“PRG安全则PRF安全”时，归约算法只能把攻击者当黑盒调用，不能拆开看内部结构。这种完全黑盒约束是保证模块化和可替换性的关键。黑盒构造允许我们在不改变框架的前提下替换底层PRG实现，因此成为密码学工程实践的首选。然而，黑盒约束也意味着无法利用PRG的任何内部结构信息，限制了我们可能达到的效率上限。本文正是在这种约束下探索效率极限。
但在标准黑盒定义下，有一个微妙隐患：攻击者A可自行选择向函数预言机查询多少次。若A选择m次查询，归约必须给出m个回答，运行时间被A牵着走。更麻烦的是，归约对A的调用次数可能依赖m，导致模拟时出现死循环式纠缠。标准黑盒定义只要求归约在多项式时间内运行，未对交互模式施加更细约束。正是这种宽松性，使许多下界证明技术（如元归约）难以直接应用。本文提出的查询有界归约模型，正是为了填补这一技术空白。
本文引入了一个更精细的模型——查询有界归约（query-bounded reduction）。定义很直观：存在多项式d(n)，使得对所有区分优势不低于α(n) = 1 − e^{−n}的攻击者，归约与攻击者的交互次数始终不超过d(n)，且这个上界与攻击者每次交互中查询底层函数的次数完全无关。换句话说，归约可以因攻击者更强而减少调用次数，但不能因攻击者“问得多”而跟着增加。这个定义捕捉了归约行为的关键特征：归约对攻击者的“信任”程度。在查询有界归约中，归约假设攻击者优势足够大，因此一次调用就足够，无需多次“验证”。这种假设在密码学中是合理的，同时也排除了那些通过“耗尽”攻击者查询能力来获得优势的病态归约。
这个限制是不是太强了？论文给出了让人安心的论证：文献中已知的主流归约——GGM构造、Goldreich-Levin硬核谓词构造、Waters的签名方案——统统满足查询有界性。因此这个模型并非逃避困难，而是对几乎所有“正经”归约的准确刻画。作者逐一检查了这些经典归约的交互模式，发现它们都有一个共同特征：归约对攻击者的调用次数是预先固定的常数（或多项式），不依赖于攻击者在单次调用中查询函数的次数。例如，在GGM构造的安全性证明中，归约只需调用攻击者一次——攻击者提交区分判断，归约据此构造PRG区分器。这种“单次调用”模式正是查询有界归约的典型特征。因此，本文下界适用于所有已知主流构造，大大增强了结论说服力。
理想敌手与真实敌手：元归约范式的巧妙运用
本文的技术核心是元归约（meta-reduction）范式，最早可追溯到Boneh和Venkatesan的工作。思路概览：首先，假设存在黑盒归约R，能将任何区分PRF与随机函数的攻击者A转化为区分PRG与随机串的攻击者B。然后，构造一个“理想敌手”A_ideal，拥有超强计算能力（如指数级查询），能轻松区分PRF与随机函数。接着，构造一个“真实敌手”A_real，计算能力有限但能“模拟”A_ideal的行为。若A_real与A_ideal行为足够接近，则R(A_real)能以显著优势区分PRG，与PRG安全性矛盾。这个矛盾意味着假设R存在是错误的，从而证明所需下界。元归约的巧妙之处在于，它将看似不可能的下界证明问题，转化为关于敌手行为模拟的构造性问题。
先设计“理想敌手”：它可以指数级查询PRG，因此能轻松区分PRF和随机函数。理想敌手查询PRG的所有输入，同时查询PRF/随机函数的m个输入，如果所有回答能一致地匹配某个密钥就输出1（表示“这是PRF”），否则输出0。由于密钥长度为λ，取m = λ + n时，真随机函数与某个密钥一致的概率只有2^{−n}，熵论证保证了理想敌手的区分优势接近1。熵论证基于一个简单事实：真随机函数的m个输出是独立均匀分布的，而PRF（由密钥k索引）的m个输出完全由k决定。因此，当m > λ时，真随机函数的输出与任何密钥都不一致的概率极高。理想敌手通过穷举所有密钥来检查匹配，虽然计算量巨大，但在理论上（非高效）是可行的。这个理想敌手的存在性，为后续真实敌手模拟提供了目标。
再构造“真实敌手”：它不能真的做指数级查询，但它可以“偷看”归约对PRG的查询记录，把归约给出的回答收集起来。对每个可能的密钥k，真实敌手计算一个“真实分数”rs_k——它估计的是在归约查询到的PRG输出背景下，该密钥与回答一致的概率加和。理想分数is_k则是对固定密钥k，直接数有多少输入输出对匹配。由线性期望关系，真实分数恰好等于理想分数的期望。这里的“偷看”是元归约的核心技术手段：真实敌手并不需要自己查询PRG，而是利用归约R的查询记录来获取信息。因为R在模拟攻击者时，必须回答攻击者对PRF的查询，而这些回答是通过查询PRG获得的。真实敌手通过观察R的查询模式，可以推断出R所使用的PRG种子，从而计算出每个密钥的匹配程度。这种“搭便车”策略，使得真实敌手能在多项式时间内完成模拟。
但直接比对分数还有两个坑。第一个坑是输出的依赖性：如果两个输入x_i和x_j对应同一个PRG种子，那么这两个PRF输出并不独立，无法直接用集中不等式。论文的解决办法很聪明——先证明一个图论引理（Claim 3）：对每个密钥k，要么存在一个种子被至少p个输入共享，要么能找到规模为m/p的一组输入，它们的PRG种子两两互不相同。在后者情况下，用随机预言机实例化PRG，输出就是独立随机变量，于是Hoefding不等式可以上场。这个图论引理是证明中的关键一步，它将“种子共享”这一复杂情况分解为两种简单的极端情况：要么大量输入共享同一个种子，要么存在大量输入使用互不相同的种子。在第一种情况下，我们可以通过固定该种子的输出来简化分析；在第二种情况下，我们可以利用独立性来应用概率集中不等式。这种“二分法”是处理复杂依赖关系的常用技巧。
第二个坑是挑战值y*的植入。归约手里握着一个PRG挑战y*（要么是G(s)，要么是均匀串），它可能故意把y*当作某次调用的输出植入回答中。如果只有一个输出被这样影响，而其他输出又通过切断依赖保持了独立性，那么挑战对总分数的整体扰动就被限制在可忽略范围。为彻底平滑真实/理想分数的剩余差异，论文引入一个随机阈值α，在[0.8, 1]区间均匀选取，分数超过α则判定为PRF。随机化让边界处的判断误差被“涂抹”掉，只要两个分数的差距足够小，最终输出的统计距离就足够小。这个随机阈值技术是元归约中的标准技巧，它避免了在固定阈值处可能出现的“边界效应”。如果使用固定阈值（例如0.9），那么真实分数和理想分数可能在阈值附近有微小差异，导致判断结果不同。通过随机化阈值，这种差异被“平均化”了，从而使得真实敌手和理想敌手的输出分布更加接近。
从单次调用到多次调用：下界证明的推广
单次调用的论证如何推广到c次非自适应调用？非自适应的意思是：构造在计算一个输入x时，同时发出c个PRG查询，且所有查询在结果返回前就已经确定，不依赖任何中途输出。一般形式如下。非自适应构造是密码学中非常自然的一类构造，因为它们的分析相对简单——所有查询可以并行执行，不需要考虑查询之间的依赖关系。许多实际构造（如GGM）都是非自适应的。然而，非自适应构造也可能不是最优的——自适应构造（即后续查询依赖于先前查询的输出）可能用更少的调用次数实现同样的功能。本文的定理1专门针对非自适应构造，而定理2则对自适应构造也给出了下界（尽管仅针对长输出PRF）。
证明采用迭代修补策略。每一轮，对剩余未固定的PRG调用，寻找一个“高频种子”——也就是被当前样本集中足够多样本对应的输入共同使用的种子。如果找到，就固定该种子的PRG输出值，并缩小样本集，记录这个种子。重复这个过程，直到两种终止条件之一发生。这个迭代过程类似于“逐步压缩”策略：每一轮我们都识别出一个被大量输入共享的种子，通过固定它的输出，我们减少了需要分析的“自由度”。这个过程类似于在解线性方程组时逐步消元。每一轮固定一个种子，相当于减少了一个未知数，使得剩余的问题更易于处理。迭代的终止条件确保了过程不会无限进行下去——要么所有种子都被固定（条件一），要么剩余种子的共享程度不够高（条件二）。
条件一：所有c个种子都被固定。此时PRF输出与密钥相关的熵已被压缩到极限，可以用统计方法直接区分PRF与随机函数。在这种情况下，PRF的输出完全由固定的种子值和输入x决定，不再依赖于密钥k。因此，我们可以通过比较不同输入下的输出模式来区分PRF和随机函数——PRF的输出模式是确定性的（给定固定的种子），而随机函数的输出模式是随机的。这种区分方法不需要知道密钥，只需要观察足够多的输入输出对。
条件二：某个轮次不再有高频种子。此时可以通过推广的Claim 3，找到一个足够大的输入集合，使它们的PRG种子两两互不相同，恢复独立性，回到单次调用时的论证框架。在这种情况下，剩余的种子虽然可能被多个输入使用，但没有任何种子被“足够多”的输入共享。这意味着我们可以找到一个输入子集，使得它们使用的种子互不相同（或者至少大部分不同），从而恢复统计独立性。一旦有了独立性，我们就可以应用Hoefding不等式等概率工具，将问题简化为单次调用时的情形。
参数控制是证明能“闭合”的关键。样本数按上面的递推增长，最终m = (poly(n))^c · c!。由于c = o(in/log in)，在n充分大时m ≤ 2^in，即样本空间没有超出PRF的输入域。与此同时，c = o(n/log n)又保证元归约对PRG的总查询数d·poly(m) ≤ 2^{n/4}。根据论文的Lemma 1，即使允许2^{n/4}次查询，也无法区分真随机函数与均匀随机输出。于是归约“攻破PRG”的声称与随机函数的安全性产生矛盾，结论就是不存在的构造。这里的参数控制体现了密码学证明中常见的“平衡”技巧：我们需要样本数m足够大，以便真实敌手能够准确模拟理想敌手；同时，我们又需要m不能太大，以免超出PRF的输入域或导致归约的查询次数过多。这两个约束条件共同决定了c的上界：c = o(in/log in)和c = o(n/log n)。当in = Θ(n)时，这两个条件等价；当in远小于n时，第一个条件更严格。
这里有一个直接推论：任何常数次非自适应的黑盒构造都被排除了。因为当in = O(log n)时，PRF可以直接用密钥存真值表无条件构造；当in = ω(log n)时，定理1直接给出矛盾。这个推论顺带解决了“单次调用”这个40年悬案在查询有界归约框架下的答案。这个推论的证明非常简洁：如果in = O(log n)，那么输入空间的大小是2^in = poly(n)，PRF的真值表大小也是poly(n)，因此可以直接将密钥设为真值表，无需任何PRG调用。如果in = ω(log n)，那么定理1的结论c = ω(in/log in) = ω(1)意味着c不能是常数。因此，任何常数次调用的构造都被排除了。这个推论的重要性在于，它首次在一般构造类别中排除了常数次调用的可能性，而不仅仅是树构造。
长输出PRF：自适应构造同样受限
定理2针对输出长度out较长的PRF，技术路线与定理1完全不同，走的是熵论证。核心思想是：考虑某个函数f的m次应用的总熵。对于真随机函数，m个不同输入输出的总熵显然是out·m；但如果f来自一个用“病态PRG”构造的PRF，总熵就会少掉一截。熵论证是一种强大的下界证明技术，它不依赖于归约的具体结构，而是直接分析构造的“信息论极限”。基本思路是：如果某个构造产生的PRF的总熵低于真随机函数的总熵，那么必然存在一个统计区分器能够区分它们。这个区分器不需要知道密钥，只需要比较m个输入输出对的总熵。熵论证的优势在于，它适用于任何构造，包括自适应构造，因为它不关心查询顺序。
病态PRG长什么样？看下面的公式：G只对输入的前w位应用一个随机函数G'，剩下的输入位直接原样拼在输出后面。论文取w = out − r − 1 = ω(log n)，也就是说只有前ω(log n)位被真正“随机化”了。这个病态PRG虽然看起来“很弱”，但它仍然是安全的——因为前w位经过随机函数处理，而后out - w位是输入的直接拷贝。任何试图区分G(s)和均匀随机串的算法，都需要区分前w位的随机函数输出和均匀随机串，这本身就是困难的。然而，这个PRG的熵特性非常差：它的输出熵最多只有w + (in - w) = in比特（因为后out - w位是确定性的），远小于均匀随机串的out比特。正是这种“熵缺口”使得基于它的PRF构造可以被区分。
图8：病态PRG构造。它只对输入前w位应用随机函数G′，剩余位原样输出。这类PRG依然安全，但熵被严重压缩。这个构造的巧妙之处在于，它利用了PRG安全定义的“宽松性”——安全定义只要求输出与均匀随机串不可区分，而不要求输出具有高熵。因此，一个熵很低的PRG也可以是安全的。本文利用这一点，构造了一个“安全但熵低”的PRG，从而将PRF构造的熵分析转化为对PRG调用次数的下界。
直觉很清晰：如果底层PRG是这种形式，那么无论构造如何把PRG输出揉进最终函数值，每个输出点最多只能从三处获得熵：密钥λ、PRG对被随机化部分的“伪随机贡献”以及输出中直接透传的输入位。对于一次调用，输出熵不超过λ + (out−1)。对m个不同输入求和，总熵不超过λ + m·(out−1)。相比之下，真随机函数的熵是out·m。两者相差m − λ比特，取m = λ + n就得到n比特的熵差，足够在统计上区分。这个熵论证的关键在于，它给出了PRF输出熵的一个上界，这个上界与构造的具体形式无关，只依赖于PRG的熵特性。因此，无论构造如何巧妙，都无法突破这个熵上界。当m足够大时，熵差变得显著，从而可以被统计区分器检测到。
推广到c次调用后，下界变为out / max(r, ω(log n))。这个下界有一个非常漂亮的对应：GGM构造配合Levin域扩展，用n位拉伸的PRG构造n位输出的PRF需要ω(log n)次调用；若从1位拉伸的PRG出发，先经Goldreich-Levin定理提升拉伸量，再套GGM，总调用次数是ω(n)。定理2给出的下界是n/ω(log n)。两者相比，GGM构造在ω(log n)因子内已经是最优——这在40年后算是给了经典构造一个“基本配得上”的复杂度认证。这个对比揭示了一个有趣的现象：虽然GGM构造可能不是最优的，但它已经非常接近最优了。下界out / max(r, ω(log n))表明，任何构造至少需要out / r次调用（当r较大时）或out / ω(log n)次调用（当r较小时）。对于典型的参数设置（out = n, r = 1），下界是n / ω(log n)，而GGM构造需要ω(n)次调用，两者相差ω(log n)因子。这个因子可能是一个技术上的gap，也可能反映了构造与下界之间的真实差距。
总结与展望：黑盒分离的未解之谜
这篇论文的两个下界，是把“从PRG构造PRF最少需要几次调用”这个横跨40年的问题，往终点线推了两大步。但终点线还远：尽管本文的结果在查询有界归约和长输出PRF这两个重要场景中取得了突破，但一般情况下的最优性仍然是一个开放问题。从更广阔的视角看，黑盒分离领域的研究不仅关乎PRF构造的效率，更关乎我们对密码学“不可约复杂度”的理解。每一个下界结果都在告诉我们：某些看似可能的构造路径，实际上是被数学定律所禁止的。这种“负面结果”虽然不如“正面构造”那样引人注目，但它们共同构成了密码学理论的坚实基础。
一般黑盒归约的扩展：定理1目前只覆盖查询有界归约。能否把该限制完全去掉，是本文遗留的最直接的开放问题。如果答案是肯定的，那就意味着黑盒构造的调用下界真的和归约的“品格”无关。这个问题的难度在于，标准黑盒归约中，归约对攻击者的调用次数可能依赖于攻击者的查询次数，这会导致元归约的模拟过程出现循环依赖。要解决这个问题，可能需要发展全新的技术工具，或者找到一种方法来“归一化”归约的行为。
常数次与最优次之间的空隙：非自适应下界是c = ω(n/log n)，而GGM + Levin给出的构造只需ω(log n)次。从线性除以对数到纯对数，中间还有巨大的鸿沟有待填补。这个gap意味着，要么存在比GGM更高效的构造（接近n/log n次调用），要么存在更强的下界（接近ω(log n)次调用）。无论哪种情况，都将是一个重要的突破。填补这个gap可能需要新的构造技术或新的证明技术，或者两者兼而有之。
短输出自适应构造：定理2只处理长输出情形。对于1比特输出且允许自适应调用的构造，目前仍没有强下界。自适应往往能比非自适应“省”调用次数，证明难度也会大一个量级。自适应构造的挑战在于，后续查询依赖于先前查询的输出，这使得熵分析变得更加复杂。在自适应构造中，不同输入的PRG种子可能以复杂的方式相互关联，导致总熵的上界更难刻画。目前，对于短输出自适应构造，我们甚至不知道是否存在常数次调用的可能性。
树构造与一般构造的统一：Beimel等人已经在树构造中证明GGM最优，本文的结果为更一般构造提供了部分支持。但要把树构造与一般构造统一在一个框架下，仍需要全新的洞见。树构造的特殊性在于，每个PRG种子只被一个输入路径使用，这大大简化了分析。一般构造中，多个输入可能共享种子，这种“共享”是分析的主要难点。本文的迭代修补策略提供了一种处理共享种子的方法，但这种方法可能不是最优的。未来的研究可能需要发展更精细的工具来刻画共享种子的影响。
黑盒分离这个领域，表面上只是“证明某个东西做不到”，但每一条证明背后都是硬核的数学博弈。在量子计算和格密码不断冲击经典密码学边界的今天，这种扎实的复杂性下界研究，依然是整个密码学大厦最底层、最可靠的承重墙之一。正如本文所展示的，一个看似简单的问题（最少需要几次调用）可能需要数十年的时间才能取得实质进展。这种“慢工出细活”的特点，正是理论密码学的魅力所在——它不追求短期的应用价值，而是致力于建立永恒不变的数学真理。
龙迷三问
这篇论文到底在解决什么问题？本文研究黑盒构造伪随机函数（PRF）所需的最少伪随机生成器（PRG）调用次数。
这篇工作最值得看的点是什么？论文为理论证明，无实验效果，主要贡献为证明下界。
这篇工作的边界或风险在哪里？优点：证明了PRF构造中PRG调用次数的下界，填补了理论空白；提出了查询有界归约的新概念，扩展了黑盒分离的适用范围。缺点：结果仅适用于查询有界归约，未覆盖所有黑盒归约；证明过程复杂，技术性强，难以直接应用。
如果你还有哪些想要了解的，欢迎在评论区留言或者讨论~
龙哥点评
论文创新性分数：★★★★☆
通过元归约范式，构造理想敌手和真实敌手，证明在查询有界归约下，非自适应调用PRG次数为o(n/log n)和o(in/log in)的PRF完全黑盒构造不存在。
实验合理度：★★★☆☆
现有材料未完整覆盖数据划分、基线公平性和统计显著性，因此按中性评价处理。
学术研究价值：★★★★☆
通过元归约范式，构造理想敌手和真实敌手，证明在查询有界归约下，非自适应调用PRG次数为o(n/log n)和o(in/log in)的PRF完全黑盒构造不存在；更关键的是问题定义是否可复用到同类任务。
稳定性：★★★☆☆
现有材料未提供充分的极端条件、重复运行或扰动测试，稳定性暂按中性评价。
适应性以及泛化能力：★★★☆☆
现有材料未完整展示跨数据集、跨场景或分布外实验，泛化能力仍需进一步验证。
硬件需求及成本：★★★☆☆
现有材料缺少完整训练资源、参数量、显存和推理时延信息，成本暂按中性评价。
复现难度：★★★☆☆
现有材料未确认完整代码、配置、数据处理脚本和权重是否齐备，复现难度暂按中性评价。
产品化成熟度：★★★☆☆
论文验证以研究实验为主，真实部署中的时延、成本、维护和异常场景仍需补充验证。
可能的问题：结果仅适用于查询有界归约，未覆盖所有黑盒归约；证明过程复杂，技术性强，难以直接应用。
*本文仅代表个人理解及观点，不构成任何论文审核或者项目落地推荐意见，具体以相关组织评审结果为准。欢迎就论文内容交流探讨，理性发言哦～ 想了解更多原文细节的小伙伴，可以点击"阅读原文"，查看更多原论文细节哦！
