【隐私计算篇】OT&OT扩展(不经意传输扩展)深入浅出
【隐私计算篇】OT&OT扩展(不经意传输扩展)深入浅出
不经意传输（Oblivious Transfer，简称OT）是安全多方计算中的基础组件，在混淆电路、匿踪查询、多方安全计算等领域都有广泛应用。本文将深入浅出地介绍OT的基本概念、实现方法、性能优化以及OT扩展技术（OTE），帮助读者全面理解这一重要技术。
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个步骤：
- 发送方有消息（素数域），发送方随机选取，并计算，将发送给接收方。
- 接收方选择第σ条消息（σ=0或1），接收方随机选取，并计算，将B发给发送方。
- 发送方利用，按照图中的步骤3计算和的值，然后用为密钥，对称加密；用为密钥，对称加密。将加密后的密文和传递给接收方。
- 接收方利用A和b计算解密密钥，对称解密对应的密文后拿到想要的正确消息。
上述过程为1-out-of-2 OT，同理可以扩展到1-out-of-n OT，计算流程如图3所示：
图3. 基于离散对数加密实现1-out-of-n OT
协议执行过程分为4个步骤：
- 发送方有n条消息，(代表素数域)，挑选的两个生成元，将发送给接收方。
- 假定接收方想获得第条消息，则接收方随机选择大整数，并计算，将发给发送方。
- 发送方利用，分别对条消息，重复执行图中左下角的计算步骤，每一次执行都会随机选择大整数，并结合消息计算和。然后将组发送给接收方。
- 接收方拿到组后，利用掌握的大整数，计算想要的第条消息。
- 对于第4步接收方的操作，把消息泛指为，则对的计算公式展开得到如下：
- 可以看出，要想获得消息，要么令，此时消息为接收方想要获得的消息；要么计算出，由于是发送方的秘密数字，因此保证了接收方不可能正确解密除消息之外的其余条消息。
- 对于发送方来说，虽然知道，但是不知道的情况下，由于离散对数问题难解，因此是无法推断出的正确值。
3. 不经意传输存在的性能问题
了解了OT的应用场景、功能以及原理后，我们来分析下OT存在的性能方面的问题，以下分析参考了OSU Mike教授的分享【1】。先看一种简单的实现，需要注意，该方案是一种朴素实现，仅为了方便说明OT的性能问题，帮助理解。
图4. 基于非对称加密实现1-out-of-2 OT的通信&计算代价分析
可以看到，OT 需要一定的计算通信代价， 每次 OT 都使用公钥操作（比对称密钥操作慢几个数量级）。 OT 需要公钥密码学。 安全计算一般使用成千上万次的 OT，这种代价在实际业务难以承受。
如果降低OT的成本？
想法：使用预计算
- 预先计算少量随机 OT（使用公钥密码学）
- 将这些扩展为许多常规 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生成两个随机信息，分别为，接收方持有选择比特, 通过基于公钥的OT完成离线预处理计算，即接收方获取到选择比特对应的信息，。
在线阶段：假设发送方持有的真实信息为，接收方持有选择比特，那么可以计算出，发送方使用根据对进行相应盲化，，，接收方接收到后，在接收方本地，，计算，接收方顺利拿到选择比特对应的信息。如果计算，拿到的将是一个随机数。
基于上述过程，我们已经可以实现在输入未知之前的离线阶段完成所有的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，发送方计算 ( ) , 对于每个i，接收方确切知道发送方的一个值及其位置（OT），理解了这一点，就可以理解IKNP03的OTE了，通过有限的OT过程，生成n组Random OT结果。后续利用图5介绍的方案，采用对称加密或者异或盲化可以完成大量的OT过程计算。
另外需要注意，每行使用相同的s，因此OT字符串是相关的, 需要应用哈希函数H打破相关性(如果H是随机预言机，则是安全的)。
分析一下IKNP03 OTE的消耗：
使用高而窄的矩阵（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变体、恶意敌手模型》