A Practical Protocol for Quantum Oblivious Transfer from One-Way Functions

本文提出了一种基于单向函数、在普通模型下具有新穎性、實用性且可模擬安全的量子 oblivious transfer 協議，該協議通過等價且鬆弛可提取的量子比特承諾來解決糾錯問題，同時提升了實驗實現的效率。

要点

想象你正在观看一场魔术表演，其中爱丽丝（Alice）和鲍勃（Bob）两人想要玩一个“秘密选择”游戏。

游戏：不经意传输

在这个游戏中，爱丽丝拥有两条秘密消息（我们称之为消息 A和消息 B）。鲍勃想要选择其中一条来查看。

• 限制条件 1：鲍勃绝不能窥探另一条消息。
• 限制条件 2：爱丽丝绝不能知道鲍勃选择了哪一条。

这被称为不经意传输（OT）。它是安全计算的一个基本构建模块，就像一个数字“盲盒”：卖家不知道您打开了哪个盒子，而您也无法打开另一个盒子。

问题：旧协议过于脆弱

长期以来，科学家们知道如何利用量子力学（使用称为光子的微小光粒子）来实现这一点。然而，旧方法存在三个主要缺陷，使得它们在真实实验室中无法构建：

1. 过于敏感：如果光子丢失，或者因微小的噪声（如桌面的轻微震动）导致状态翻转，整个游戏就必须重新开始。这就像试图在飓风中搭建纸牌屋。
2. 过于沉重：旧方法需要天文数字般的光子——单轮游戏就需要约10 万亿（10¹³）个。即使使用最快的激光器，发送这些光子也需要数月时间。
3. 过于复杂：它们依赖于复杂的数学证明，难以用标准的现成技术来实现。

解决方案：一种实用且“抗噪”的协议

本文的作者构建了一个新版本的该游戏，它实用、快速且稳健。以下是他们如何利用一些简单的类比来实现这一点的：

1. “纠错网”（处理噪声）

在旧游戏中，如果掉落了一张牌，整副牌就毁了。在这个新游戏中，爱丽丝和鲍勃使用了一张安全网。

• 比喻：想象爱丽丝发送一条写在纸上的消息，但她同时也发送了一个“校验和”（一种秘密代码，用于告知纸张是否破损）。
• 工作原理：即使一些光子丢失或翻转（噪声），该协议也会使用纠错码（就像一张接住掉落牌子的网）来修正错误。这意味着，仅仅因为实验室不完美，游戏就不会崩溃。

2. “单次通行证”（效率）

旧协议就像是一个游戏，你需要翻转一万亿次硬币才能获得一次“正面”。

• 比喻：新协议就像一列高速列车，而不是缓慢蜿蜒的小径。
• 结果：他们不再需要 10 万亿个光子，而只需要约1000 万到 3000 万个。这将所需时间从数月缩短至仅仅几秒。这就像等待信件通过船只送达与发送电子邮件之间的区别。

3. “魔法锁盒”（技术诀窍）

为了确保游戏安全，他们使用了一种特殊类型的量子锁盒（称为“比特承诺”）。

• 旧方法：锁盒过于严格，如果你试图作弊，整个系统就会崩溃。
• 新方法：作者发明了一种**“宽松”锁盒**。
  • 想象一个通常只容纳一个不可更改秘密的锁盒。
  • 新版本说：“我们不需要每一个锁盒都完美无缺。我们只需要大多数锁盒被紧紧锁住。”
  • 这种“宽松”的规则允许他们跳过旧协议中繁重且重复的步骤，从而节省大量的时间和资源，同时仍然保持游戏的安全。

大局观

作者不仅证明了这在理论上是可行的，还提供了一个构建它的蓝图。

• 他们表明，利用当前的技术（与量子密钥分发中使用的技术相同，该技术已在城市中进行测试），这个游戏今天就可以进行。
• 他们精确计算了需要多少光子以及需要多长时间，证明了一个安全的、多方的量子网络不再是一个遥远的梦想，而是一个可行的工程项目。

简而言之：他们将一个脆弱、缓慢且理论化的量子游戏，转变为一个坚固、快速且实用的工具，使其能够在实验室中真正被构建出来。

技术摘要

技术摘要：基于单向函数的量子不经意传输实用协议

1. 问题陈述

量子不经意传输（QOT）是在量子环境下构建多方计算（MPC）的基础原语。虽然先前的工作 [6, 7] 证明了 QOT 可以基于单向函数（OWFs）和量子资源构建，但这些协议在实验实现方面面临重大障碍。 identified 的主要问题包括：

• 脆弱性：现有协议无法容忍实验误差（例如，状态分发过程中的比特翻转）。
• 实现复杂性：对未以黑盒方式使用单向函数的零知识证明的依赖，使得将其与实用的后量子哈希函数（如 SHA）集成变得非平凡。
• 低效性：先前协议的迭代结构需要不切实际数量的量子态（例如，每次运行约 $10^{13}$ 个 BB84 态），导致传输时间长达数月量级。

作者旨在提供一种基于普通模型（plain model）中单向函数的、容噪且高效的 QOT 协议，使其适用于当前的实验设置。

