⚛️ quantum physics

From Worst-Case Hardness of $\mathsf{NP}$ to Quantum Cryptography via Quantum Indistinguishability Obfuscation

本文通过定义该原语的自然变体并证明，结合 $\mathsf{NP}$ 的无限次量子最坏情况硬度，该原语能够实现多样化的量子密码学原语构建（如伪随机酉算子和量子公钥加密），同时也实现了从经典 iO 构建单向函数的简化过程，从而开启了对量子不可区分混淆（iO）的研究。

原作者： Tomoyuki Morimae, Yuki Shirakawa, Takashi Yamakawa

发布于 2026-07-07

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Tomoyuki Morimae, Yuki Shirakawa, Takashi Yamakawa

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

大局观：锁定“黑盒”

想象你有一个秘密蛋糕配方。你想把配方交给一位烘焙师，让他们去烤蛋糕，但你不希望他们偷走配方或发现其中的秘密成分。

在密码学领域，这被称为混淆（Obfuscation）。它就像是将一本清晰易读的说明书搅成一个乱七八糟、无法阅读的结。这个“结”依然有效（你仍然可以烤出蛋糕），但如果你试图窥视它，你无法得知它是如何运作的，也无法得知其中的秘密成分是什么。

长期以来，科学家们一直在研究一种特定类型的搅乱方式，叫做不可区分混淆（Indistinguishability Obfuscation, iO）。其规则是：如果你有两个产生完全相同蛋糕的不同配方，那么这些配方的混淆版本在任何试图窥探它们的人眼中都应该看起来是一模一样的。

问题所在：经典 vs 量子

直到现在，这项研究大多是“经典”的。它假设负责搅乱配方的人和阅读配方的人使用的是标准的、非量子的计算机。

然而，我们正在进入量子时代。量子计算机就像是拥有超能力的超级厨师，能够完成经典计算机无法完成的任务。这篇论文提出的核心问题是：如果我们使用量子力学来搅乱我们的配方，会发生什么？

作者发现，量子搅乱非常棘手。在经典世界中，你有时可以通过“倒回”搅乱过程来证明其安全性。但在量子世界中，测量（观察）混淆配方的行为本身会改变它，使得“倒回”过程变得不可能。这曾让人们觉得，量子搅乱可能对于创建强大的安全锁毫无用处。

突破点：难题的“魔术戏法”

作者发现，尽管量子搅乱看起来很混乱，但如果我们假设一个特定的前提，它就会变得极其强大：即某些数学问题极其困难，以至于即使是量子计算机也无法快速解决它们。

他们称之为“NP 的最坏情况硬度（Worst-Case Hardness of NP）”。把它想象成一个巨大的、无法解开的迷宫。如果假设没有人能解开这个迷宫，那么作者展示了量子搅乱可以被用来构建一整套全新的安全锁工具箱。

量子搅乱的五种“风味”

论文定义了三种不同方式来混合“量子”与“经典”部分。想象一个拥有三个工作站的工厂：

搅乱器 (Obf)： 负责弄乱配方的人。
阅读器 (Eval)： 负责读取混淆后的配方并烤制蛋糕的人。
配方卡 (Encoding)： 混淆后的配方呈现出的样子。

作者测试了这些工作站分别为“经典”（普通）或“量子”（超能力）的所有组合。以下是他们的发现：

1. 全量子工厂 (Q, Q, Q)

设置： 搅乱器、阅读器和配方卡全部都是量子的。
结果： 这创造了量子对称密钥加密。
类比： 想象一种只有当双方都使用量子魔法时才能生效的秘密握手。如果你试图复制这个握手，量子规则会将其破坏。这允许进行超安全的通信，其中“信息”本身是一个量子态（就像一片脆弱的雪花）。

2. 量子搅乱器，经典配方卡 (Q, Q, C)

设置： 搅乱器和阅读器是量子的，但最终的配方卡是一张普通的纸。
结果： 这创造了量子计算-经典通信 (QCCC) 对称密钥加密。
类比： 你使用量子魔法来搅乱配方，但将结果打印在纸上发送。接收者使用量子魔法来阅读它。这非常适合在保持处理能力为量子的同时，通过普通电话线发送信息。

3. 量子搅拉器，经典阅读器 (Q, C, C)

设置： 只有搅乱器是量子的；阅读器和配方卡都是普通的。
结果： 这创造了公钥加密（类似于 HTTPS 网站使用的锁）。
类比： 你使用一台量子机器来锁住一个盒子，但任何拥有普通计算机的人都可以检查这个盒子是否被锁好了。这是一个巨大的突破，因为这意味着我们可以构建即使面对未来量子黑客也安全的网站，而无需接收者拥有量子计算机。

4. 经典搅乱器，量子阅读器 (C, Q, C)

