⚛️ quantum physics

How Not to Build Microcrypt

本文引入了高效的 NP 辅助影子层析术（NP-aided shadow tomography），用以证明许多被提议的量子伪随机性构造——包括那些旨在规避单向函数的构造——都在无意中暗示了单向函数或 NP 困难性的存在，从而为在 NP 复杂度类之外构建此类原语建立了新的不可行性结果。

原作者： Aditya Gulati (UCSB), Dakshita Khurana (UIUC,NTT Research), Kabir Tomer (UIUC)

发布于 2026-09-25

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Aditya Gulati (UCSB), Dakshita Khurana (UIUC,NTT Research), Kabir Tomer (UIUC)

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在量子密码学这个安静而高风险的世界里，科学家们正试图构建即使是使用量子力学奇特规则的计算机也无法破解的锁。几十年来，所有安全通信的基础一直是“单向函数”——一种容易上锁但如果没有特定密钥就极难解锁的数学锁。然而，一个被称为 Microcrypt 的新领域已经出现，这是一个理论性的领域，研究人员希望即使在传统的这些单向锁不存在的情况下，也能构建出安全的量子系统。其目标是寻找新的、虽然较弱但仍足以保护秘密的假设。为此，他们提出了新型数字对象，例如“伪随机态”和“伪随机幺正算子”，这些对象旨在对没有密钥的人来说看起来像随机噪声，但实际上是由特定的隐藏过程生成的。重大的问题在于，这些新对象是否真的可以在不依赖于旧的、更强的锁的情况下存在，还是说它们在秘密地依赖于这些锁。

来自加州大学圣塔芭芭拉分校、伊利诺伊大学和 NTT Research 的一个研究小组现在通过对许多领先候选对象的明确回答，给出了一个否定的结论。他们开发了一种分析这些量子对象的新方法，并证明了几个被认为即使在没有单向函数的情况下也是安全的流行设计，在面对一种特定类型的强大对手时实际上会失效。他们的工作表明，如果你尝试使用某些常见的架构蓝图来构建这些量子锁，你也会不经意间创造出一个传统的单向函数。这意味着，在更弱的基础上构建量子密码学的承诺比之前预想的要困难得多，而且许多目前的流行设计并不是解决方案。

研究人员的突破来自于一种他们称之为“阴影断层扫描”（shadow tomography）的技术，这是一种获取量子态并创建其紧凑经典记录的方法。想象一下，通过从不同角度照射光线并记录下投射出的阴影，来理解一个复杂且不可见的物体的形状。在量子世界中，这个过程涉及测量量子态的副本以收集有关其结构的信息。该团队意识到，对于一大类此类提议的量子态，从这些阴影中收集到的信息具有如此强的结构性，以至于拥有特定类型逻辑助手——“NP 预言机”（NP oracle）——的计算机可以利用它来逆向工程出秘密密钥。NP 预言机是一个理论工具，它可以瞬间解决某些类型的复杂搜索问题，就像一个超级智能的助手，可以在不必逐一尝试所有可能性之前，检查是否存在某个解。

研究人员展示了对于许多提议的量子态，利用这种逻辑助手进行寻找密钥的过程变成了一个简单的搜索任务。他们表明，如果量子态是“可计算的”（即其内部数值可以由标准计算机计算），那么拥有这种逻辑助手的对手可以高效地推导出密钥。这有效地破坏了系统的安全性。团队将此方法应用于一个被称为“哈密顿相位态”（Hamiltonian Phase States）的著名候选对象，该对象此前一直被广泛认为是无需单向函数即可安全的构建模块。他们的分析证明，这些态并不安全；如果它们存在，则意味着传统单向函数的存在。这一结果粉碎了通过这种特定设计绕过对更强假设需求的希望。

调查并未止步于态。研究人员还将注意力转向了“伪随机幺正算子”，它们是更复杂的量子操作，能以一种看起来随机的方式转换数据。这些被认为是 Microcrypt 工具箱中最强大的工具。团队识别出了许多最有希望的幺正算子设计中所使用的一种共同架构模式：一种简单的、可预测的层被夹在两层“Clifford”操作（一种特定类型的量子门）之间。他们发现，这种被称为 CMC 结构的特定排列会留下一个独特的指纹。通过使用一种涉及纠缠粒子对的特殊测量，他们可以提取出关于隐藏在中间层的置换的经典线索。借助那个逻辑助手，他们随后可以搜索出一个能够解释所有观察到的线索的密钥。如果幺正算子是真正的随机，那么没有任何单一密钥能解释所有的线索。但如果它是使用这种特定架构构建的，正确的密钥将总是能完美契合这些线索。

