Oblivious Transfer (OT)
Table of Contents
1. OT 简介
两个人（Alice 和 Bob）在玩扑克，玩一段时间后比较无聊，他们想到一个刺激的主意：
Alice 拿出两张牌，但 Bob 只能看其中的一张牌，同时 Alice 却不能知道 Bob 看了哪一张牌。
如果有一个“公正的第三方”，那这个问题很容易解决。在没有公正的第三方参与的情况下，怎么办呢？本文的主角 Oblivious Transfer (OT) 就是解决这个问题的。
2. 1–2 OT
1-2 OT 协议描述如下：
In a 1–2 oblivious transfer protocol, Alice the sender has two messages m_0 and m_1, and Bob the receiver has a bit b, and the receiver wishes to receive m_b, without the sender learning b, while the sender wants to ensure that the receiver receives only one of the two messages.
1-2 OT 协议如图 1 所示。
Figure 1: Oblivious Transfer (OT)
2.1. Even, Goldreich, and Lempel Construction
图 2（摘自 https://en.wikipedia.org/wiki/Oblivious_transfer ）描述了一个可行的 1-2 OT 协议，这个协议是 Even, Goldreich, and Lempel 在论文 A Randomized Protocol for Signing Contracts 所提出协议的一个变种。
Figure 2: 1-2 OT 协议
这个协议中，Bob 只获得了
2.2. 其它构造方式
还有其它一种构造 1-2 OT 协议的方式，如 Bellare-Micali Construction，Naor-Pinkas Construction，这里不详细介绍，可参考：
- https://crypto.stanford.edu/pbc/notes/crypto/ot.html
- Non-Interactive Oblivious Transfer and Applications, by Mihir Bellare and Silvio Micali, 1989
- Efficient Oblivious Transfer Protocols, by Moni Naor and Benny Pinkas, 2001
3. 1-n OT, k-n OT
1-2 OT 可以一般化到 1-n OT（即 Alice 拿出 n 张牌，Bob 只能看其中的一张牌，但 Alice 不知道 Bob 看的哪一张）；更进一步，还可以一般化到 k-n OT。
4. OT Extension
OT 协议的执行开销非常大。由少数几个 OT 操作扩展为很多个 OT 操作的技术称为 OT Extension。
1996 年，Beaver 在论文 Correlated Pseudorandomness and the Complexity of Private Computations 中提出第一个 OT Extension 协议，这个协议被称为 Correlated Oblivious Transfer Extension。2003 年，Ishai、Kilian、Nissim 和 Petrank 在论文 Extending Oblivious Transfers Efficiently 中提出第一个高效的 OT Extension 协议，这个协议被称为 IKNP 协议（作者名字的首字母组合）。