2. 方法论与技术途径

所提出的解决方案通过引入一种新的密码学原语——可 equivocal 且松弛可提取（ERE）比特承诺方案，构建了一个模拟安全的 QOT 协议。

核心创新：

• 松弛可提取性：作者观察到，证明 QOT 的安全性并不需要完全的可提取性。他们引入了“松弛可提取性”，即模拟器可以提取大部分承诺中的承诺消息，而极小部分可能无法提取。这种松弛允许更高效的协议结构。
• 通过纠错实现容噪：与先前假设无噪声设备的工作不同，该协议结合了线性纠错码（具体为基于综合征的码，如 LDPC）。发送方发送编码值的综合征，使得接收方（或模拟器）能够在存在噪声的情况下纠正错误并提取正确的种子。
• 高效种子蒸馏：协议利用隐私放大技术（左余哈希引理）对 BB84 态进行蒸馏，以生成随机种子。这些种子作为 equivocal 承诺的密钥。该结构将这些种子分组为族，以允许并行承诺，避免了先前编译器中存在的二次开销。
• 承诺结构：ERE-Commitment 方案结合了：
  1. EqCommitment：一种编译器，将标准的统计绑定承诺转换为 equivocal 承诺。作者修改了原始编译器 [7]，将顺序重复次数从 $\lambda$ 减少到单个实例，以用“松弛绑定”换取完全绑定。
  2. ERE-Commitment：一种使用 EqCommitment 方案的高级协议。它涉及发送方发送 BB84 态，接收方对其测量结果进行承诺，以及一个挑战阶段，其中打开子集进行验证。剩余的状态用于生成最终消息加密的种子。

协议流程（协议 1）：

1. 量子传输：Alice 向 Bob 发送 $2\lambda_{OT}$ 个 BB84 态。
2. 承诺：Bob 进行测量，并使用 ERE-Commitment 方案对其基选择及结果进行承诺。
3. 挑战：Alice 挑战承诺的一个随机子集 $T$。Bob 打开这些承诺，以验证其与 Alice 发送的态的一致性（考虑实验误差 $\alpha$）。
4. 密钥生成：Alice 发送未挑战集合 $\bar{T}$ 的基信息。Bob 根据匹配的基将 $\bar{T}$ 划分为集合 $I_0$ 和 $I_1$。
5. 加密：Alice 发送纠错综合征，并使用从未挑战态导出的种子及伪随机生成器（PRG）加密其消息 $m_0, m_1$。
6. 解密：Bob 使用综合征纠正其错误，并解密与其选择比特 $b$ 对应的消息。

3. 主要贡献

• 新原语：定义并构建了基于单向函数的可 equivocal 且松弛可提取（ERE）比特承诺方案。
• 容噪 QOT：一种明确通过基于综合征的纠错处理实验误差（比特翻转和多光子事件）的 QOT 协议，这是先前理论构造中缺失的功能。
• 效率提升：通过优化承诺结构并利用纠错，该协议将所需的 BB84 态数量从 [7] 中的约 $10^{13}$ 减少到约 $10^7$。
• 多 OT 蒸馏：该协议允许从单次协议运行中蒸馏出多个 OT 密钥（$n_{OT}$），这对于高效实现 MPC 至关重要。
• 分析框架：本文提供了分析表达式，用于将所需的量子资源与目标安全参数（迹距离 $\Delta$）进行基准比较，同时考虑物理误差率（$\alpha$）和泄露（$\vartheta$）。

4. 结果与性能

作者提供了一个性能基准（表 1），将他们的协议与 [7] 和 [21] 针对目标迹距离 $\Delta \le 10^{-15}$ 进行了比较：

• 资源减少：所需的 BB84 态数量（$N_{BB84}$）从 [7] 协议中的 $2.27 \times 10^{13}$ 减少到约 $1.43 \times 10^6$（理想情况）至 $3.33 \times 10^7$（现实噪声环境）。
• 时间效率：这种减少转化为获取时间（$T_{acq}$）为秒级（例如，假设 1 MHz 速率，时间为 1.43 秒至 43.6 秒），而先前的工作 [7] 则需要约 8.6 个月。
• 安全性：该协议被证明在普通模型中针对恶意方是模拟安全的，仅依赖于后量子单向函数的存在。

5. 意义与主张

本文声称，这项工作弥合了理论量子密码学与实际实现之间的差距。通过消除对无噪声设备的要求并大幅减少量子资源开销，作者断言他们的协议使得 QOT（进而量子 MPC）的实验实现成为当前技术下的可行方案。

作者强调，他们的构造实现了与基于随机预言机模型（ROM）的协议 [21] 相当的 BB84 成本，但在严格更弱的计算假设下运行（基于 OWFs 的普通模型而非 ROM）。他们明确表示，其目标是“实际实现”，并不声称能达到基于 ROM 的承诺的经典效率，而是为现实世界中的量子安全 OT 提供一条可行路径。该工作还强调，松弛可提取性属性足以保证安全性，这一技术见解使得在不损害 MPC 所需的基于模拟的安全保证的前提下实现了效率提升。