这一发现意味着，许多最近提出的安全量子幺正算子的提案，包括那些明确旨在避免单向函数的提案，实际上都是脆弱的。研究人员表明，这些设计可以与真正的随机性进行区分，并且它们的秘密密钥可以被恢复。他们针对几种著名的构造进行了测试，例如基于“PFC”（置换-函数-Clifford）结构以及各种“LRFC”（Luby-Rackoff-Function-Clifford）设计的构造。在每种中间层为简单置换或相位偏移的情况下，攻击都成功了。他们证明，这些架构不能成为 Microcrypt 的基础，因为它们不可避免地会导致回到单向函数的存在，从而使试图在更弱假设基础上构建密码学的目的失效。

然而，这篇论文并没有完全关闭 Microcrypt 的大门。研究人员仔细绘制了哪些设计在他们的攻击中幸存下来，以及哪些没有。他们发现，涉及多个重叠混合层或在端点使用秘密非 Clifford 操作的构造可能仍然是安全的。这些幸存的候选对象现在成为了未来研究的焦点。这项工作起到了至关重要的引导作用，或者说是一套“护栏”。它告诉科学家哪些是不应该去构建的，防止他们将时间浪费在本质上有缺陷的蓝图上。通过排除这些常见的途径，研究人员迫使整个领域去寻找在本质上不同的架构，以免不经意间创造出单向函数。

这项工作的意义对于量子安全的未来是深远的。它阐明了在不使用单向函数的情况下构建量子密码学的路径比之前认为的更窄、更艰难。研究人员提供了一种测试新提案的严谨方法，确保未来的设计不仅在理论上有趣，而且在面对已知最强大的攻击时也是安全的。他们的发现表明，如果 Microcrypt 要得以实现，它将需要全新的思考量子操作的方式，远离目前一直主导该领域的熟悉模式。这项工作证明了系统性分析的力量，即证明什么行不通与发现什么行得通同样重要。

技术摘要：如何构建错误的微加密（Microcrypt）

1. 问题陈述

量子密码学领域近期聚焦于“微加密”（Microcrypt）：即基于比经典单向函数（OWF）更弱的假设来构建加密原语（如伪随机态 (PRS)、伪随机幺正算子 (PRU) 和单向态生成器 (OWSG)）。具体而言，研究人员试图寻找即使在面对配备 NP 预言机的对手时仍能保持安全的原语。

虽然目前已有一些候选构造被提出（例如，哈密顿相位态、IQP 群作用以及各种 Clifford-Monomial-Clifford 架构），但针对 NP 辅助对手的系统性密码分析仍然匮乏。一个核心挑战在于：确定这些构造是否会在无意中暗示了经典单向函数的存在，从而使其不符合微加密的要求。本文旨在探讨这样一个问题：哪些用于构建 PRS 和 PRU 的自然配方，会因为暗示了单向函数或 NP 硬度而失败？

2. 研究方法

作者开发了两个主要的数学框架，用于分析并破解候选构造：

A. 可计算态的 NP 辅助阴影层析成像（Shadow Tomography）

作者引入了一种利用 NP 预言机高效学习量子态的算法。

可计算态（Computable States）： 定义一组态 $\{|\psi_k\rangle\}$ 为“可计算”的，是指在给定密钥 $k$ 的情况下，可以高效地在经典计算机上计算出任何计算基项的振幅和相位。
攻击策略： 该算法分为两个阶段：
1. 基分布匹配（Basis Distribution Matching）： 在计算基下测量未知态的副本，以获得一个经典转录（transcript）。利用 NP 预言机，搜索一个候选密钥 $k_0$ ，使得其预测的测量分布能最大化观测到的转录的似然度。这一步恢复了一个近似未知态幅度分布的密钥。
2. 通过干涉提取相位（Phase Extraction via Interference）： 为了恢复基测量丢弃的相位信息，算法构建一个“参考态” $|\psi_{k_0}^+\rangle$ （即候选密钥的正振幅态）。随后，在未知态与该参考态之间进行受控 SWAP 干涉实验。这使得提取相对相位信息成为可能。
3. 最终密钥恢复： 算法收集来自该干涉分布的样本，并使用第二次 NP 查询来寻找一个密钥 $h$ ，使相位敏感样本的似然度最大化。
结果： 对于任何具有可计算态的 OWSG 系列，拥有 NP 预言机的对手可以在多项式时间内反转生成器（找到产生高保真态的密钥）。

