【隐私计算篇】不经意传输OT及扩展协议OT Extension的进一步探索（涉及OT变体、恶意敌手模型、silent OT、OT扩展的通信对比等）

时间：2024-10-07 11:34:51

1. 背景介绍

        继《OT&OT扩展(不经意传输扩展)深入浅出》、《不经意传输协议(OT/OTE)的进一步补充（COT、ROT、依赖的困难假设等）》之后，针对不经意传输，我们继续更新该系列文章。不经意传输OT作为隐私计算、多方安全计算中的基础密码原语，扮演着非常关键的角色，比如《隐私计算匿踪查询技术深入浅出》中介绍了基于OT实现的匿踪查询PIR技术，在《安全多方计算(MPC)矩阵乘法算子的原理分析》中介绍了OT在Beaver三元组生成、乘法/与门算子实现中的应用，在《混淆电路深入浅出》中介绍了基于GC的比较算子实现引入了OT技术，以及《隐私集合求交（PSI）原理深入浅出》中谈及了基于OT技术的PSI算法。

        对于该技术知识体系的不断完善和补充，对于理解隐私计算及其解决方案、实际业务应用，也会有更进一步的助益。 本文参考【1】中系统性的综述分析，对其中关键点进行介绍和分析，以补充前两篇未谈及的部分。

2. 不经意传输OT及OT扩展协议的进一步介绍

2.1 来龙去脉

        1996年之前，OT（Oblivious Transfer）协议的构建主要依赖于公钥密码学原语（如整数分解、离散对数），导致其计算效率相对较低。Impagliazzo 和 Rudich 在1989年提出，完全摆脱公钥密码学原语，单纯依赖对称密钥原语（如伪随机数生成器或哈希函数）来构造OT协议的难度相当于证明P≠NP，这表明该问题在理论上极为困难。虽然 Beaver 在之后提出通过预计算大量随机OT实例（ROT）的方式来提高OT协议在线执行阶段的效率，但这一方法的预计算依然依赖于公钥密码学，未能从根本上解决问题。直到1996年，Beaver提出了OT扩展（OT Extension，OTE）协议，通过结合公钥密码学原语和对称密码学原语，成功突破了理论上的限制。OT扩展协议只需执行少量的“种子OT”操作（基于公钥原语），随后通过对称密钥原语扩展生成大量OT实例。

        随着后续研究的不断改进，OT扩展协议成为实际应用中大多数通用和专用安全多方计算（SMPC）协议的重要构建模块。由于OT协议和OT扩展协议在SMPC协议中的广泛使用，它们的效率在很大程度上决定了整个SMPC协议的执行效率。通过OT扩展协议，OT协议在计算效率上得到了显著提升，使得SMPC协议的实际应用变得更加可行和高效。

2.2 OT 类型及变体

        不经意传输（OT）协议有多种变体，主要包括2-选-1 OT和n-选-1 OT，它们在不同的应用场景和构造方式上有所区别：

  1. 2-选-1 OT：

    • 在2-选-1 OT协议中，发送方有两个可能的消息，而接收方从中不经意地选择其中一个接收。此协议被广泛应用于：
      • PSI协议（私有集合求交协议）：用于保护集合交集的隐私。
      • SMPC协议（安全多方计算协议）：在多方共同计算过程中保证数据隐私。
    • 2-选-1 OT协议也有其扩展版本，利用OT扩展协议能够大规模生成OT实例，从而减少计算开销并提升效率。

  2. n-选-1 OT：

    • 在n-选-1 OT协议中，发送方拥有n个可能的消息，而接收方不经意地从中选择一个消息接收。此变体应用于更复杂的场景，如：
      • PSI协议：特别是在处理更大集合时需要更多消息传输。
      • SPIR协议（对称私有信息检索）：用于确保在信息检索过程中保护数据隐私。
      • 不经意采样和不经意多项式求值（OPE）：用于保护在随机采样和多项式计算过程中的隐私。

