Certified Randomness with Optimal Rate

在数字世界中，信任是一种脆弱的商品。当我们进行在线投票、生成银行加密代码或为去中心化网络选举领导人时，我们依赖的是真正不可预测的随机性。如果这种随机性是可预测或有偏差的，整个系统就会崩溃。几十年来，科学家们一直在寻找一种无需依赖生成机器本身即可生成此类随机性的方法。理想的情况是，一个设备能够产生一串比特位——零和一——其过程如此混沌且均匀，以至于没有任何人，甚至包括设备的拥有者，都无法预先猜到结果。这就是“认证随机性”（certified randomness）的圣杯：一种数学上的保证，证明输出是真正随机的，且任何人都可以验证，而无需预先存在的秘密种子。

挑战一直在于，现有的方法要么产生的随机性较弱、容易被操纵，要么需要一个受信任的人来提供一个微小的、随机的起始数字。Siddhartha Jain、Saachi Mutreja 和 Bhaskar Roberts 的一项新研究解决了这一根本局限。他们开发了一种协议，允许量子计算机证明其生成了一串具有近乎完美随机性的比特位，即使这台计算机是恶意的，且检查结果的人是完全确定性的（即不具备任何随机数）。这一突破消除了对任何信任起始点的需求，实现了理论上尽可能高的随机率。

研究人员在被称为“量子随机预言机模型”（quantum random oracle model）的框架内开展工作，这是一个理论设定，其中所有参与方都可以访问一个公共的、完美的随机函数，该函数充当通用的哈希函数。在这个环境下，他们构建了一个系统，量子证明者可以生成一长串比特位，并提供一个简短的证明，以证明该字符串是真正随机的。关键的创新在于，验证者（即检查证明的人）不需要具备随机性；他们可以是一个固定的、确定性的算法。以往实现这一目标的尝试要么无法保证高质量的随机性，要么依赖于验证者拥有一个微小的、受信任的随机种子来启动过程。新协议完全消除了那个种子，证明了确定性验证者仍然可以被说服，从而相信一个由不受信任的量子设备生成的长字符串的随机性。

要理解其重要性，必须观察系统在非完美随机状态下会发生什么。如果一串比特位仅是“弱”随机的，它看起来可能很混乱，但仍可能偏向某些模式，从而变得易受预测攻击。研究人员证明，他们的方法保证了接近最大值的熵（即无序度）。在实际应用中，这意味着对于特定长度的字符串，真正不可预测的比特数量几乎等于总长度。唯一的微小随机性损失是一个对数量级的，这是由于物理定律和计算性质所导致的不可避免的结果。这比以往的方法有了巨大的进步，以往的方法往往产生的字符串中，保证的随机量仅占总长度的一小部分。

该协议主要分为两个阶段。首先，量子设备使用一种已被证明在面对量子攻击时是安全的特定数学构造，生成一个“弱”随机源。这个来源尚不足以用于高风险的应用。在第二阶段，设备将此来源通过一个压缩函数，该函数起到了过滤器的作用。这个过滤器将弱随机源浓缩成一个更短、更强的比特字符串。研究人员展示了，即使对手试图通过选择特定输入或观察函数的行为来操纵过程，他们也无法强行使最终输出变得可预测。最终的字符串保留了极高的最小熵（min-entropy），即衡量在对手观察了整个交互历史后，预测最可能结果的难度。

这项工作的核心组成部分是“条件”最小熵的概念。在许多现实世界的应用中，例如每小时广播一个新随机数的公共随机性信标（randomness beacon），当前数字的安全取决于这样一个事实：即使攻击者知道之前所有的数字，也无法预测当前的数字。研究人员表明，他们的协议保证了每一次新的随机脉冲都是不可预测的，即使在以之前所有的消息和数据为条件的情况下也是如此。这对于区块链网络中的领导者选举或为密码学协议生成公共随机字符串等应用至关重要，因为这些应用的当前轮次的完整性依赖于过去轮次的不可预测性。

团队还以严谨的态度对待了自身工作的局限性。他们证明，如果允许对手在多项式时间内运行，那么通过确定性验证者实现完美的、均匀的随机性是不可能的。攻击者理论上可以使用一种称为“拒绝采样”（rejection sampling）的技术来固定输出中的少量比特，从而有效地“操纵”系统以产生略有偏差的结果。然而，研究人员表明，他们的协议在这些约束条件下实现了最佳结果：它保证了攻击者可以固定的比特数量极其微小，以至于剩余的随机性对于所有实际的密码学用途而言仍然足够。这种损失是微不足道的，且安全性在面对任何具有现实计算能力的对手时依然成立。

这项工作对未来的安全通信和去中心化系统具有直接影响。通过消除对信任种子的需求，该协议允许创建可以在单个不受信任的量子设备上运行的随机性信标。这样的信标可以定期发布新鲜的、不可预测的随机数，且任何人都可以验证这些数字。这些数字的安全性不取决于设备操作者的诚实程度，而是取决于量子力学的定律和协议本身的数学结构。虽然目前的实现依赖于理论模型，但实际应用的路径比以往任何时候都更加清晰，它提供了一种无需我们去信任机器，即可生成现代数字社会迫切需要的信任随机性的方法。

这项研究是对早期研究人员提出的关于认证随机性极限问题的明确回答。它证实了，虽然对于确定性验证者来说，完美的均匀性在数学上是无法实现的，但达到一种在效果上与完美随机性无异的随机水平是可行的。研究人员不仅提高了随机率，还重新定义了在无信任环境下的可能边界。他们的构造为量子随机预言机模型下的无条件安全性提供了稳健的保证，为我们如何看待量子时代的随机性树立了新标准。其结果是一个既在理论上严密又在实践上有意义的协议，弥合了抽象量子理论与安全数字基础设施的具体需求之间的鸿沟。