技术摘要：Pauli 编码与不可克隆加密

1. 问题陈述

本文探讨了由 Gottesman [Got03] 以及 Broadbent 和 Lord [BL20] 发起的不可克隆比特问题（Unclonable Bit Question）。核心问题在于，是否可以将一个经典比特 $x \in \{0, 1\}$ 在经典密钥 $k$ 下加密为一个量子态 $\rho_{x|k}$，使得该方案满足以下条件：

1. 正确性（Correctness）： 在给定密钥和密文的情况下，可以以概率 1 恢复消息。
2. 效率（Efficiency）： 算法在多项式时间内运行。
3. 不可克隆安全性（Unclonable Security）： 对手在收到密文后，将其拆分为两个互不通信的系统（分别由 Bob 和 Charlie 持有）。在密钥公开后，Bob 和 Charlie 无法同时以显著大于 $1/2$ 的概率恢复消息 $x$。

该安全性概念被形式化为不可克隆不可区分安全性（unclonable-indistinguishable security），这暗示了**不可克隆比特（Unclonable Bit）的存在。本文通过分析与之相关的克隆博弈（Cloning Game）的最优获胜概率来研究这一问题，该概率受限于纠缠单配性（Monogamy-of-Entanglement, MoE）**博弈的获胜概率上界。

2. 研究方法

作者引入并分析了一类广泛的方案，称为 Pauli 编码（Pauli Encodings）。

2.1 方案定义

对于一组 Pauli 字符串 $\mathcal{K}(n) \subseteq \{I_2, X, Y, Z\}^{\otimes n} \setminus \{I_{2^n}\}$，比特 $x$ 在密钥 $P \in \mathcal{K}(n)$ 下的加密定义为归一化投影算子：
$$\rho_{x|P}^{(n)} := \frac{I_{2^n} + (-1)^x P}{2^n}$$
对应的解密 POVM 为 $A_{x|P} = \frac{I_{2^n} + (-1)^x P}{2}$。

2.2 分析工具

为了评估安全性，本文将克隆问题归约为 MoE 博弈。利用以下工具分析最优获胜概率 $P^*(\text{win MoE})$：

• 对称性约化（Symmetry Reductions）： 利用 Pauli 群的对称性和特定编码集的结构。
• NPA 层级（NPA Hierarchy）： 利用 Navascués-Pironio-Acín (NPA) 矩层级来计算获胜概率的上界。作者通过精确的对称性约化，为特定族群求解了最高至第三级的层级问题。
• Frobenius 范数论证（Frobenius Norm Arguments）： 用于推导针对具有受限局部维度的对手的界限。
• 成对松弛（Pairwise Relaxations）： 通过分析“成对 MoE 博弈”来识别某些证明技术的局限性。

3. 主要贡献与结果

3.1 通用下界

本文为任何具有 $K$ 个密钥的 Pauli 编码建立了通用的最优获胜概率下界：
$$P^*(\text{win MoE}) \geq \frac{1}{2} + \frac{1}{2\sqrt{K}}$$
该界限是通过针对单个密钥进行攻击并在此基础上进行猜测实现的。作者针对特定的结构化族进行了精细化处理：

• 全 Pauli 字符串 ($\{I, X, Y, Z\}^{\otimes n}$)： 下界 $\approx \frac{1}{2} + \frac{1}{2}(\frac{1+\sqrt{3}}{4})^n$。
• 实 Pauli 字符串 ($\{I, X, Z\}^{\otimes n}$)： 下界 $\approx \frac{1}{2} + \frac{1}{2}(\frac{1+\sqrt{2}}{3})^n$。
• HZH 多重集（HZH Multiset）： 下界 $\approx \frac{1}{2} + \frac{1}{2}(\frac{1}{2} + \frac{1}{2\sqrt{2}})^n$。

3.2 不可行性结果与局限性

作者指出了证明不可克隆安全性时自然方法的根本局限性：

