【隐私计算篇】OT&OT扩展(不经意传输扩展)深入浅出

不经意传输(ObliviousTransfer,OT)，也称茫然传输，在安全多方计算中作为基础功能组件，扮演着非常重要的作用，在混淆电路、匿踪查询、多方安全计算都有相关应用。

1. 不经意传输(OT)定义

OT就其功能来说非常明确，1-out-of-2 OT的标准定义涉及两方:发送方S持有两个信息, 接收方R持有一个选择比特，OT协议执行后,R可以得到选择比特对应索引的信息，但不能获知其他信息,而S并不知道R选择的信息是哪一个。可以推广到1-out-of-n OT，也就是接收方需要从发送方的n个信息中秘密获取某一个信息。同样的，进一步推广到k-out-of-n OT，即从发送方的n个信息中，接收方秘密获取k个信息。

图1. OT过程简图

在OT协议中,发送方拥有全部的数据权限,接收方拥有单个数据的选择权,数据交换在不经意间完成,同时保证了双方私有数据的隐秘性。

2. 不经意传输实现举例

接下来我们通过非对称加密算法，来实现一个简单的OT协议，帮助理解上述描述的过程。

图2. 基于离散对数加密实现1-out-of-2 OT

利用离散对数问题生成两个大素数p和g，协议执行过程分为4个步骤：

发送方有消息 $m_0, m_1 \in F_{P}^{*}$ （素数域），发送方随机选取 $a \in F_{P}^{*}$ ，并计算 $A=g^a\ mod \ p$ ，将发送给接收方。

接收方选择第σ条消息（σ=0或1），接收方随机选取 $b \in F_{P}^{*}$ ，并计算 $B = A^{\sigma} * g^{b} mod p$ ，将B发给发送方。

发送方利用，按照图中的步骤3计算和的值，然后用为密钥，对称加密；用为密钥，对称加密。将加密后的密文和传递给接收方。

接收方利用A和b计算解密密钥 $g^{ab} mod\ p$ ，对称解密对应的密文后拿到想要的正确消息。

上述过程为1-out-of-2 OT，同理可以扩展到1-out-of-n OT，计算流程如图3所示：

图3. 基于离散对数加密实现1-out-of-n OT

协议执行过程分为4个步骤：

发送方有n条消息 ${m_1,...,m_n}$ ， $m_i \in G$ (代表素数域 $F_{P}^{*}$ )，挑选的两个生成，将发送给接收方。

假定接收方想获得第条消息，则接收方随机选择大整数 $r \in G$ ，并计算 $y=g^r*h^t\ mod\ p$ ，将发给发送方。

发送方利用，分别对条消息，重复执行图中左下角的计算步骤，每一次执行都会随机选择大整数 $k_i \in G$ ，并结合消息计算和。然后将组发送给接收方。

接收方拿到组后，利用掌握的大整数，计算想要的第条消息 $m_t=\frac{b_t}{a^r_t}$ 。

对于第4步接收方的操作，把消息泛指为，则对的计算公式展开得到如下：

可以看出，要想获得消息，要么令，此时消息为接收方想要获得的消息；要么计算出，由于是发送方的秘密数字，因此保证了接收方不可能正确解密除消息之外的其余条消息。
对于发送方来说，虽然知道，但是不知道的情况下，由于离散对数问题难解，因此是无法推断出的正确值。

3. 不经意传输存在的性能问题

了解了OT的应用场景、功能以及原理后，我们来分析下OT存在的性能方面的问题，以下分析参考了OSU Mike教授的分享【1】。先看一种简单的实现，需要注意，该方案是一种朴素实现，仅为了方便说明OT的性能问题，帮助理解。

图4. 基于非对称加密实现1-out-of-2 OT的通信&计算代价分析

可以看到，OT 需要一定的计算通信代价，每次 OT 都使用公钥操作（比对称密钥操作慢几个数量级）。 OT 需要公钥密码学。安全计算一般使用成千上万次的 OT，这种代价在实际业务难以承受。

如果降低OT的成本？

想法：使用预计算

1. 预先计算少量随机 OT（使用公钥密码学）

2. 将这些扩展为许多常规 OT（仅使用对称密钥密码学）

4. 性能提升之不经意传输扩展(OT Extension)

针对上述提到的OT开销过大问题，引出OT扩展(OT Extension，即OTE)技术。OT扩展协议通过使用少量的公钥原语实例和大量的对称密码学操作，‌生成大量的公钥实例。‌这一技术被称为“扩展原语”，‌在加密过程中起到了非常重要的作用。‌OT扩展协议的目的是大幅降低公钥密码学运算次数，‌从而提高协议的执行效率。‌Beaver在1996年提出了第一个OT扩展协议。

OT扩展协议的基础是OT协议，‌OT的执行开销非常大，‌无法通过对称密码学操作实现OT。OT扩展协议的实现涉及多个步骤和概念，‌包括Base OT协议基础构造、‌OT扩展协议基础框架、‌以及在不同敌手模型下的协议构造。‌总的来说，‌OT扩展协议通过优化和扩展传统的OT协议，‌使得能够在不增加太多计算开销的情况下执行大量的OT操作，‌这对于需要高效安全通信的应用来说是非常重要。

