EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity

技术摘要：不具备单向谜题（One-Way Puzzles）的 EFI 对

1. 问题陈述与动机

量子密码学目前缺乏一个类似于经典密码学中单向函数（OWF）的单一最小原语。目前出现了两个领先的候选最小假设：

1. EFI 对（高效准备、统计远离、计算不可区分）：一对混合量子态，它们易于生成，在统计上是截然不同的，但在计算上是不可区分的。EFI 对等价于量子比特承诺，并能实现安全的多方计算。
2. 单向谜题（OWPuzzs）：一个由 $(Samp, Ver)$组成的对，其中采样器生成一个经典谜题$s$和一个密钥$k$，且无界的验证者检查该密钥。OWPuzzs 蕴含了 EFI 对，但其逆命题仍是一个悬而未决的问题。

核心开放问题在于：EFI 对所需的硬度（量子态的不可区分性）是否必然意味着 OWPuzzs 所需的经典平均情况硬度（反转搜索问题）。具体而言，是否存在一个相对于某个预言机（Oracle）使得 EFI 对存在，但 OWPuzzs（即使是对于低效的验证者）不存在？

2. 方法论与预言机构造

作者构造了一个单一的确定性经典预言机 $\mathcal{O}'$ 来分离这些原语。该预言机由两层组成：

1. 状态源 ($R$)：在输入 $(b, 1^\lambda)$ 时，返回一个新鲜的混合态 $\rho_{b,\lambda}$ 的副本。这些状态由一个 Haar 随机的半维子空间 $H \subseteq \mathbb{R}^n$（其中 $n=2^\lambda$）构造而成。具体而言，$\rho_0$ 是 $H$ 上的最大混合态，而 $\rho_1$ 是 $H^\perp$ 上的最大混合式态。
2. 计数预言机 ($Count$)**：一个经典预言机，给定一个具有经典输出的预言机辅助采样器$C$的描述，返回输出概率$\Pr[C^{\mathcal{O}}(1^\lambda) = x]$ 的精确比特位。为了避免循环定义，查询按秩（Rank）**进行分层：秩为 $r$ 的查询只能询问其自身对预言机调用秩严格小于 $r$ 的采样器。

访问模型（相干最后访问，Coherent-Last Access）：针对 EFI 对的安全性是在定义的访问模型下证明的。该模型授予：

• 多项式长度的经典建议（或 $O(\lambda)$ 个量子建议）。
• 对预言机的多项次自适应经典查询。
• 在交互过程的最后阶段，恰好一次相干（叠加态）查询。
• 对挑战态（由公共源生成）的多项次参考副本。

3. 核心贡献与结果

A. 单向谜题的不存在性 (定理 A(i))
相对于 $\mathcal{O}'$，OWPuzzs 不存在，即使对于计算无界的验证者也是如此。

• 机制：$Count$ 预言机允许对手以指数级精度估计任何采样器的输出概率，仅需多项次经典查询。
• 攻击：对手可以通过逐位重建给定谜题比特的条件分布。通过从这些估计的条件概率中进行采样，对手生成的密钥能以概率 $1 - \text{negl}(\lambda)$ 被验证者接受。
• 范围：这种攻击是纯经典的，并且适用于具有全相干访问权限的对手（因为攻击并不依赖于量子查询）。因此，由 OWPuzzs 蕴含的所有原语（多副本伪随机态、纯输出单向态生成器、量子货币）在相对于 $\mathcal{O}'$ 时也不存在。

B. EFI 对的存在性 (定理 A(ii))
相对于 $\mathcal{O}'$，半子空间对 $(\rho_0, \rho_1)$ 在定义的访问模型下构成了一个安全的 EFI 对。

• 经典查询（通信复杂度归约）：针对经典查询的安全性被归约为**向量-在-子空间（VSP）**问题。在 VSP 中，Bob 持有一个子空间 $H$，Alice 持有一个承诺属于 $H$ 或 $H^\perp$ 的向量。
  • 量子情形：VSP 是容易的（Alice 通过 $O(\log n)$ 个量子比特发送向量；Bob 进行测量）。
  • 经典情形：VSP 是困难的，需要 $\Omega(n^{1/3})$ 比特的通信（Klartag–Regev 界限）。
  • 作者表明，任何关于 $H$ 的长度为 $L$ 的经典转录（Transcript）对于区分这些状态提供的优势最多为 $O(L/n^{1/3})$。由于对手受限于多项式级别的经典比特，其优势是可忽略的。
• 参考副本：对手被授予了状态的参考副本。作者表明，这些副本可以用其张成的空间的经典描述来替代。对这些张成的空间进行条件化处理，可以将问题归约为更小规模的 VSP 实例，且仅产生可忽略的安全损失。
• 相干查询：交互最后阶段允许的单次相干查询通过随机矩阵理论进行了限制。单次查询对手的偏差被证明为 $O(\sqrt{\log M / n})$，对于多项式宽度的 $M$ 而言是可忽略的。注：EFI 安全性声明特别限制在此“相干最后”模型下；该分离在面对对经典预言机具有完全相干访问权限（多次自适应叠加态查询）的对手时尚未成立。

C. 交互坍缩 (定理 B)
相对于 $\mathcal{O}'$，不存在证明具有经典消息的协议具有量子性的方法。任何在本文协议中的量子多项式时间参与者，都可以由一个向 $\mathcal{O}'$ 进行经典查询的经典多项式时间参与者来模拟。这意味着，对于具有经典输入和输出的任务，在这一预言机世界中，量子多项式时间并不比经典多项式时间提供任何优势。

D. 原语的分离
本文建立了一个黑盒障碍：在定义的模型 1.1 区分器类中，不存在从 EFI 对构造 OWPuzzs 的完全黑盒构造方法。这分离了 “NanoCrypt” 世界（EFI 对存在，OWPuzzs 不存在）与 “CountCrypt” 世界（OWPuzzs 存在）。

4. 意义与局限性

意义：

• 硬度的分离：这项工作证明了区分量子态的硬度（EFI）并不一定意味着经典搜索问题的硬度（OWPuzzs）。这表明量子密码学的最小假设可能比经典平均情况硬度更弱。
• 新的证明技术：论文引入了一种通过将量子态不可区分性归约为经典通信复杂度下界（特别是 VSP）来证明的新方法。
• 预言机构造：它提供了一个具体的单一经典预言机，在保留量子态不可区分性（在“相干最后”限制下）的同时，消除了经典输出的硬度（搜索、决策及交互）。

局限性与开放问题：

• 相干访问：EFI 安全性证明依赖于限制为一次相干查询。论文留下的问题（猜想 8.2）是：该分离是否在面对具有完全相干访问权限（多次自适应叠加态查询）的预言机时仍然成立。
• 建议（Advice）：安全性在面对 $O(\lambda)$ 量子建议时成立，但并未排除多项式大小的量子建议结合经典查询的情况（这实际上允许对手在经典转录之前合成任意量子侧信息）。
• 相对化：这些结果是关于预言机的分离。它们并未解决在非相对世界中能否从 EFI 对构造出 OWPuzzs 的问题，也不意味着 $P \neq PSPACE$。

总而言之，本文构造了一个预言机世界，在该世界中，量子密码学可以建立在量子态的不可区分性（EFI 对）之上，而不必依赖于单向谜题所需的经典平均情况硬度，从而阐明了量子密码学中最小假设的图景。