只用哈希函数换不出密钥:完美正确的 QCCC 密钥协商被证明不可能

两个人隔着一条所有人都能听见的走廊喊话,喊完之后要拥有一个共同的秘密——旁边听全程的人不知道。

这听起来不可能,但它每天都在发生:你打开一个 https 网页,浏览器和服务器就在做这件事。它们靠的是数学难题,比如离散对数。

现在换一个问法。假设你手上只有一个「单向函数」——正着算容易,反着推难。哈希函数就是这类东西的直觉模型。光靠这个,能不能喊出一个共同的秘密?

1989 年 Impagliazzo 和 Rudich 证明了:在随机预言机模型下不能。后来 Barak 和 Mahmoody 把攻击代价降到 $O(q^2)$ 次查询——协议双方各查 $q$ 次预言机,窃听者查 $q^2$ 次就能拿到密钥。

那时候还没有量子计算机。现在有了,于是这个问题重开:如果双方能用量子方式查询呢?

8 月 4 日的一篇 arXiv 论文给出了答案:还是不行。而且窃听者根本不需要量子计算机。

先说结论

任意轮数、完美正确的 QCCC 密钥协商协议(本地量子计算、量子查询预言机,但通信全是经典消息),都存在一个窃听者以概率 1 恢复密钥,只用 $O((q_A+q_B)^5)$ 次经典查询。
「完美正确」= 双方最终一定得到同一个密钥,失败概率严格为 0。这个条件是证明的支点,不是技术性假设。
查询数与轮数、通信长度、密钥长度、预言机定义域大小全部无关。之前的结果要么只覆盖两轮(Li 等,CRYPTO 26),要么依赖未证明的猜想(Austrin 等,CRYPTO 22)。
结论是黑盒不可能性:量子安全的单向函数无法以黑盒方式造出完美正确的量子密钥协商。这不是说密钥协商不安全,而是说它需要比单向函数更强的假设。
论文致谢里写:GPT-5.6 Sol Ultra 在一次对话中找到了这个证明并起草了初稿,作者独立验证了每一条陈述与证明,并重写了全文。

三个朴素猜想,逐个撞墙

猜想一:量子查询是纯增益,双方应该更占优势。

直觉上,能查询叠加态是一种更强的能力。经典查询一次读一个位置,量子查询一次「同时」碰到所有位置。Grover 搜索就是靠这个把 $N$ 次降到 $\sqrt{N}$ 次。

但更强的能力也意味着更难分析——难分析不等于更安全。这篇论文的结果正好反过来:双方用了量子查询,窃听者只用经典查询就够。能力更强的一方没有换来安全性。

猜想二:多加几轮总能拉开差距。

这是个很硬的直觉。密钥协商的构造都在利用「交互」:我发一点,你回一点,来回几次积累出对方独有的信息。既然两轮不安全,十轮、一百轮呢?

论文的界里干脆没有轮数这一项。 $O((q_A+q_B)^5)$ 只跟两边查预言机的次数有关。多喊几句话不产生新的秘密——秘密只可能来自预言机,而预言机的查询次数已经被计进去了。

猜想三:那就把密钥拉长、把预言机的定义域做到天文数字。

也没用,界里同样没有这两项。这条特别值得停一下:定义域大小 $N$ 通常正是安全参数的来源(暴力搜索要 $2^N$ )。这里它完全不出现。

机制:把概率变成多项式

证明的骨架短得可以在一页里讲完,而且只用一个核心工具。

第一步:把协议写成两个多项式的乘积。

固定完整的公开通信记录 $t$ 、Alice 输出的密钥 $a$ 、Bob 输出的密钥 $b$ ,再固定预言机本身——把它写成真值表 $z \in \{0,1\}^N$ 。因为通信全是经典的、双方的初始私有状态互相独立,这一支的概率可以因式分解:

$\Pr[T=t,\ K_A=a,\ K_B=b \mid z] = A_{t,a}(z) \cdot B_{t,b}(z)$

这一步是整个证明的入口。它成立的条件恰好就是模型的那几条限制:消息是经典的(否则纠缠会把两边耦合起来),初始状态是乘积态(所以不允许预共享纠缠)。

第二步:量子多项式方法给出次数上界。

$A$ 和 $B$ 是什么?它们是关于 $z$ 的多项式。量子多项式方法(Beals 等)说:一个做 $q$ 次量子查询的算法,其接受概率是一个次数至多 $2q$ 的多项式。于是 $\deg A_{t,a} \le 2q_A$ , $\deg B_{t,b} \le 2q_B$ 。

这就是「量子」被消化掉的地方。叠加查询的全部威力,在这里被折叠成一个次数上界。后面的论证完全是关于低次布尔多项式的组合学,不再涉及量子。

第三步:完美正确性 = 交叉项恒为零。

定义

$C_{t,k} = A_{t,k} \cdot B_{t,k}$

