Malleability of transformations on the ciphertext in noisy Quantum public key encryption

技术摘要：噪声量子公钥加密中密文变换的可延展性

问题陈述
本文旨在解决在存在噪声的情况下，如何为噪声量子公钥加密（QPKE）和量子密钥分发（QKD）建立严谨的“永恒安全性”（everlasting security）公式化定义。虽然 Malavolta 和 Walter [3] 的前人工作已建立了无噪声设置下的永恒安全性框架——证明了在 Alice 和 Bob 之间仅需两轮交互即可实现安全性——但本研究探讨了引入噪声如何影响协议的安全阈值。具体而言，本文研究了密文变换的可延展性（malleability）与注入噪声后的协议安全性之间的关系。其核心问题是如何利用关于明文和密文变换可延展性的假设，将（在理想无噪声情况下的）可忽略函数（用于量化攻击者优势）推广到噪声设置中。

方法论
作者结合量子信息理论和抽象密码学，对噪声 QPKE-QKD 协议进行了分析。该方法围绕以下关键组成部分构建：

1. 通过可延展性注入噪声： 本文改编了由 Maurer 和 Tackmann [9] 提出的可延展性概念，用于比较“先认证后加密”与“先加密后认证”协议。作者定义了通过三种错误概率（转发错误、删除错误和重构错误）表征明文空间的噪声变换。这些错误被用于模拟噪声对密文的影响。
2. 迹距离与温和测量引理（GML）： 一个核心技术工具是改编自量子信息理论中的温和测量引理（Gentle Measurement Lemma）[18]。作者利用该引理，通过基于特定算符迹的下界，建立两个量子态（代表真实实验与理想实验）之间迹距离的上界。这使得在存在噪声的情况下推广可忽略函数成为可能。
3. 噪声量子多项式时间（NQPT）机器： 本文通过定义噪声量子多项式时间（NQPT）机器和噪声完全正保迹映射（CPTP 映射）来形式化噪声设置。这些对象取代了其无噪声对应的版本，用以模拟噪声条件下 Alice、Bob 以及攻击者（Eve）的行为。
4. 投影算符与状态分解： 分析过程涉及构建包含噪声项（例如 $|\sigma + \text{noise}\rangle$）的噪声投影算符 ($\tilde{\Pi}$)，并将其整合进无噪声 QPKE-QKD 协议中使用的标准投影算符 $\Pi$ 中。作者通过比较噪声与无噪声投影算符、迹运算以及 ket/bra 态的比率，推导出了迹距离的上界。
5. 资源理论方法： 本文利用 [9] 中的资源理论框架，根据协议构建的资源的可区分性来定义安全性和可用性。这包括分析协议的组合以及混合实验的不可区分性。

主要贡献

• 噪声永恒安全性的形式化： 本文定义了噪声 QPKE 协议的“永恒安全性”（定义 37），确立了噪声混合实验之间的迹距离受取决于噪声安全参数 $\lambda'$ 的可忽略函数所限制。
• 可忽略函数的泛化： 作者推导了噪声设置下的迹距离与可忽略函数 $NEGL(\lambda')$ 之间的关系。他们证明了在特定噪声假设下，噪声设置下的可忽略函数相对于无噪声情况具有更高的安全阈值。
• 通过 GML 进行迹距离界定： 一个主要的数学贡献是利用温和测量引理推导出迹距离的上界。作者证明了：
  $$Td(\tilde{Exp}, Exp) \lesssim \sqrt{NEGL(\lambda' - \lambda)}$$
  这是通过证明涉及噪声与无噪声状态（$\tilde{\rho} - \tau$）之差的特定算符的迹的下界来实现的。
• 可延展性假设： 本项工作明确地将协议的安全性与密文变换的可延展性联系起来。它量化了噪声变换的转发、删除和重构错误概率如何与无噪声 ($\lambda$) 和噪声 ($\lambda'$) 协议之间的安全阈值差距相关联。
• 计算运行时权衡： 本文分析了噪声与无噪声协议（编码、解码和密钥生成）之间的计算运行时权衡。研究表明，如果噪声协议的运行时显著更大，则安全阈值差距 $\lambda' - \lambda$ 会以特定方式缩放，这可能与运行时的差异呈指数或多项式函数相关。

结果

• 主定理： 本文证明，对于满足正确性条件的噪声 QPKE-QKD 协议，以比特 0 和 1 初始化的噪声混合实验之间的迹距离受噪声安全参数的可忽略函数限制：
  $$Td(\tilde{Exp}_{A_{\lambda'}}(1^{\lambda'}, 1), \tilde{Exp}_{A_{\lambda'}}(1^{\lambda'}, 0)) \lesssim NEGL(\lambda')$$
• 关于优势函数的推论： 作者表明，不同混合实验（$\tilde{Adv}(0), \tilde{Adv}(1), \tilde{Adv}(2)$）的噪声优势函数都受限于同一个可忽略函数 $NEGL(\lambda')$，从而确认了不同实验设置下安全定义的一致性。
• 迹的下界： 本文提供了详细的推导，表明涉及噪声与无噪声状态差值的特定算符的迹，其下界由可忽略函数的倒数乘以一个常数构成，这是应用温和测量引理的前提条件。

意义与主张
本文声称为将永恒安全性的概念扩展到噪声量子公钥加密提供了一个严谨的数学框架。通过改编温和测量引理，作者证明了只要噪声通过密文变换的可延展性假设进行表征，无噪声协议的安全保证就可以推广到噪声设置中。

作者强调，虽然引入噪声通常会导致更高的安全阈值（意味着在参数 $\lambda'$ 方面可能具有较弱的安全保证），但所推导的界限允许对噪声与无噪声协议进行定量比较。这项工作被定位为一个理论上的垫脚石，指出虽然实现无条件和永恒安全性的要求在实验上难以达成，但所提出的框架为分析噪声量子计算在密码学背景下的局限性提供了一个有价值的起点。文章最后指出，用于界定迹距离的计算过程可以进一步在以博弈论方法为中心的场景中进行研究，尽管它并未提出具体的实验实现或除理论分析之外的直接应用。