Quantum Time-Lock Puzzles in the Quantum Random Oracle Model

在密码学领域，长期以来一直存在着一种愿望：发送一条在特定时间段内无法被读取的消息。想象一下，一封数字信件被密封在一个盒子里，而这个盒子需要一把钥匙，但这把钥匙只能通过一项需要整整一年持续、循序渐进的工作才能锻造出来。这种被称为“时间锁谜题”（time-lock puzzle）的概念，是定时释放加密技术（如在特定日期后才揭示秘密的加密技术）或密封竞标（如在截止日期前保持出价隐藏状态）等技术的基石。挑战始终在于：如何确保创建谜题的人可以快速完成，而试图破解谜题的人却被迫等待，即使他们拥有成千上万台强大的计算机同时工作。几十年来，研究人员一直认为，在标准的计算环境中，构建这样一个安全的谜题是不可能的。其逻辑很简单：如果谜题仅仅是一段数据，聪明的攻击者只需简单地复制该数据，并将其分配给许多处理器，就能几乎瞬间解决它，而不是等待所需的时间。

这种不可能性的结论在经典计算机中是成立的，但一支研究团队现在展示了，当谜题本身是一个量子对象时，规则就会发生改变。Prabhanjan Ananth 和 Yao-Ting Lin 在一项新研究中证明，通过将谜题编码进一种脆弱的量子态，我们可以创建一个即使是面对最强大的量子计算机也依然安全的时限锁，前提是这些计算机无法运行超过所需的完整时长。他们的工作解决了一个悬而未决超过十五年的问题：是否可以利用量子力学的定律来强制执行一种无法通过并行处理来绕过的时延。他们构建了一个系统，在该系统中，谜题可以瞬间生成，但破解它则需要一段特定的、连续的时间，这段时间无法被跳过或加速，从而有效地创造了一个依赖于量子信息的本质属性来保护其秘密的数字时间胶囊。

问题的核心在于创建谜题与解决谜题之间的区别。在经典环境下，如果一个谜题只是一串比特，攻击者可以复制这串比特并将其分发给一千台不同的计算机。每台计算机同时尝试解题的不同部分，从而在比单台计算机所需时间短得多的时间内解决谜题。这种复制和并行化的能力，使得经典的定时释放加密谜题无法在标准密码学模型中实现安全。研究人员意识到，解决方案在于量子态的独特属性：它们无法被完美复制。如果谜题是一个特定的量子态，攻击者就只能受限于一份谜题副本。这种单副本约束至关重要，因为它阻止了攻击者将副本分发到网络中的计算机。相反，他们必须按照谜题创建者的意图，一个接一个地进行顺序操作，即使他们拥有许多并行处理器。

为了实现这一点，研究人员设计了一个系统，其中的谜题由一组微小的量子粒子组成，每个粒子都处于一种特定的、微妙的配置中。谜题的创建者生成这些粒子，并在其上附带一些经典线索，然后将整个包发送给接收者。接收者随后必须执行一系列操作来寻找隐藏的代码。该过程的设计使得创建者可以几乎瞬间生成谜题，但接收者必须花费很长时间，执行一系列不能跳过或加速的检查步骤。研究人员证明，即使攻击者拥有无限的计算能力，并且可以使用多项式数量的并行处理器，只要他们无法运行满所需的持续时间，他们就无法比预定的时间更快地解决谜题。

该系统的安全性依赖于对随机函数以及量子态与它们相互作用方式的巧妙运用。谜题包含了一组量子令牌，每个令牌都与一个隐藏的数字相关联。要找到解，求解者必须针对一个随机函数测试不同的可能性，这个过程就像一把锁，只有在尝试正确的钥匙时才会开启。在经典世界中，攻击者可以同时尝试所有可能的钥匙。而在这种量子版本中，由于谜

件是一个单一且不可复制的状态，攻击者无法通过复制谜题在多个副本上进行并行尝试。虽然攻击者被允许在单轮计算内进行多次并行查询，但谜题的单副本特性迫使他们必须通过一系列无法绕过的轮次来推进。研究人员表明，即使使用最先进的量子算法，攻击者也无法通过猜测答案或在允许的并行宽度之外使用并行处理来获得显著优势。唯一的成功途径就是遵循谜题所要求的漫长且缓慢的路径。