• “3/4 之咒”（The "Curse of 3/4"）： 他们证明，对于任何正确的二进制加密方案，成对 MoE 博弈（即边际猜测概率的平均值）的最优获胜概率至少为 $3/4$。这意味着仅依赖于成对猜测边际量（pairwise guessing marginals）的论证无法建立强不可克隆不可区分安全性。
• BB84 编码的不安全性： 本文证明了 BB84 编码（使用密钥 $\{X, Z\}^{\otimes n}$）不是弱不可克隆不可区分安全的。其最优获胜概率恰好为 $\cos^2(\pi/8) = \frac{1}{2} + \frac{1}{2\sqrt{2}} \approx 0.8536$，该值在 $n \to \infty$ 时不会消失。

3.3 安全性结果

• 有界维度对手： 对于局部希尔伯特空间维度受限于 $d$ 的对手，其获胜概率的上界为 $\frac{1}{2} + \frac{d\sqrt{2^n}}{2\sqrt{|K(n)|}}$。这表明对于如 $K_{\text{all}}^{(n)}$ 等方案，针对与 $n$ 无关的维度的对手具有强安全性。
• 强不可区分安全性（Strong Indistinguishable Security）： 本文证明了几种高效的族（$K_{\text{all}}^{(n)}$、$K_{\text{real}}^{(n)}$ 以及特定的 HZH 族）满足强不可区分安全性（这是一个比不可克隆安全性更弱的概念）。值得注意的是，BB84 编码尽管在不可克隆安全性上失败，但也满足强不可区分安全性，这展示了两者概念之间的分离。
• 反交换协议分析（Anticommuting Protocol Analysis）： 对于使用成对反交换 Pauli 字符串的低效协议（见 [Bot+26]），作者对第三级 NPA 层级进行了完整的对称性约化。他们得到了一个渐近上界 $\omega_3^{(\infty)} \approx 0.5556$。这改进了之前的第一级上界 $5/8 = 0.625$，并为“最优值等于 $\frac{1}{2} + \frac{1}{2\sqrt{K}}$”的猜想提供了数值证据。
• 第一级层级的最优性： 作者证明，在固定密钥数量的所有 Pauli 交换模式中，反交换模式使第一级 NPA 上界最小。因此，任何第一级分析都无法得出低于 $5/8$ 的渐近上界。

3.4 高效协议

本文分析了几种高效的 Pauli 编码（其中密钥生成的复杂度相对于 $n$ 是多项式级别的）。来自第一级 NPA 计算的数值证据表明，像 $K_{\text{all}}^{(n)}$ 和特定 HZH 变体这样的族是不可克隆比特的有前途的候选方案，因为它们的获胜概率随 $n$ 的增加而降低。

4. 意义与主张

本文声称将 [Bot+26] 中特定的反交换协议推广到了更广泛的 Pauli 编码类，为分析其安全性提供了一个统一的框架。

• 理论极限： 它确立了“3/4 之咒”作为通过成对边际量证明不可克隆性的根本障碍，澄清了为什么文献中某些先前的方法可能是不充分的。
• 精细界限： 它为各种 Pauli 族提供了更精确的上下界，证明了在固定密钥数量的情况下，反交换协议在至少在第一级 NPA 分析的约束内，是 Pauli 编码中最优的。
• 概念分离： 通过展示 BB84 既是不可区分安全但不是不可克隆安全的，本文强调了不可克隆安全性定义的严格性。
• 未来方向： 作者指出，虽然他们为高效 Pauli 编码的安全性提供了强有力的证据，但证明这些高效方案具有强不可克隆安全性仍是一个开放问题，他们对此持猜想态度。他们明确引用了近期独立的并行工作 [AS26; Rag26]，这些工作已经建立了这些高效方案的强安全性。

这项工作是对基于 Pauli 的不可克隆加密领域进行的严谨分析，划定了哪些是可证明不安全的，哪些是有条件安全的，以及哪些仍然属于猜想范畴。