3.2　不经意传输

不经意传输（Oblivious Transfer，OT）是密码学里面一个非常重要的原语，它使得接收方能够不经意地获得发送方输入的某些信息，保护发送方和接收方的隐私。不经意传输是众多密码学应用的基础协议，比如安全多方计算（Secure Multi-Party Computation，MPC）、隐私集合求交（Private Set Intersection，PSI）等。Kilian[32]证明，在理论层面上，安全多方计算与不经意传输是等价的：在不借助任何其他密码学原语、不增加任何其他假设的情况下，安全多方计算可以单独由不经意传输实现，反之亦然。

不经意传输最初由Rabin[33]提出，在Rabin的协议中，发送方持有一条秘密信息（b∈{0,1}），经过一系列的协议执行，接收方以1/2的概率获取该信息，在协议过程中，接收方确定自己是否得到了正确结果，而发送方无法确定接收方是否获取了自己的信息，协议的实现是基于RSA公钥算法的。

Even等人[34]提出了2选1不经意传输（1-out-of-2 OT，写作），此时发送方有两条输入信息，而接收方能以等概率获得其中的一条，过程中确保发送方无法得知接收方获得的是哪一条信息，而接收方也无法得知另一条未获得信息的任何信息。Crépeau[35]证明，2选1不经意传输与Rabin提出的不经意传输实际上是等价的。

为了便于实际使用，研究者又提出了可选择的2选1不经意传输，即接收方具备对信息的选择能力，同时能向发送方隐藏自己做出的选择，定义可以表示成如图3.1所示形式，S表示发送方，x0、x1表示发送方持有的秘密信息，R表示接收方，b是接收方的选择位，xb是接收方收到的信息。

这样可选择的渐渐取代了原本的OT概念，因此本书中如果没有特殊说明，OT指代的都是可选择的不经意传输协议。基于2选1不经意传输的概念，研究者从增加发送方持有的秘密信息数量和增加接收方获取的秘密信息数量这两个角度出发，提出了更多形式的不经意传输协议。Brassard等人[36]将自然地推广到了n选1不经意传输（写作），即发送方持有n个秘密信息，而接收方从中选择1个并获取。在现实中还存在着n选k不经意传输（写作）的需求，即接收方从发送方持有的n个秘密信息中选择k个并获取，一种直接且可行的做法是同时执行k个协议，但其消耗会是单个协议的O(k)倍，而Naor和Pinkas[37]给出了协议的实现方式，从而极大地减小了消耗。

下面以一个生活化的例子来展示OT协议的实现。发送方S有3封密信，接收方R最终会得到其中的2封，也就是一个3选2的不经意传输协议。假设S有外观完全无法区分的3个箱子和3把锁，接收方无法打开这3把锁；而R也有2把外观无法区分的锁，发送方无法打开这2把锁。整个协议的过程如图3.2所示。

首先，发送方把3封信放进3个箱子内，并把箱子锁好，发送给接收方。

然后，接收方从发送方的3个箱子当中，选择2个，丢弃剩余的1个；将自己的2把锁也加到选择的2个箱子上，打乱次序以后送回给发送方。

接着，发送方拿到箱子以后，把自己加的2把锁给去掉，发送给接收方。

最后，接收方也去掉自己加的2把锁，最终得到所选的2封密信。

协议的正确性显而易见，接收方从3封密信中得到了2封，实现了期望的3选2。安全性从两个角度来看，红框内被丢弃的那个箱子，因为有发送方的锁，接收方无法解开，因此保证了发送方未被选信息的安全；而蓝框里，加上了接收方的锁并通过打乱送回，则能避免发送方根据回传的信息，知道接收方的具体选择，从而保证接收方选择信息的安全。

对于这样的一个现实的3选2不经意传输协议，我们以物理上的假设来保证协议的安全性：箱子在外观上不可区分，接收方无法打开发送方的锁，发送方无法打开接收方的锁。而实际的OT协议则与其他的众多密码学协议一样，建立在困难问题之上，以困难的数学问题作为“锁”，确保攻击者破解的难度。基于不同困难问题和安全性假设的OT协议不断被提出。例如，Naor和Pinkas[37]提出的应对被动攻击的OT协议与Chou和Orlandi[38]提出的应对主动攻击的OT协议。