B. 幺正算子的 NP 辅助学习（CMC 攻击）

作者针对形式为 $U_k = C_{2,k} M_k C_{1,k}$ 的幺正算子族（其中 $C$ 为 Clifford 幺正算子， $M$ 为单项式层/Monomial layer，即带有相位的置换）开发了特定攻击。

策略： 该攻击利用 Bell 态测量。通过准备一个 Bell 态 $|\beta_{a,c}\rangle$ ，将未知幺正算子 $U$ 同时作用于两个寄存器，并在 Bell 基下进行测量，对手可以获得“位移”（displacement）约束。
Clifford 校正： 由于外层是 Clifford 结构，对手可以从经典上计算这些层如何置换 Bell 基标签。通过在经典层面“撤销”这些 Clifford 层，问题简化为检查观测到的位移是否与中间的单项式层 $M_k$ 一致。
NP 查询： 对手询问 NP 预言机：“是否存在单个密钥 $h$ 以及一组见证字符串，能够解释所有观测到的位移约束？”
结果： 对于任何此类 CMC 构造，拥有 NP 预言机的对手能以高概率将该幺正算子与 Haar 随机幺正算子区分开来。此外，通过搜索-判定归约（search-to-decision reduction），对手可以学习到密钥。

3. 核心贡献与结果

A. 反转可计算 OWSG

本文证明，所有具有可计算态的 OWSG 系列在 BQPNP（具有访问 NP 预言机的量子多项式时间）中都是可逆的。

对单向函数的意义： 如果一个 OWSG 不仅是可计算的，而且是可采样的（即给定密钥后，可以高效地从测量分布中进行经典采样），那么此类 OWSG 的存在将暗示经典单向函数的存在。
具体破解案例： 该结果破解了以下构造的安全性：
- 哈密顿相位态 (HPS)： 此前被认为可能依赖于比 OWF 更弱的假设，但作者表明它们暗示了 OWF 的存在。
- IQP 群作用态： Morimae 和 Xagawa 提出的硬度假设被证明暗示了 OWF。

B. 破解伪随机幺正算子 (PRUs)

论文表明，许多著名的 PRU 架构在 NP 辅助的对手面前是不安全的：

PFC 和 C2PFC1： 在 Clifford 层之间夹着置换/相位层的构造（例如 $C_2 P F C_1$ ）可以被区分于 Haar 随机分布并被学习。
LRFC 及分块变体： 各种带有 Clifford 端点的 Luby-Rackoff 函数构造均被破解。
泛化结论： 该攻击适用于任何“中间”层为单项式层且端点为高效描述的 Clifford 层的幺正算子族。

C. 识别幸存的候选方案

论文明确列出了其技术手段无法提供攻击的构造，并指出这些构造仍是可能的（尽管尚未得到证明）的微加密路径。其中包括：

具有多次混合轮次的完整 PRSS（伪随机态混淆器）行走。
长 Kac 行走。
具有重叠块或在单项式层之间存在中间 Clifford 层的构造（例如第三种分块 LRFC 形式）。
隐藏基底的哈密顿动力学。

4. 重要性与主张

作者将这项工作定位为为微加密领域建立“护栏”。其主要主张如下：

系统性密码分析： 他们超越了零散的攻击，提供了一套通用的方法论（NP 辅助阴影层析成像和 CMC 分析），用于评估量子密码候选方案。
无结果（No-Go Results）： 他们证明了一大类“自然”的构造——特别是那些依赖于可计算振幅或 Clifford-Monomial-Clifford 架构的构造——无法实现微加密，因为它们会无意中暗示经典单向函数或被 NP 预言机破解。
未来研究方向： 通过识别哪些架构会失效，本文缩小了寻找可行微加密原语的搜索范围。它表明，未来的构造可能必须依赖于极有可能在 NP 复杂度类之外的假设，并避免作者已证明易受攻击的特定结构模式（如可计算振幅或简单的 Clifford-Monomial-Clifford 形式）。

文章总结道，尽管微加密的图景依然开放，但那些基于可计算及可采样态构造的“低垂果实”，以及标准的 CMC 幺正架构，已被排除在无需单向函数的加密候选方案之外。