不经意传输（Oblivious Transfer, OT）学习文档

在学习隐语课程（https://www.secretflow.org.cn/community/bootcamp/2narwgw4ub8rabq/course/exat9e9krgue7il?isMooc=true）的过程中，对于不经意传输的原理特别好奇，所以有了此文档记录一下。

1. 什么是不经意传输？

不经意传输（Oblivious Transfer, OT）是密码学中的一个重要基础协议。

想象一个场景：

我（接收者）想从你（发送者）那里获取一些信息，但我不想让你知道我具体获取了哪条信息。同时，你（发送者）也希望确保我只能获取到我选择的那条信息，而不能了解到其他任何信息。

不经意传输协议就是为了解决这个问题而设计的。它是一种双方协议，一方是发送者（Sender），拥有多个秘密信息；另一方是接收者（Receiver），希望获取其中一个秘密信息。

核心特性：

• 接收者的隐私性： 发送者不知道接收者选择了哪个秘密信息。
• 发送者的安全性： 接收者只能学到自己选择的那个秘密信息，对其他秘密信息一无所知。

这个“不经意”就体现在发送者对于接收者的选择是“不经意”的，即不知情的。

2. OT 的安全性基石：计算复杂性

与依赖“行为诚实”的物理比喻不同，真实世界中的密码学协议，其安全性建立在计算复杂性理论之上。这意味着协议的安全性依赖于某个数学难题（如大数分解、计算离散对数等）在计算上的困难性。

一个安全的OT协议必须保证：

• 对接收者而言：如果发送者想知道接收者的选择，那么他必须解决一个数学难题。
• 对发送者而言：如果接收者想获取比协议规定更多的信息（例如，获取两个消息），那么他也必须解决一个数学难题。

只要这个数学难题不被攻破，协议就是安全的。下面，我们将介绍一个基于“大数分解难题”的经典1-out-of-2 OT协议。

3. 真实的数据交互原理（基于大数分解难题的OT协议）

这个协议的安全性，依赖于“在不知道一个合数N的质因数分解的情况下，计算其模平方根是困难的”这一数学事实。

前提: Alice（发送者）有两个消息 M0 和 M1。Bob（接收者）想获取 Mb，其中 b 是他的选择（0 或 1）。

1. Alice的准备 (Setup):

   • Alice 生成两个非常大的素数 p 和 q，并计算它们的乘积 N = p * q。
   • 她将 N 公开，但严格保密 p 和 q。这是协议安全的核心。
   • Alice 再随机选择两个数 x0, x1。
   • Alice 将 (N, x0, x1) 发送给 Bob。

2. Bob的选择 (Choice):

   • Bob 收到了 N, x0, x1。他选择了他想要的消息索引 b (0 或 1)。
   • Bob 生成一个随机数 k。
   • Bob 计算出一个值 v = (x_b + k^2) mod N。这个 v 值巧妙地“隐藏”了他的选择 b。因为 Alice不知道 k，她无法从 v 直接反推出 b。
   • Bob 将 v 发送给 Alice。

3. Alice的加密 (Encryption):

   • Alice 收到了 v。她现在要计算两个“候选密钥”。
   • 她计算 k0_squared = v - x0 和 k1_squared = v - x1。
   • 因为 Alice 知道 N 的质因数 p和q，所以她有能力计算模 N 的平方根。她分别计算 k0_squared 和 k1_squared 的模 N 平方根。这会得到两组解（每组通常有4个根）。我们称这两组解为 Roots_0 和 Roots_1。
   • 关键点：由于 v - x_b = k^2，所以 Bob 的 k (或 -k) 必定在 Roots_b 这组解中。但是 Alice 无法分辨 k 到底是在 Roots_0 还是 Roots_1 中，因为两组解对她来说看起来都是合法的。
   • Alice 从 Roots_0 中随机挑选一个根作为 k'_0，从 Roots_1 中随机挑选一个根作为 k'_1。
   • 她使用这两个根作为一次性密码本，加密她的消息： e0 = M0 + k'_0 和 e1 = M1 + k'_1。
   • Alice 将 (e0, e1) 发送给 Bob。

4. Bob的解密 (Decryption):

   • Bob 收到了 (e0, e1)。
   • 他拥有自己选择的原始随机数 k。他可以轻易地解密他想要的消息：Mb = e_b - k。
   • 对于另一条消息 M_{1-b}，他需要解密密钥 k'_{1-b}。然而，他不知道 Alice 从 Roots_{1-b} 的四个根中究竟选了哪一个。更重要的是，如果 Bob 不知道 N 的因数分解，他连计算出 Roots_{1-b} 这个集合本身都做不到。因此，他无法获取另一条消息。

/“

3.1. 一个帮助理解的通俗解释

上面的协议充满了数学技巧，我们可以用一个“魔法信箱”的比喻来帮助理解。

第1步 - Alice的准备：
可以把 Alice 想象成一个魔法信箱的制造者。

• 她制造了一个信箱 N，这个信箱有个特性：任何人都可以往里投信，但只有她——信箱的制造者——因为掌握着秘密图纸 (p和q)，才懂得一种“魔法”，可以对信件内容进行一种特殊的操作（计算模平方根）。
• 她在信箱旁边的公告板上贴了两张公开的便签，分别是 x0 和 x1。

第2步 - Bob的选择：
Bob 想要与便签 x0 相关的信息。