2.3 OT协议的分类

  • 原始OT协议：最早由Rabin在1981年提出，基于二次剩余的计算困难性，提供一种不经意传输（OT）机制。发送方S发送1比特信息，接收方R有1/2概率接收到该信息，且S无法知道R是否成功接收。

  • 2-选-1 OT协议：1985年，由Even等人提出，基于单向陷门置换函数假设（如RSA）。发送方S持有两条信息M_0和M_1​，接收方R根据其选择比特r \in \{0,1\}接收M_r​。S无法推断出R的选择，而R也不能获取另一条信息。此协议广泛用于OT扩展协议的“Base OT”阶段。

  • n-选-1 OT协议：由Brassard等人在1986年提出，扩展了2-选-1 OT。发送方S持有n条信息，接收方R选择其中一条接收，而无法获取其他信息。早期实现需要调用n次2-选-1 OT，后续通过Naor和Pinkas的优化，使用O(\log n)次OT实现，并基于DDH假设在随机谕言机模型中优化为更加高效的方案。

  • 随机OT协议（ROT）：ROT由Beaver于1995年提出。R选择比特b \in \{0,1\}，S则随机生成一对消息m_0, m_1​。R接收m_b，而S无法得知R的选择。ROT常用于优化OT协议，分为线下和线上两个阶段，在线上阶段可有效减少通信开销。

  • OT扩展协议：1996年由Beaver提出，OT扩展通过少量的公钥原语和对称密钥原语组合，大幅降低了执行大量OT协议时的计算开销。其核心思想是利用伪随机数生成器或伪随机函数生成多个OT实例，从而显著提升协议的效率。

  • 广义OT协议（GOT）：由Ishai和Kushilevitz于1997年提出，允许接收方R在发送方S的消息集合中选择特定的子集。该协议广泛应用于多项式不经意求值等场景。

  • n-选-k OT协议：Naor等人在1999年提出了比单独执行k次n-选-1 OT更高效的n-选-k OT协议。R根据选择向量从S的n条信息中选择k条，而无法获知其他信息。近年的研究在隐私集合交集中采用了n-选-k OT扩展的思想，提升了协议效率。

  • 自适应OT协议：自适应OT由Naor等人于1999年提出，允许接收方R逐步选择查询，并根据之前的查询结果调整后续选择。该协议在隐私检索和数据库查询等场景中有广泛应用。

  • 门限OT协议：Naor和Pinkas于2000年提出，将发送方的任务分散给多个服务器，保证其中一定数量不合谋时，接收方R可以获得正确的OT输出。该协议具备信息论安全性，且计算更加高效。

  • 相关OT协议（COT）：2013年由Asharov等人提出，COT通过引入相关函数，使得发送方S的消息对彼此相关，且广泛应用于多方安全计算协议的预处理阶段，生成乘法三元组等共享信息。

  • 其他变体协议：包括对称OT、均摊rate-1 OT、基于陷门哈希函数的OT优化等。OT的变体使其特性在更多应用场景中发挥作用，如分支程序同态加密、私有信息检索等。

2.4 恶意敌手模型

2.4.1 恶意敌手1-out-of-2 OT

        为了应对接收方 R 的恶意行为，使其无法获得多个公钥对应的私钥，研究提出了一种通过发送方 S 控制接收方生成的公钥的机制。具体地，接收方 R 需要选择并生成两组公钥 PK_0​ 和 PK_1，但为了限制 R 只能获得其中一个公钥所对应的私钥，Bellare 和 Micali 在1989年提出了一种构造：令 R 随机生成的公钥 PK_{1-\sigma}（其中 \sigma \in \{0,1\}} 是接收方的选择比特）由发送方 S 发送的随机元素 C 决定。这意味着 R 无法*选择两个公钥中的任意一个，而只能确定其中一个公钥对应的私钥，这种机制有效防止了 R 的恶意行为。

        在这个构造中，发送方 S 通过发送一个随机值 C 来影响接收方的选择，从而保证 R 在选择比特 σ 之后只能掌握与 PKσ​ 对应的私钥，而无法同时获知 PK_0​ 和 PK_1​ 的私钥。这种机制确保了 R 的选择保持隐私，但防止了 R 作恶获取更多信息。

        在该机制的基础上，Naor 和 Pinkas 于1999年对其进行了改进，优化了通信和计算开销，最终成为目前广泛使用的经典 Base OT 原语。该改进利用了离散对数假设的困难性，特别是在DDH（离散对数难题）假设下，通过减少通信轮次和公钥计算的复杂度，使得OT协议在性能上更加高效。

2.4.2 Base OT的恶意安全

        Base OT 协议在 SMPC 协议和 OT 扩展协议中都是最基础、最核心的密码学原语 . 目前广泛使用的 Base OT原语以及后续工作都是基于恶意敌手模型下安全的。

2.4.3 恶意敌手OT扩展协议

        OT扩展协议由 Beaver 提出，极大提高了 OT 协议的效率。Beaver 使用了伪随机生成器 (PRG) 与基础 OT 相结合的方式，使得只需执行少量公钥密码操作，便能生成多数量级的 OT 实例。Ishai 和 Kilian 等人对 Beaver 协议进行了优化，提出了 IKNP 协议。在 IKNP 协议中，利用随机谕言机模型，对基础 OT 的交换信息进行扩展，实现了高效的 OT 扩展。

IKNP协议的核心阶段

  1. 基础 OT 阶段 (Base OT)：在这一阶段，进行少量的基础 OT 操作，交换伪随机种子。接收方选择它需要的消息的索引，发送方生成随机数以进行后续的扩展。

  2. OT 扩展阶段：这是 IKNP 协议的关键阶段，通过伪随机生成器 (PRG) 对基础 OT 中交换的种子进行扩展，生成大规模的 OT 实例。具体包括按列扩展和按行扩展两个步骤：

    • 按列扩展：通过PRG生成一个矩阵 Q，基于基础 OT 的种子信息扩展出多组选择比特。
    • 按行扩展：利用列扩展后的矩阵，对应生成所需的多项式规模的 OT 实例。通过对称加密算法加密消息，使得接收方只能解密它选择的消息。

  3. 输出阶段：接收方使用扩展后的选择向量解密消息，而发送方通过哈希函数H(j, q_j)进行加密，确保接收方只能解密它选择的部分。