接下来，会具体阐述OTE的实现原理，首先介绍【2】中协议：

图5. 基于Random OT来降低在线OT计算和通信成本

这里的Random OT，是指在预计算阶段生成的OT，它们使用公钥密码学生成，并且选择的消息是随机的。这些预先生成的随机OT可以在后续阶段通过对称密钥密码学扩展为实际所需的OT，从而减少了公钥操作的开销。通过这种方式，可以显著降低每次OT的成本，使其接近对称密钥加密的成本。

带入具体的示例数值进行流程计算。

离线阶段：假设发送方S生成两个随机信息，分别为 $r^\$ _0 = 3,r^\$ _1 = 8$ ，接收方持有选择比特 $c^\$ = 1$ , 通过基于公钥的OT完成离线预处理计算，即接收方获取到选择比特 $c^\$$ 对应的信息， $r^\$_{c^\$ }=r^\$_1=8$ 。

在线阶段：假设发送方持有的真实信息为 x_0 = 2, x_1 = 6 ，接收方持有选择比特 b=0 ，那么可以计算出 d = 1 ，发送方使用 r_0, r_1 根据对 m_0, m_1 进行相应盲化， $m_0 = r_1 \bigoplus x_0 = 8 \bigoplus 2 = 10$ , $m_1 = r_0 \bigoplus x_1=3 \bigoplus 6 = 5$ ，接收方接收到后，在接收方本地， m_b = m_0 ，计算 $m_0 \bigoplus r^\$ _{c^\$} = m_0 \bigoplus r_1 = 10 \bigoplus 8 = 2 = x_0$ , 接收方顺利拿到选择比特 b=0 对应的信息。如果计算 $m_1 \bigoplus r^\$ _{c^\$} = m_1 \bigoplus r_1 = 5 \bigoplus 8 = 13$ , 拿到的将是一个随机数。

基于上述过程，我们已经可以实现在输入未知之前的离线阶段完成所有的OT ，但依然存在缺点： OT的成本仍然和以前一样，必须发送两个额外的L位消息。

接下来，继续介绍改进版本IKNP03【3】中提出的OTE方案，以较低的成本，将少量（基础）OT扩展为大量OT，公钥操作仅用于基础OT。

图6. IKNP03-OT Extension计算流程

在图6所示例子中，通过Step1-Step6，进行6次OT，生成n组Random OT信息。如果不能明白，可以使用另一个角度，如图7所示，进一步观察体会。

图7. IKNP03-OT Extension计算结果的另一种理解

对于每个i，发送方计算 ( $q_i, q_i \bigoplus s$ ) , 对于每个i，接收方确切知道发送方的一个值及其位置（OT），理解了这一点，就可以理解IKNP03的OTE了，通过有限的OT过程，生成n组Random OT结果。后续利用图5介绍的方案，采用对称加密或者异或盲化可以完成大量的OT过程计算。

使用高而窄的矩阵（n行，m列，且n远大于m）对每一列执行基础OT

m个OT

传输n位字符串，获取每一行的扩展随机OT

每个OT进行2次哈希函数调用（不需要公钥密码学）

如果需要常规OT，则需要发送2个额外的消息

性能：在semi-honest场景，可以实现秒级完成2800万次OT计算。

进一步分析，图7中的方案存在一个问题，那就是receiver方每一列使用的都是相同的r，但malicious player可能不会这么用，所以需要设置检查，【4】提出确保使用的都是同样的r（采用类似于spdz中的MAC-check），花费的额外代价可控，在malicious场景，可以实现秒级完成2400万次OT计算。另外，【5】提到了后续对IKNP03性能提升的方案，可以进一步学习。

另外，看到有同学【6，7，8，9】分享的OT知识理解的内容，写的也挺好，可以参考学习一下。

扩展阅读系列：

1. 《不经意传输协议(OT/OTE)的进一步补充（COT、ROT、依赖的困难假设等）》

2. 《不经意传输OT及扩展协议OT Extension的进一步探索（涉及OT变体、恶意敌手模型》

5. 参考文献

【1】[Mike Rosulek，OSU] Oblivious Transfer

【2】[Beaver91]Efficient Multiplarty Protools Using Circuit Randomization

【3】Ishai, Yuval, et al. "Extending oblivious transfers efficiently." Annual International Cryptology Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003.

【4】Gilad Asharov, Yehuda Lindell, Thomas Schneider, and Michael Zohner. More efficient oblivious transfer extensions with security for malicious adversaries. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology – EUROCRYPT 2015, Part I, volume 9056 of Lecture Notes in Computer Science, pages 673–701. Springer, Heidelberg, April 2015.

【5】Practical Secure Two-Party Computation and Applications

【6】Oblivious Transfer (OT) Protocol

【7】不经意传输(OT)-总结

【8】Mike Rosulek系列课程笔记整理(完结): 不经意传输及其优化

【9】高效的不经意传输（Oblivious Transfer）扩展协议-IKNP

【10】安全多方计算(1):不经意传输协议

今天的文章【隐私计算篇】OT&OT扩展(不经意传输扩展)深入浅出分享到此就结束了，感谢您的阅读。