研究人员还解决了如何在不提前泄露答案的情况下验证是否找到了正确答案的问题。他们包含了一个验证标签，这是一个小的经典信息，允许求解者检查是否找到了正确的隐藏数字。该标签的生成方式与其量子态紧密相连，但不会泄露解。如果求解者试图在没有完成全部工作的情况下通过猜测来破解，验证标签几乎肯定会失败，从而迫使他们重新开始。这种机制确保了求解者无法通过猜测和检查来尝试绕过所需的任务，而是必须执行解锁消息所需的完整序列操作。

这项工作的显著方面之一是，它是在一个被称为“量子随机预言机模型”（quantum random oracle model）的理论框架内进行的。该模型假设所有参与方都可以访问一个完美的、可以以量子方式进行查询的随机函数。虽然这是一个理论构造，但它为证明该系统在符合量子力学定律的任何可能攻击下都是安全的提供了坚实的基础。研究人员证明了他们的构建是高效的，这意味着谜题可以被快速创建，并且即使攻击者拥有大量并行处理器，它依然保持安全。他们证明，对于任何期望的时延（例如一年），生成谜题所需的时间随延迟增长得非常缓慢，而解决它所需的时间则随延迟呈线性增长。

这一发现对于未来安全通信的影响是深远的。它为基于时间而非仅仅基于数学难度的新型加密协议打开了大门。例如，它可以实现公平的合同签署，即双方都能保证对方在时间过后无法退出；或者实现安全的投票系统，即投票仅在特定截止日期后才进行统计。研究人员还指出，他们的方法避免了对复杂数学假设的依赖，而这些假设可能会被未来的计算进步所打破。相反，其安全性依赖于量子力学的基本属性，而这些属性被认为是不可破解的。

在构建过程中，研究人员使用了一种被称为 BB84 态的特定量子态，这是在量子系统中编码信息的已知方法。他们将这些状态与一系列随机函数相结合，创造出一个既易于生成又难以破解的谜题。谜题由大量此类量子态组成，每个状态都携带一部分隐藏信息。求解者必须按特定顺序处理这些状态，任何试图跳过步骤或改变处理顺序的行为都将导致无法恢复消息。研究人员表明，攻击者在未完成工作的情况下猜中正确解的概率极小，在任何实际用途中几乎可以忽略不计。

论文还明确了哪些情况是不可能的。它确认，如果谜题是一个经典对象，或者求解者使用的是经典计算机，其安全性将会崩溃。经典谜题的不可能性结果仍然成立，研究人员的工作并未改变这一点。突破点专门在于量子领域，即谜题本身是一个量子态，且求解者是一个量子计算机。这种区分至关重要，因为它突出了量子信息在强制执行经典世界无法实现的约束方面的独特能力。

研究人员的证明是严密的，依赖于一系列层层递进的逻辑步骤。他们首先证明了单个量子谜题对于能够进行有限次查询的攻击者是安全的。接着，他们扩展了这一结果，证明即使攻击者可以使用多项式数量的并行处理器，只要受到单份谜题副本的限制，安全性依然成立。最后，他们证明了该系统对于任何可能的量子策略都是安全的，包括那些涉及将谜题与其它量子系统纠缠的策略。其结果是一个全面的证明，证明了在他们定义的条件下，该定时释放加密谜题是安全的。

这项工作代表了量子密码学领域的一个重要进展。它表明，通过拥抱量子力学的独特属性，可以克服经典计算的局限性。创造一个能够抵御量子攻击者的定时释放加密谜题的能力，为安全通信开辟了新的可能性。虽然这项技术目前仍处于理论阶段，但其可能性的证明为未来的发展提供了坚实的基础。研究人员已经展示，通过正确的方法，是可能创造出一个真正由时间锁定的数字时间胶囊的，这为数字时代提供了更高水平的安全保障。