• 他拿出一张自己的白纸，在上面写下了一个只有自己知道的“秘密印记” k。
• 他没有直接把 k 投进去，而是先对它进行了一个“加密”处理（计算 k 的平方），然后把这个结果和公告板上的 x0 的内容加在一起，得到一个看起来毫无规律的数字 v。
• Bob 把写着 v 的这张纸投进了魔法信箱。
• 关键点： 对于信箱外的任何人（包括Alice），都无法仅凭 v 就看出 Bob 当初参考的是 x0 还是 x1。他的选择被“秘密印记”k 完美地隐藏了。

第3步 - Alice的“魔法”操作：
Alice 拿到了 Bob 投递的 v。她并不知道 Bob 的选择。

• 她施展她的“魔法”，对 v 进行了两次分析：
  1. 她假设 Bob 参考的是 x0，然后计算 v - x0。她对这个结果施展魔法，得到了一组“可能的秘密印记” Roots_0。
  2. 她又假设 Bob 参考的是 x1，然后计算 v - x1。她对这个结果也施展魔法，得到了另一组“可能的秘密印记” Roots_1。
• 关键点： 因为 Bob 确实是基于 x0 计算的，所以他真正的“秘密印记” k (或者 -k) 就在 Roots_0 这个集合里。但是，由于数学上的巧妙设计，Roots_0 和 Roots_1 这两组“可能的印记”对 Alice 来说看起来是完全一样的，她无法分辨哪一组是“真”的。
• 于是，她从 Roots_0 里随便拿一个印记 k'_0 当作钥匙，加密了消息 M0；又从 Roots_1 里随便拿一个印记 k'_1 当作钥匙，加密了消息 M1。然后把两个加密后的消息都发给 Bob。

第4步 - Bob的解密：
Bob 拿到了两个加密的消息。

• 他拿出自己一开始记下的那个“秘密印记”k。
• 他用 k 去解密那个用 k'_0 加密的消息 e0，因为 k 和 k'_0 都出自同一个集合 Roots_0（实际上就是 k 本身或其相关值），所以他能成功解密，得到 M0。
• 而对于另一个消息 e1，它是用一个完全不同的、Bob 从未见过的“印记” k'_1 加密的，所以 Bob 无法解开它。

这样一来，Bob 就只得到了他想要的消息，而 Alice 始终不知道 Bob 到底选了哪一个。这个过程的安全性，依赖于 Bob 无法在没有图纸的情况下施展 Alice 的“魔法”（即计算模平方根）。

流程图 (Mermaid):

  sequenceDiagram
    participant Bob as 接收者 Bob
    participant Alice as 发送者 Alice

    Alice->>Alice: 生成大素数 p, q<br>计算 N = p*q<br>生成随机数 x0, x1
    Alice->>Bob: 发送 (N, x0, x1)

    Bob->>Bob: 选择 b (0或1)<br>生成随机数 k
    Bob->>Bob: 计算 v = (x_b + k^2) mod N<br>(Alice无法从v反推b)
    Bob->>Alice: 发送 v

    Alice->>Alice: 计算 (v-x0) 的4个平方根 -> Roots_0
    Alice->>Alice: 计算 (v-x1) 的4个平方根 -> Roots_1
    Alice->>Alice: (k在Roots_b中, 但Alice无法分辨)
    Alice->>Alice: 随机选 k'_0 (从Roots_0), k'_1 (从Roots_1)
    Alice->>Alice: 加密消息 E0 = M0 + k'_0, E1 = M1 + k'_1

    Alice->>Bob: 发送密文 (E0, E1)

    Bob->>Bob: 使用自己的k解密 E_b<br>Mb = E_b - k
    Bob->>Bob: (无法得到 k'_{1-b}, 无法解密 E_{1-b})
  

通过这个严格的密码学流程，我们真正实现了不经意传输。Bob 的选择对于 Alice 是保密的，而 Alice 的另一条消息对于 Bob 也是保密的。任何一方想要破坏协议，都面临着一个几乎不可能解决的数学难题。

4. 实践应用

不经意传输是构建更复杂安全协议的“积木”或“原子操作”，在很多领域都有广泛应用，尤其是在多方安全计算（Secure Multi-Party Computation, SMPC）中。

• 隐私集合求交 (Private Set Intersection, PSI):
  两方或多方（比如两家公司）想知道他们的客户名单中有哪些是重合的，但又不想暴露各自的完整客户名单。OT是实现PSI协议的核心技术之一。

• 安全计算外包:
  用户想让一台强大的云服务器帮助自己完成某项计算，但不想让服务器知道自己输入的具体数据和计算结果是什么。

• 私有信息检索 (Private Information Retrieval, PIR):
  我想从一个公开的数据库（比如维基百科）中查询一个词条，但我不想让数据库管理员知道我查了什么。OT可以用来构建PIR协议。

• 姚氏混淆电路 (Yao’s Garbled Circuits):
  这是SMPC的一个经典实现方案。在协议的输入阶段，就需要用到OT来让一方安全地获取另一方输入的对应密钥，而不知道对方的具体输入。

5. 总结

不经意传输（OT）是一个看似简单但功能强大的密码学工具。它解决了“我想让你知其一，但不知其所以一”的问题，完美保护了数据交互中接收方的选择隐私和发送方的数据安全。作为许多高级密码学协议的基石，理解OT的原理对于深入学习隐私计算、多- 方安全计算等领域至关重要。