给量子硬币开收据：认证随机性的安全假设清零，一篇新论文补上最后一块拼图
掷硬币公平的前提，是没人能控制它。量子随机数号称「上帝亲自掷骰子」——可你面前只是一台黑箱子，灯闪了闪，吐出一串 0 和 1。凭什么是真随机？
你怎么知道硬币没被做手脚
掷硬币公平的前提，是没人能控制它。量子随机数号称「上帝亲自掷骰子」——可你面前只是一台黑箱子，灯闪了闪，吐出一串 0 和 1。凭什么是真随机？
这个问题有个学名：认证随机性（certified randomness）。让一台不受信任的量子机器产生随机数，还要让经典世界的你验证它确实随机。本站前几天聊过量子随机数的验证标准（《量子随机数终于要补上「怎么验」的标准》），那是产业侧的动作。8 月 31 日晚上，理论侧补上了最硬的一块：arXiv:2608.31112，标题《Unconditional Certified Randomness without Structure》——不带结构假设的、无条件的认证随机性。六位作者分布在 UW、UIUC、哥大、Berkeley 和 NTT。
一部绕行史
「无条件」三个字为什么值钱？看一眼前人怎么绕就明白了。
三条路各有各的税。贝尔路线要多台纠缠设备互相盯着；LWE 路线（BCM+21）要好几轮交互、只有握着陷门的验证者能查；采样路线（AH23）压在一个没人证明过的复杂度假设上；YZ 路线最优雅——单台设备、零交互、任何人都能验证——但它的随机性结论押在 Aaronson–Ambainis 猜想上。这个 2009 年就挂出来的猜想（arXiv:0911.0996），论文原话：「被广泛相信为真，却在持续攻关下抵抗住了证明」，从 Montanaro 2012 一路到 Bhattacharya 2025，一串尝试全灭。
本文把这笔押金退了：在一个稍作变形的 YZ 问题上，无条件证出安全性，顺带反过来给 AA 猜想本身添了一份证据（它的一个重要推论成立了）。
协议长什么样
没有承诺阶段，没有交互，没有陷门。一台量子机器算一次，输出一条经典信息 x。谁想查都能查：只看 x 是不是落在某个公开的纠错码 C 里、并且每个坐标都满足公开随机预言机 H 的一个简单条件。两条经典检查全过，x 本身就是那份认证过的随机串。
安全性的量级值得抄原文：面对做了 2^o(n^c) 次自适应量子查询的敌手——计算能力可以无限——输出仍然保有 Ω(n^c) 的最小熵。相对 KRT26 只敢对付 o(log n) 层浅查询，论文自称「双重指数级的改进」。
还有个必然的第一问：随机性会不会本来就藏在预言机里？论文专门处理了这一点，验证时以预言机取值为条件来计算熵，「证明提供的是预言机之外的额外随机性」。
花絮与冷水
§8 有一段坦白得可爱的 AI 声明：「ChatGPT 5.6 被用于细化 FRS 码族的参数选择。本工作其余技术均由人类生成。」量子密码学家让大模型帮忙调参数；AI 头脑风暴还产出了「更强猜想的反例」，把他们自己的开放问题守在原地。
冷水也要泼足。这是一篇 62 KB 的理论文章：没有会议标注，没有代码；结论只覆盖 YZ 问题的有偏变体（p = 1/Θ(√n) 的有偏预言机）；熵的保证是 Ω(n^c)、c < 1/2，离 n 比特均匀输出还有距离。另外特意查了全文——beacon、区块链、彩票、NIST，一个词都没出现。论文只管数学；至于随机性信标、抽签这些应用图景，是读的人自己的想象，账别记到作者头上。
对量化与密码圈的意义倒是实在的：可公开验证的随机性源一旦有了无条件安全的基础设施级协议，从随机性信标到审计抽签的整条应用链，底座都换成了不依赖任何未证猜想的混凝土。什么时候有硬件能跑、跑多贵，是下一个十年的问题。
来源
- 论文：https://arxiv.org/abs/2608.31112
- Yamakawa–Zhandry（JACM 2024）：https://arxiv.org/abs/2204.02063
- Aaronson–Ambainis 猜想原稿：https://arxiv.org/abs/0911.0996