恶意安全的 OT 扩展

        虽然 IKNP 协议在半诚实模型下是安全的，但当接收方 R 是恶意时，它可能通过改变选择比特来尝试获取未选择的信息。为了应对这种攻击，需要在协议中加入一致性检测机制，确保 R 在 OT 扩展阶段中使用的是相同的选择比特。常用的防御机制包括：

  • cut-and-choose 技术：通过随机选取部分消息进行验证，以检测接收方是否遵循了协议。
  • 一致性检测：使用哈希 MAC 对基础 OT 阶段的交换信息进行验证，确保接收方未篡改选择比特。这一技术由 Nielsen 和 Nordholt 提出，并被优化用于恶意安全的 OT 扩展协议。

        Asharov 等人进一步优化了一致性检测的哈希函数执行次数，Keller 等人则提出了一种无需增加额外基础 OT 实例的一致性检测方法，使得恶意安全的 OT 扩展协议的效率几乎与半诚实安全模型下的 IKNP 协议相当。这些改进降低了协议的通信和计算开销，极大提升了其实际应用性能。

2.5 Silent OT 扩展协议及后续改进Ferret OT

        Silent OT是一种基于伪随机相关生成器（PCG）的OT扩展协议，它的提出主要是为了解决在大量执行OT协议时，公钥密码学操作带来的巨大开销。Silent OT的优势体现在它显著降低了通信复杂度，特别是在网络带宽有限的情况下，提供了一种高效的解决方案。

Silent OT的工作流程可以分为三个阶段：

  1. 种子密钥建立阶段：在该阶段，双方通过少量的Base OT协议交换种子信息，这些种子信息会作为后续阶段的输入。尽管这一阶段涉及的计算复杂度较高，但它的通信成本较低。

  2. 本地伪随机扩展阶段：Silent OT的核心创新体现在这个阶段。双方不再需要通信，而是通过PCG技术在本地对交换的种子信息进行长度扩展，生成具有相关性的伪随机比特串。这一特点使得Silent OT扩展协议可以在后续操作中避免频繁通信，减少了网络负担。

  3. 输出阶段：在最后的输出阶段，双方基于本地生成的伪随机比特串完成OT协议的具体执行。这一过程依赖伪随机数生成器（PRG）或伪随机函数（PRF），并通过对称密码学操作实现加解密。

        Silent OT的最大优势在于它的通信复杂度与生成的COT数量呈次线性关系，这意味着它在通信效率上相比IKNP协议框架有很大提升，尤其适用于那些通信开销是主要瓶颈的应用场景。

        然而，Silent OT也有一些局限性，特别是种子密钥建立阶段的计算开销较大，以及依赖dual-LPN假设所带来的复杂编码问题。因此，虽然Silent OT在通信上效率极高，但其计算效率还需要进一步优化。在一些改进工作中，Schoppmann等人提出了使用GGM树技术来降低计算开销，并采用primal-LPN假设代替dual-LPN假设，以支持更高效的编码方式。

        基于这些改进，新的OT扩展协议如Ferret OT在通信效率和计算效率上都有进一步提升。特别是，在网络带宽较大的环境中，Ferret OT比Silent OT快了数倍，且相比传统的IKNP类型协议更加高效，因为它省去了矩阵转置等繁重操作。Silent OT扩展协议为OT协议的实现提供了一个全新的思路，通过减少通信次数和优化本地计算，实现了高效的OT扩展，特别是在网络资源稀缺的场景下具有广泛的应用潜力。

2.6 OT 扩展协议通信开销分析比较

3. 总结

        OT协议的效率直接影响了安全多方计算技术在实际应用中的落地速度。这里参考不经意传输协议研究综述，列出了一些个人比较关注的要点。

        尽管OT协议在理论和应用上都取得了显著进展，仍然存在一些挑战：

  • 计算效率与通信效率的平衡：如何在计算开销与通信开销之间找到平衡点，尤其是在网络环境受限或硬件计算资源不足的场景下。
  • 适应不同安全模型：在恶意敌手模型下实现高效、安全的OT协议仍然是一个难题，如何设计出既安全又高效的协议仍是未来的研究重点。
  • 新型密码学假设的应用：未来的研究可能会更多地探索基于新的密码学假设（如LWE、LPN）的OT协议，以获得更高效、更安全的构造。

4. 参考材料

【1】高莹等， 不经意传输协议研究综述， 2023， 软件学报

相关文章