设置： 搅乱器是普通的，但阅读器是量子的。
结果： 这创造了单向函数和公钥加密。
类比： 这是一种“后量子”锁。一台普通机器搅乱配方，但你需要一台量子机器才能解开它。作者证明了这足以构建现代互联网安全的基础。

5. 全经典工厂 (C, C, C)

设置： 一切都是普通的（没有量子部分）。
结果： 这是“经典”的结果，但作者发现了一种更简单的方法来证明它的有效性。
类比： 他们展示了即使使用旧式工具，只要假设那个“无法解开的迷宫”存在，你就可以比以前更容易地构建这些锁。

简单解释“魔术戏法”

他们是如何证明的呢？他们使用了一个基于著名数学定理（Valiant-Vazirani）的巧妙技巧。

想象你有一个拥有唯一解的谜题（一个“唯一见证”）。

他们取了一个“零函数”（一个始终输出“0”的配方）和一个“点函数”（一个仅在特定秘密数字处输出“1”的配方）。
他们使用其量子 iO 来搅乱这两个配方。
他们证明了，除非人们能够解开那个“无法解开的迷宫”（那个困难的数学问题），否则没人能分辨出搅乱后的“零”配方和搅乱后的“点”配方之间的区别。
因为没人能分辨差异，他们就可以利用这种“不可区分性”来构建在数学上无法破解的加密密钥。

为什么这很重要

在这篇论文之前，我们并不确定量子混淆是否真的能发挥任何作用。我们曾担心量子力学的“随机性”可能会破坏安全性。

这篇论文说：不，它是有效的！

如果我们假设存在量子计算机也无法快速解决的数学问题，那么：量子混淆是构建几乎所有类型安全量子通信的“核心枢纽”。
它允许我们构建单向状态生成器（创建容易制作但无法复制的量子态）、谜题（难以求解但易于验证）以及加密技术，从而保护秘密安全。

简而言之，作者将一个令人困惑的量子概念变成了一个可靠的未来安全通信蓝图。他们表明，即使在量子世界中，只要我们假设某些数学问题依然是无法解决的，我们仍然可以构建坚不可摧的锁。

技术摘要：从 NP 的最坏情况硬度到通过量子不可区分混淆实现量子密码学

问题陈述

不可区分混淆（indistinguishability obfuscation, iO）是一种强大的密码学原语，当与单向函数（one-way functions, OWFs）结合使用时，能够构建出大量的先进密码学工具。然而，仅凭 iO 本身并不意味着 OWF 的存在；它需要关于 NP 硬度的额外假设。在经典设定下，Komargodski 等人 [KMN+14] 证明了，在假设 NP 的无限次（infinitely-often）最坏情况硬度（ $NP \not\subseteq i.o.BPP$ ）的前提下，可以从经典 iO 构建出 OWF。

本研究解决的核心问题是**量子不可区分混淆（quantum iO）**的密码学能力。与经典混淆器不同，量子混淆器由于测量的特性而本质上是随机化的，这意味着它们不能通过固定随机种子来进行“去随机化（derandomization）”。因此，[KMN+14] 中利用去随机化从 iO 构建 OWF 的经典方法无法直接扩展到量子设定。目前尚不清楚量子 iO 结合 NP 的量子最坏情况硬度（ $NP \not\subseteq i.o.BQP$ ）是否能暗示任何密码学原语的存在，特别是那些不需要 OWF 的原语（通常被称为“微密码学（Microcrypt）”原语）。

方法论

作者通过根据三个组件（混淆算法 $Obf $、评估算法$ Eval $、混淆编码$ \hat{C}$）的计算性质（经典或量子）来形式化定义各种变体，从而对量子 iO 展开系统性研究。

他们定义了 $(X, Y, Z)$ -iO，其中 $X, Y, Z \in \{Q, C\}$ ，分别代表混淆器、评估器和编码是量子（Quantum）还是经典（Classical）。本文重点讨论五种有意义的变体： $(Q, Q, Q)$ 、 $(Q, Q, C)$ 、 $(Q, C, C)$ 、 $(C, Q, C)$ 和 $(C, C, C)$ 。

核心技术方法

其结果的基础是从 NP 的最坏情况硬度到特定密码学分布存在的归约。其方法论如下：

