Compressed Permutation Oracles Revisited

在数字世界中，安全性往往依赖于一个完美的、不可预测的机器的概念。密码学家构想了一种设备，它接受任何输入并产生完全看似随机的输出，但有一个至关重要的规则：如果你两次输入相同的输入，你每次都会得到相同的输出。这被称为随机置换（random permutation）。它是支撑我们保护数据之工具背后的隐形引擎，从我们存储密码的方式到验证通信完整性的算法。为了测试这些工具是否真正安全，科学家们设想了一位强大的攻击者，他可以向这台机器提问。在经典世界中，攻击者一次只能问一个问题。但在量子世界中，攻击者可以同时询问许多问题，以一种叠加的方式进行，感觉就像是在同时询问每一个可能的问题。这种以叠加态进行查询的能力使得证明安全性变得极其困难，因为攻击者获取信息的方式挑战了我们的直觉。

多年来，研究人员一直试图建立一个数学模型来追踪量子攻击者从这些问题中学习到了什么。一种很有前景的方法叫做“压缩预言机”（compressed oracle），它就像一本简化的笔记本。它并不记录整个庞大的机器，而只记录攻击者目前所询问过的输入与输出的具体配对。这使得数学处理变得可行，让科学家能够证明某些安全系统是安全的。然而，一个严重的问题困扰着这种方法：这本笔记本并不完全准确。它仅在攻击者询问相对较少的问题时才被证明能正确工作。如果攻击者询问过多，笔记本的预测就会偏离现实，导致安全证明变得不可靠。这种局限性意味着对于许多现代密码系统，我们无法确定它们在面对果敢的量子对手时能否保持稳固。

一组研究人员现在重新审视了这种方法并修复了其最关键的缺陷。他们证明了这种压缩后的笔记本比之前认为的要可靠得多。他们的全新分析证明，即使在攻击者询问的数量远大于之前的情况时——具体来说，高达总可能输入的平方根时——该方法仍然能正确工作。这比之前的限制有了巨大的提升，之前的限制仅为这个数字的一个微小部分。研究人员通过改变构建真实复杂机器与简化笔记本之间连接的方式实现了这一点。他们没有采用复杂的间接构建，而是展示了可以将笔记本视为对机器底层状态的直接测量。这种新的视角不仅使数学变得更简洁、更直接，还移除了限制攻击者提问数量的人为天花板。

这一改进的影响是即时且具体的。研究人员将他们新的、更紧密的证明应用于现代密码学中两个最重要的结构：海绵结构（sponge construction）和 Davies-Meyer 压缩函数。这些是构建保护我们数字世界的哈希函数（包括 SHA-3 标准以及较旧的 SHA-1 和 SHA-2 系统）的蓝图。利用他们改进后的方法，团队精确计算了攻击者破解这些系统所需的量子查询次数。他们发现，这些系统的安全性非常稳固，寻找碰撞所需的操作次数随系统规模的平方根增长，而寻找原像（pre-images）则需要更多。他们的结果为 SHA-3 的四个主要变体提供了明确、具体的数值，表明即使面对强大的量子计算机，只要这些计算机没有找到利用底层设计特定结构弱点的方法，这些变体依然是安全的。

研究人员小心地区分了证明数学模型的安全性与实际硬件安全性的区别。他们的工作证实，如果底层的随机置换表现如预期，那么构建在其之上的密码构造就是安全的。他们并没有声称用于实际 SHA-3 标准的特定置换是完美的，而是指出该设计本身是稳健的。这种区别至关重要；这意味着系统的失败很可能源于特定置换实现的缺陷，而非其构建方式存在根本性的弱点。通过收紧数学边界，研究人员为分析未来的系统提供了更强大的工具，确保下一代数字安全能够在对量子威胁有清晰且准确理解的基础上进行设计。

他们发现的核心在于如何处理攻击者的查询与已知答案数据库之间的关系。在旧方法中，真实机器与笔记本之间的连接较为松散，随着问题数量的增加，误差会不断累积。新方法将笔记本视为机器状态的一个直接、相干的反映。他们构建了一个连接两者之间的桥梁，保留了精确的数学关系，确保无论询问多少次问题，笔记本都不会丢失对系统真实状态的追踪。这个桥梁是通过一种将信息分为不同层级（类似于按楼层组织图书馆）的技术构建的，然后仔细规范化层级间的连接。这种规范化确保了笔记本中计算出的概率与现实世界中的概率相匹配，消除了此前限制该方法有效性的漂移现象。

这项工作不仅仅改进了一个单一的证明；它加强了对称密码学量子安全分析的整个基础。通过将压缩预言机的限制从可能输入的极小部分推升至平方根，研究人员为分析此前难以触及的系统打开了大门。结果表明，在设计具有足够容量的前提下，破解这类特定密码系统的量子优势可能并不像人们担心的那样大。团队能够提供明确的常数和具体的界限，这意味着工程师现在可以计算出系统提供的确切安全水平，而不是依赖模糊的估计。这种清晰度对于构建未来的数字基础设施至关重要，确保我们的数据在量子计算机成为现实的时代仍能受到保护。

该研究还将发现扩展到了理想密码（ideal ciphers）上，它们是许多加密方案的构建模块。在这种模型中，安全性取决于一个由不同密钥控制的置换族。研究人员表明，即使攻击者可以在不同密钥上以叠加态查询系统，他们改进后的方法在这里同样有效。这是一个显著的结果，因为它意味着这些系统的安全性不会仅仅因为涉及许多密钥而退化。无论有多少个密钥，该分析都保持稳固，强化了这些密码设计基本结构在面对量子攻击时的稳健性。

最终，这篇论文代表了理解量子安全性工具的一次成熟。它将一种曾被认为过于脆弱、无法进行严密证明的方法，强化为一种可靠的工具。研究人员表明，压缩预言机不仅仅是一个启发式的近似，而是一种追踪量子信息的数学上完备的方法。通过这样做，他们为密码学界提供了一个更清晰的视野，使人们能够设计出在面对最先进威胁时也能被证明是安全的系统。这项工作证明了通过完善数学模型来更好地反映量子世界的复杂现实所具有的力量。