次数至多 $d := 2(q_A + q_B)$ 。现在用完美正确性:双方永不输出不同的密钥,所以对任意 $k \ne \ell$ 和任意 $z$ ,都有 $A_{t,k}(z)B_{t,\ell}(z) = 0$ 。于是

$C_{t,k}(z)\,C_{t,\ell}(z) = \bigl(A_{t,k}(z)B_{t,\ell}(z)\bigr)\bigl(A_{t,\ell}(z)B_{t,k}(z)\bigr) = 0$

也就是说,固定 $t$ 之后,这一族多项式 $\{C_{t,k}\}_k$ 的支撑集两两不交:每个预言机 $z$ 最多只能让其中一个非零。

注意这里为什么必须是完美正确。如果协议允许 $10^{-9}$ 的失败概率,交叉项就不是 0 而是一个很小的正数,「支撑集不交」这个纯组合结论立刻失效。论文明说,推广到不完美正确性需要相当不同的想法。

第四步:候选密钥最多 $2^d$ 个。

标准事实: $\{0,1\}^N$ 上一个非零的多重线性多项式,若次数至多 $d$ ,则它在至少 $2^{N-d}$ 个点上非零。设 $\mathcal{K}_t$ 是所有可能与 $t$ 一起出现的密钥集合,由支撑集不交:

$2^N \ge \sum_{k \in \mathcal{K}_t} |\mathrm{supp}(C_{t,k})| \ge |\mathcal{K}_t| \cdot 2^{N-d}$

所以 $|\mathcal{K}_t| \le 2^d$ 。

这一步的意味很强:密钥可以有一百万位长,但看到通信记录之后,真正可能的取值最多 $2^d$ 个,而 $d$ 只由查询次数决定。这就是「密钥长度不出现在界里」的原因。

第五步:不逐个试,而是二分。

$2^d$ 个候选逐个验证太贵。论文证了一条引理:若两个次数至多 $d$ 的多项式 $p, q$ 支撑集不交,且已知其中恰好一个在真实的 $z$ 上非零,那么只读 $O(d^4)$ 个预言机比特就能确定是哪一个。

过程分轮进行:每一轮找出 $O(d^3)$ 个预言机位置,一旦读到这些位置的值,要么答案立刻确定,要么两个多项式之一的次数下降。次数最多降 $O(d)$ 次,于是总共 $O(d^4)$ 。

最后做平衡二分:把候选密钥分成两半,令 $p$ 为前一半对应多项式之和、 $q$ 为后一半之和。因为恰好一个候选在 $z$ 上非零,所以 $p(z)$ 和 $q(z)$ 里恰好一个非零,引理适用。二分最多 $d$ 层,每层 $O(d^4)$ :

$O(d^5) = O\bigl((q_A+q_B)^5\bigr)$

           通信记录 t
                |
       候选密钥 <= 2^d 个        [第四步: 支撑集不交 + 低次]
                |
        +-------+-------+
      前一半         后一半      [每层用引理判断, O(d^4)]
        |               |
       ...             ...       [最多 d 层]
                |
           唯一密钥              [合计 O(d^5) 次经典查询]

窃听者全程只做经典查询。它甚至不需要一台量子计算机——协议双方用的那点量子能力,在第二步就已经被换成了一个次数上界。

为什么这样设计:代价在哪

这套证明的漂亮之处是把量子性隔离在一步之内(多项式方法给出次数上界),之后全是经典组合论证。代价是模型必须足够干净,才能让第一步的因式分解成立:

通信必须是经典的。允许量子消息,两边状态会纠缠,概率就不再分解成 $A \cdot B$ 。
不能有预共享纠缠、不能有相关的初始设置。初始态必须是乘积态。
必须完美正确。这是最重的那条,前面已经说了原因。

所以这个不可能性结果的适用范围,正好是这三条划出来的那个盒子。它没有说「量子密钥协商不可能」——BB84 那类协议走的是量子信道,不在盒子里;现实中的后量子密钥交换(比如 ML-KEM)基于格问题的具体结构,也不是把单向函数当黑盒来用。

边界

完美正确是硬条件。现实里的协议常常允许可忽略的失败概率,那一类不在本文覆盖范围内。论文自己说需要「相当不同的想法」。这不是小缺口,是主要的开放方向。
黑盒不可能性不等于不可能。这类结果排除的是「把单向函数当黑盒调用」的构造。利用具体函数内部结构的非黑盒构造不受约束,历史上这条缝隙不是理论摆设。
这是查询复杂度意义上的结果。窃听者的计算量不受限制,只限查询次数。 $O(d^5)$ 次查询不等于 $O(d^5)$ 的运行时间,这不是一个能拿去跑的攻击程序。
未经同行评议。8 月 4 日的 v1 预印本。作者声明独立验证了每一步,但外部复核尚未发生。
AI 参与的那部分无法从外部核查。作者说 GPT-5.6 Sol Ultra 在一次对话里给出了证明,这句话本身不可复现:不知道提示词是什么、试了几次、人改了多少。可核查的只有最终那份数学。