Valiant-Vazirani 归约： 作者利用 Valiant-Vazirani 定理，将假设 $NP \not\subseteq i.o.BQP$ 归约为 $UP \not\subseteq i.o.BQP$ （其中 UP 是具有唯一见证者的类）。这使得他们能够处理具有唯一见证者的问题。
点函数与零函数的不可区分性： 核心技术定理（定理 4.1）确立了在 $NP \not\subseteq i.o.BQP$ $N P \neq \subseteq i . o . B QP$ 的假设下，随机点函数 $P_k$ $P_{k}$ （仅在输入 $k$ $k$ 时输出 1）的混淆与零函数 $Z_m$ $Z_{m}$ （在所有处均输出 0）的混淆在计算上是不可区分的，即使区分者获得了使用相同密钥 $k$ $k$ 生成的多个样本。
- 证明简述： 如果一个区分者能够分辨 $Obf(P_k)$ 与 $Obf(Z_m)$ ，则可以构造一个算法来恢复 UP 实例的唯一见证者。这是通过构造一个电路 $V[x, v]$ 实现的，该电路仅在一个输入（ $w \oplus v$ ）上与零函数不同。通过 iO 的安全性（特别是在此设定下，其等价于单点差异输入混淆），区分这些混淆允许提取差异输入，从而恢复见证者 $w$ 。
原语构建： 利用 $Obf(P_k)$ $O b f (P_{k})$ 与 $Obf(Z_m)$ $O b f (Z_{m})$ 的不可区分性，作者构建了各种加密方案和其他原语。具体的构建取决于 $(X, Y, Z)$ $(X, Y, Z)$ 变体：
- 对于公钥加密（PKE），他们使用 $Obf(P_k)$ 作为公钥，并构造一个检查输入是否匹配密钥 $k$ 的电路。
- 对于对称密钥加密（SKE），他们使用 $Obf(P_k)$ 和 $Obf(Z_m)$ 分别作为消息 1 和 0 的密文。

核心贡献与结果

论文证明了量子 iO 结合 $NP \not\subseteq i.o.BQP$ 可以暗示丰富的密码学原语层级。结果按 iO 变体进行总结：

$(Q, Q, Q)$ -iO（量子混淆、量子评估、量子编码）：
- 暗示 IND-CPA 安全的量子对称密钥加密（QSKE），其中密钥是经典的，密文是量子态。
- 暗示 单向状态生成器（OWSGs） 和 EFI 对。
$(Q, Q, C)$ -iO（量子混淆、量子评估、经典编码）：
- 暗示 IND-CPA 安全的 QCCC SKE（量子计算-经典通信 SKE），即局部计算是量子的，但通信是经典的。
- 暗示 EV-OWPuzzs（高效可验证单向谜题）、OWPuzzs、OWSGs、QEFID 对 以及 EFI 对。
$(Q, C, C)$ -iO（量子混淆、经典评估、经典编码）：
- 暗示 IND-CPA 安全的 QCCC PKE。
- 暗示与 $(Q, Q, C)$ -iO 相同的原语集（EV-OWPuzzs, OWPuzzs, OWSGs 等）。
- 注：由于混淆器是量子的，因此无法进行去随机化，所以在此特定变体中无法通过标准路径直接暗示 OWF，但加密方案是直接构建的。
$(C, Q, C)$ -iO（经典混淆、量子评估、经典编码）：
- 暗示 IND-CPA 安全的 QCCC PKE。
- 暗示 （后量子）OWFs。
- 从而暗示由伪随机幺正算子（PRUs）所暗示的所有微密码学原语。
$(C, C, C)$ -iO（经典混淆、经典评估、经典编码）：
- 暗示 IND-CPA 安全的 PKE 和 （后量子）OWFs。
- 这恢复了 [KMN+14] 的经典结果，但证明更为简化且要求更弱。

意义与主张

作者声称了几项重要的贡献：

开启量子 iO 的研究： 本工作首次系统地分析了量子 iO 的密码学影响，定义了自然的变体，并将其能力映射到特定的原语。
连接最坏情况硬度与量子密码学： 论文确立了在结合量子 iO 时，NP 的无限次最坏情况硬度足以构建广泛的量子密码学原语（包括 OWSGs 和 EFI 对），即使在某些变体中不存在 OWF 的情况下也是如此。
简化经典结果： 即使在经典设定下（ $(C, C, C)$ -iO），作者也提供了一种新的、可以说更简单的从不完美 iO 和最坏情况 NP 硬度构建 OWF 的方法。他们的方法避免了 [KMN+14] 所需的“级联混淆”（即混淆一个已经过混淆的电路），并且仅需要对 3CNF 公式进行混淆，而非通用电路。
解决开放问题： 在最坏情况硬度下从不完美 iO 构建 3CNF 公式 OWF 是 [KMN+14] 留下的一个开放问题。虽然作者指出该问题最近已被其他工作 [HN24, LMP24] 使用不同技术解决了，但他们的方法提供了一条替代的、更简单的路径。

论文保持了谦逊的基调，强调这些结果是基于量子 iO 和 NP 最坏情况硬度的存在，并且所构建的具体原语高度依赖于混淆组件的量子/经典性质。