PSI系列（2）组件 | OT Extension (IKNP)

1

简介

不经意传输（Oblivious Transfer，OT）作为安全多方计算中最基础的组件，单论其功能来说十分简洁。1-out-of-2 OT的标准定义涉及两方：发送方持有两个值，接收方会选择一个比特。OT协议执行后，可以得到，但不能获知的值，而并不知道选择的比特。在OT协议中，一方拥有全部的数据权限，另一方拥有单个数据的选择权，数据交换在不经意间完成，同时保证了双方私有数据的隐秘性，这便是OT带给我最直观的感受。有一种基于公钥的半诚实安全OT协议框架[1]，原理如下：

1. 生成一个公私钥对，并从公钥空间中随机选取一个公钥。若，将发送给；若，将发送给。
2. 接受到并将密文对

   发给R。
   

3. 使用私钥解密得到。

很明显，根据来放置的位置，从而使得私钥能够顺利解密对应位置的密文得到。这个框架是易于理解的，但我们现在有一个新的问题，如果需要执行大量1-out-of-2 OT协议，带来的公钥开销会非常大，我们需要一个办法降低公钥密码学的操作数量。Ishai等人[2]提出的OT Extension便是能够解决这一问题的高效协议。
2

参数说明：执行次1-out-of-2 OT实例，其中。（这是我们的最终目标）：正整数集合。随机预言机。：，即个OT实例的输入汇集在一起。 ：由个选择比特构成的向量，表示在第次OT实例中选择。对于矩阵，表示的第行向量，表示的第列向量，表示的第行第列元素。对于二元向量和， 。对于单个比特和二元向量，
3

IKNP目标：使用实现（），即用少量OT协议实现超大量OT协议。协议：1. 会随机选取向量，随机生成一个大小为的01矩阵。 2. 两方调用，其中作为发送方提供输入，作为接收方提供输入。我们现在慢慢来看这一步的操作，在第次OT的输入包括两部分，第一部分为矩阵的第列，第二部分为为矩阵的第列异或上选择向量。为了方便说明（IKNP中并不需要额外创建新矩阵），我们可以把每次OT的第二部分都抽出来组成一个新矩阵，我们记为，如图1所示。既然每一列都与的对应列有关，那么的行又与有什么关系呢？图 1我们以第行为例，对于，有。若，则；若，则。简单地说就是，矩阵的第行要么和矩阵的第行一样，要么可以由矩阵的第行每位取反来得到。例子如图2所示。图 23. 会将次OT得到的结果合并成一个的矩阵。从上帝视角来看，会根据选择是等于还是，因此很容易得到一个结论，中的每一位要么来自，要么来自。图 3先回顾一下OT extension的目标，是使用实现，现在已经做完了，后续要做的是将发送方的隐私输入借助有行的矩阵不经意地发送给接收方。那我们看看这个矩阵有什么特点，我们关注的第行：如果，那么由于，所以不管的每一位到底是0还是1，都满足。如果，对于，有（选矩阵，选矩阵），因此可以推出。综上，我们将两种情况合并可得。
4. 对于，发送给，其中，
5. 对于，计算。若，若，
整个协议相当于通过次OT约定了组对称密钥，只会等于二者之一，也就只能根据选择的比特位解密对应的加密消息。
4

参考文献[1]:Evans D, Kolesnikov V, Rosulek M. A pragmatic introduction to secure multi-party computation[J]. Foundations and Trends® in Privacy and Security, 2018, 2(2-3): 70-246.

[2]:Ishai Y, Kilian J, Nissim K, et al. Extending Oblivious Transfers Efficiently[C]//Crypto. 2003, 2729: 145-161.

本文来源：https://zhuanlan.zhihu.com/p/619066899

作者简介：林中允，华东师范大学软件工程学院密码与网络安全系研究生，主要研究方向为多方隐私集合求交。知乎：@云波随风尽

END

往期推荐

1.全同态加密知识体系整理(下)
2.联邦学习安全聚合：基于安全多方计算的经典方案3.PSI系列（1）组件 | Cuckoo Hashing4.全同态加密知识体系整理(上)