不经意传输有一些出于特殊目的的形式，下面提到的Random OT（简称ROT）就是其中较为重要的一种，我们在图3.3中给出的具体形式。协议可以分为两种，图3.3(a)对应于前述的不可选择的OT，发送方的秘密信息是其预先提供的，而在图3.3(b)中，秘密信息则是在协议执行过程中产生的，但这两个协议具有相同的结果，即发送方持有两条秘密信息，而接收方持有一个选择比特r和相应的秘密信息。

ROT协议具有不确定性，接收方无法决定自己能够得到的信息，因此直接使用ROT协议传递信息并不方便，我们设想这样一个场景：发送方是电影提供商，在他的数据库中有若干个电影资源，用户可以用相同的价格购买其中的任何一部电影；而接收方是一个不希望发送方知道自己看了什么电影的用户。如果他们使用ROT协议来进行电影的传输，那么接收方连自己看什么电影都无法决定，这无疑是不合理的。

尽管ROT协议可能不能被直接使用，但其可以用于进行可选择的OT协议。使用进行可选择的协议的技巧最早由Beaver[39]提出。假设发送方持有的两条待发送的信息为2个比特和，而接收方希望得到信息，经过协议，发送方得到了2个比特和，接收方得到了选择比特r和。协议过程如下：接收方向发送方发送d=b⊕r；发送方在接收到d之后，向接收方发送；接收方通过计算即可还原出自己想要得到的信息。图3.4给出了这一做法的流程图。这样的转换实际上是将ROT考虑为事先得到的预计算信息，Impagliazzo和Rudich[40]指出，OT无法通过对称密码学操作实现，虽然构造和可选择的同样需要使用费时的公钥密码学技术，但由于ROT完全不依赖于具体应用的数据输入，因此可以离线地大批量生成，而在线使用时再通过转换协议进行可选择的OT协议。对于，只需要少量通信（3个比特）和轻量计算（4次异或操作）便可以获得，因此具有很强的实用性。

现实应用中往往需要大量OT，并且每个OT都需要对较长的字符串信息进行传输，但上述的OT协议都是针对极短的信息（单比特）的，并且公钥密码学操作的性能不足会导致产生OT的速度较慢，进而影响了这些应用的实用性。研究者针对OT协议的这两个缺陷做出了改进。一方面，假设我们已经有了用于传输短字符串信息的OT，那么我们可以通过标准的伪随机数生成器生成用于传输长字符串信息的OT，这一技术称为OT长度扩展；另一方面，研究者找到了对OT的实例数量进行扩展的技术，从而能够快速地得到大量OT，这一技术称为OT实例扩展，通常也简称为OT扩展。OT扩展协议只需要参与双方先进行少量的基础OT，随后使用对称密码学操作，将这些少量OT扩展为大量OT，从而极大地提高OT的生成效率。

Beaver[41]最早提出了OT扩展协议，借助单向函数（One-way Function），以少量基础OT作为种子，生成可供使用的大量OT，但这一协议的效率不高。随后，Ishai等人[42]证明OT是可以被高效扩展的，并提出了第一个高效OT扩展协议（IKNP），接收方先使用基础OT生成种子，再通过对称密码学操作和一轮通信进行扩展，这一协议也成为了后续诸多OT扩展协议的基础。Kolesnikov和Kumaresan[43]将这一在上进行扩展的协议延伸为在上进行扩展的协议。在实际应用中，使用2选1的OT传输大量短信息的做法，可以被使用n选1的OT传输少量长信息的做法代替，而n可以作为一个变量，根据实际需要传输的消息量灵活选择，实现通信量最小化。

除了这些OT扩展协议，针对特殊OT形式的扩展协议也有着广泛的应用空间，比如Correlated OT（简称COT）扩展协议。顾名思义，COT扩展协议中存在一定的相关性，具体而言，假设发送方持有m对信息(x1,0,x1,1), (x2,0,x2,1),…,(xm,0,xm,1)，接收方从每对信息中选取一条，COT扩展协议要求对于每一对信息都有xi,0⊕xi,1=Δ,i∈[m]，其中Δ是一个全局固定的偏移量。对于受这样约束的信息对，使用COT扩展协议进行传输相较于普通的OT扩展协议可以减少一定的通信量，从而提高协议性能。COT最早由Asharov等人[44]提出，这一OT的特殊形式在混淆电路中有着特别的应用。