Parallel Kac's Walk Generates PRU
本文证明了并行 Kac 步行的线性数量顺序重复构成了一个具有强抗逆向查询能力的自适应安全伪随机幺正算子族，从而证实了先前的猜想并展示了路径记录技术的有效性。
原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
在现代密码学的广阔版图中，目标通常是创造出那些对于试图窥探内部的人来说看起来完全随机、实则由特定隐藏规则生成的物体。在经典世界中，我们依赖于像伪随机函数和置换这样的工具来保障数字生活的安全，确保加密信息对黑客而言是不可读的。随着我们步入量子时代，计算机处理信息的方式发生了根本性的变化，科学家们需要同样能抵御量子攻击者的全新工具。其中一种工具便是“伪随机幺正算符”（pseudorandom unitary），这是一个复杂的数学对象，其作用类似于量子态的随机洗牌。它构建高效，但其混合程度之彻底，使得任何人即便拥有通过正向和反向查询并观察结果的能力，也无法分辨它与真正的随机洗牌之间的区别。长期以来，构建这些安全的量子洗牌器（quantum shufflers）的已知方法，都依赖于一个涉及三个不同步骤的特定且略显僵化的配方。
一组研究人员现在发现了一条通往同一目的地的不同路径，证明了基于一种被称为“并行卡茨行走”（parallel Kac's walk）概念的方法可以同样有效地生成这些安全的量子洗牌器。这种方法从 1956 年提出用于描述气体中粒子如何混合的数学模型中汲取了灵感。在量子版本中，想象一个拥有许多可能状态的系统。该过程并非一次性洗牌所有状态，而是选取这些状态中的对，并同时对每一对应用一个随机的微小旋转。通过重复这种简单的配对与旋转过程，且重复次数随系统规模线性增长，整个状态集合就会变得彻底混合。研究人员证明，如果你将这种混合过程中的真正随机选择替换为安全的、由计算机生成的伪随机选择，其结果便是一个稳健的量子洗牌器。这种新构造不仅对标准攻击是安全的，而且在面对能够反向查询系统的对手时依然表现出色，这一特性使其异常强大。
这项工作的意义在于它对既定规范的突破。直到目前为止，每种被证明能创建这些安全量子洗牌器的方法都遵循一种被称为 PFC 构造的特定模式，即按固定顺序叠加一个随机置换、一个相位偏移和另一个置换。这种新方法完全打破了这一模式。它不再是叠加不同类型的操作，而是依赖于重复应用一个单一且统一的模块：并行卡茨行走步骤。这好比构建一把安全的锁，不是通过组合三种不同类型的齿轮，而是通过多次重复应用一个设计精良的单一齿轮机构。研究人员表明，经过线性次数的此类重复后，系统会达到一种与真随机在计算上不可区分的随机水平。这意味着对于任何实际用途而言，观察者都无法分辨他们是在与构建的系统交互，还是在与一个完美的随机系统交互，即使他们被允许进行多项式次数的查询。
该安全性的证明依赖于一种称为“路径记录”（path recording）的高级技术，它允许研究人员在不知道密钥的情况下追踪对手与系统的交互。他们展示了在一定步数之后，系统实际上会将对手的视角强制进入一个特定的、受限的状态，在该状态下随机性得到保证。通过仔细分析当对手尝试从不同角度（包括反转操作）探测系统时的行为，团队确认了该构造保持了安全性。这一发现尤为重要，因为它为一种基本的密码学原语提供了一个第二个独立的候选方案。在安全领域，拥有多种不同的构建同一安全对象的方法至关重要；如果某种设计的弱点被发现，另一种设计可以作为备份。此外，这种新构造在概念上更简单，依赖于基本单元的重复而非不同组件的复杂组装，这可能使其在未来的量子硬件上更容易实现。
研究人员还探讨了进一步简化的潜力，建议在每个步骤中使用的随机旋转最终可能会被贯穿整个过程的单个、完全相同的旋转所取代，或者复杂的置换可以被更简单的局部交换所替代。如果这些简化假设成立，其结果将是一个既高效又安全的局部随机电路系统，从而解决该领域的一个长期问题。虽然这些具体的简化工作仍是未来研究的开放性问题，但核心结论依然成立：线性数量的并行卡茨行走步骤足以生成一个安全的伪随机幺正算符。这项工作不仅证实了一个先前的猜想，还扩展了量子密码学家可用的工具箱，为如何构建量子未来的“不破之锁”提供了全新的视角。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。