Brief Introduction on Techniques in OT (Oblivious Transfer) and Its Extension

Contents

1. 1. Base OT (Oblivious Transfer)
   1. 1.0.1. OT with Semi-Honest Adversary
   2. 1.0.2. OT with Malicious Adversary
   3. 1.0.3. 1-out-of-n OT
   4. 1.0.4. OT is Complete for MPC

2. Random OT and Correlated OT

1. 2.0.1. ROT (Random OT)
2. 2.0.2. COT (Correlated OT)

3. OT Extension

1. 3.0.1. 一种“反向”COT
2. 3.0.2. IKNP Extension：由到
3. 3.0.3. 大杀器：VOLE

4. EnD

这里从一个较为通顺的视角去理解OT及其相关的拓展(extension)技术，包括OT, ROT, COT, IKNP OT extension，以及简单提到VOLE OT。

Ref:

Kumar, Nishant. “Techniques in OT extension.” (2020).

Bellare, Mihir, and Silvio Micali. “Non-interactive oblivious transfer and applications.” Conference on the Theory and Application of Cryptology. New York, NY: Springer New York, 1989.

Ishai, Yuval, et al. “Extending oblivious transfers efficiently.” Annual International Cryptology Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003.

Peter Scholl. “Vector Oblivious Linear Evaluation,PCGs and Correlated Randomness.“ NIST MPTC Workshop. 28 September 2023.

Base OT (Oblivious Transfer)

OT with Semi-Honest Adversary

OT是一个这样的两方安全计算问题：Sender有两个秘密消息，记为，这里是消息的长度；Receiver有一个秘密比特。如何实现，Receiver在不泄露而得到的同时，Sender不泄露？

分解来看，目标是Receiver得到他对应想要的那个消息；同时保证Sender另一个消息对于Receiver不可知，以及Receiver的选择对于Sender不可知。

已经证明，OT很难归约到一个单向函数上；否则，相当于证明了。所以OT能用对称密码（其归约到一个假设存在的单向函数）建立起来的希望很小。并且，已经证明了OT等价于密钥交换，所以实际上相当于说OT只能用公钥密码实现，不可能基于对称密码。

下面是一种基于离散对数密码实现OT的思路：

1. Sender生成一个公钥，然后发送给Receiver。

2. Receiver随机生成一对公私钥，然后利用得到；若，则发送，否则发送。记Sender收到的公钥对为。

   注意到利用得到的在离散对数的群里也是一个公钥。

3. Sender用去分别加密，得到，发送给Receiver。注意到Sender不知道哪个公钥才是Receiver的。

4. Receiver通过得到。

   这里Receiver无法得知另一个消息，因为他不知道对应的私钥（这基于离散对数问题的困难性，如果Receiver能同时知道和的私钥，即对应的离散对数，那他也能知道对应的私钥）。

拆开来说安全性：一方面，公钥加密保证了已知公钥，无法解密密文，这用以保证Receiver无法知道Sender的另一个消息；另一方面，Sender分不清和哪个才是。

OT with Malicious Adversary

注意到，上面是半诚实假设，即假设双方忠实执行协议。实际上，如果Receiver自己生成两个公私钥对，发送其中的两个公钥给Sender，他就可以利用对应的私钥解密所有Sender的消息。

OT可以在恶意模型上实现，这需要保证Receiver无法做到上面这一点。

例如，通过离散对数问题，在一个素数阶的循环群上进行，使用的生成元记为：

1. Sender随机采样，发送给Receiver。

2. Receiver随机采样整数，得到，发送给Sender。

   注意到，由于离散对数问题的困难性，从中是得不到的值的。

3. Sender得到后，计算；随机采样两个数，计算得到，然后用一个随机Oracle（记为）去加密两个消息，然后发送两组数$,$给Receiver。

   注意到，这里Sender得到了，但不知道哪个是，所以对其不可知；这里的作用是把循环群中元素拉到和消息一样的比特长度（用一个hash函数）；由于离散对数问题的困难性，Receiver收到这两组数之后，无法求解得到其中的。

4. Receiver计算从而得到（注意到）。

   关于另一条被加密的消息的安全性，其加密所用的随机Oracle种子是，求解这个值是困难的（这基于Diffie-Hellman假设，即假如已知，求解是困难的）；同时注意到，除非恰好等于（概率极低），否则是作为这个素数阶循环群的生成元的，那么的可能取值范围等同于这个群元素的数量。

在读论文查资料的多次中发现，在89年Bellare-Micali原文中使用的并不是一个素数阶的群，而只是，所以原文中随机数如的取值范围为到，因为生成元的阶为而不是。同时，使用这个群也没法保证是生成元，从而存在落入一个小的子群而被攻击的可能。而素数阶的循环群可以解决这个问题（因为非单位元都是生成元），较新的大多数资料和论文也都是基于素数阶的循环群讨论这个协议。

1-out-of-n OT

上面介绍的称之为1-out-of-2 OT，可以进一步地实现1-out-of-n OT，即Sender有的消息，记为，然后Receiver从中选一个。在半诚实假设的情况下，这可以简单地用次1-out-of-2 OT实现。比如在第次Sender发送他的给Receiver，然后Receiver在其中选择他所需要的；但这无法防止一个恶意的Receiver窃取其他消息。

一个可能恶意的Receiver的情况下，也可以构建安全的1-out-of-n OT。实际上可以拓展一下上面所述的Bellare-Micali协议，只需要将其中的两对公钥相应拓展为个。另一种方式是借用次任意的黑盒1-out-of-2 OT实现，只需要每次发送下面的消息：

$$(r_0, x_0)\\ (r_1, r_0\oplus x_1)\\ \cdots\\ (r_i, r_0\oplus r_1\oplus \cdots\ r_{i-1}\oplus x_i)\\ \cdots\\ (r_{n-1}, r_0\oplus r_1\oplus\cdots r_{n-2}\oplus x_{n-1})$$

Receiver解开某个必须要得知之前所有的随机数，这样他就无法得知前面的消息；同时，拿到这个也就意味着拿不到，也就得不到后面的消息。

OT is Complete for MPC

OT应该怎么用呢？乍一眼看起来它所实现的并不是一个很通用的功能。实际上，OT已经被证明对于MPC(Multi-Party Computation)是完备的，也就是说OT可以用来算任何电路。最朴素的一个方法是：设这个电路的真值表有个bit输入，个比特输出，这个电路每一个输出比特的计算，都可以用一个1-out-of- OT来实现。

---

可以看到，1-out-of-2 OT是构成安全计算的一个基本单元，下面我们就关注这个问题。

Random OT and Correlated OT

ROT (Random OT)

所谓ROT即是Sender发送的两个消息是（伪）随机消息的情况（记为）。

如果我们需要次发送比特的OT（记为），我们可以通过次发送比特的ROT实现（记为）；只需要每次OT基于一个ROT来实现即可。比如先进行一次ROT，Sender发送，Receiver的选择是；然后Sender发送两条加密消息，Receiver使用对应的解密即可获得对应的消息。

上面的例子需要ROT和后续消息发送基于一样的Receiver选择，实际上可以基于不同的Receiver选择实现；这样可以将计算量大的公钥加密提前到双方各自的输入被决定前进行。实现的方式也很简单，假如ROT阶段的Receiver随机使用一个选择，在实际发送消息阶段，Receiver再发一个给Sender；如果是1，说明Receiver选择变了，Sender调换一下消息的顺序，变为，否则不变。注意这里并不会泄露或，Sender仅仅通过看不出Receiver每次具体的选择是什么。

COT (Correlated OT)

实际上上述的从OT转化到ROT，并没有降低问题的复杂度（但可以将公钥密码的计算提前）。这里我们接着将ROT转化为COT，后者可以将转化为，其中是安全参数，例如128；对于发送长消息来说，可以实现的效果。

COT也是一种Sender发送消息的特殊类别，即两条消息是correlated，而不是互相独立的；一种常见的情况是，Sender不是发送两个独立的随机消息，而是；其中是随机比特串，是某个常量，他们都是比特的消息。Sender的两条关联消息以及Receiver收到的那个消息，可以再经由一个随机Oracle把消息从比特拉到比特即可；这个Oracle是一个对correlated输入鲁棒的hash函数/伪随机生成器。

如果仔细观察上述的COT，似乎这里所用的correlated输入并无必要；使用ROT传输两条比特的消息，然后用某种hash函数拓展到比特也能实现上述功能。但是实现COT所依赖的条件更少，这意味着OT可以依赖“更少的”随机性来实现，即Sender不需要保证两条消息是互相独立的。例如，我们再观察一下上面详细讨论过的OT协议，其中发送的，实际上就是一种COT；注意到是公开的，只有以及两条消息的顺序是私有的，这依然能够实现OT。

除此之外，由于这一点，实际上构造COT会比构造ROT更易实现，即COT可以通过更高效的密码原语来做；例如VOLE, Vector Oblivious Linear Evaluation（后文会简略介绍）。

---

上文核心就是，OT可以转化为ROT，ROT可以转化为更易实现的COT，所以如果我们能安全地、低成本地构造COT，我们就能对应实现OT。

OT Extension

上面说到，已经证明OT只能基于一个困难问题构建，而不能仅凭单向函数实现。但可以基于少量的这样的基于公钥的Base OT，然后利用单向函数将其拓展为大量的OT，称之为OT Extension。其中最经典的一个方法便是IKNP Extension (IKNP没有什么特别含义，就是论文作者首字母组合) ，能做到将通过实现。

一种“反向”COT

假设Sender拥有私有的，Receiver拥有私有的；考虑这样一个COT：Sender的消息对是。注意到这个COT的性质：对于Sender而言，这个消息对可能是或者；对于Receiver而言，无论的取值，它获取到的一直是，并且对于他是未知的。

但是如何实现这样的COT呢？我们无法让Sender来决定这个消息对，因为需要保证和不泄露。这里我们考虑一种“反向”的COT：

1. Receiver先随机采样得到，然后让Receiver作为发送方，逐比特地用OT发送消息给Sender。
2. Sender作为OT的接收方用作为自己的选择；于是Sender收到的每个比特就是，次OT接收到的比特拼起来，也就是，另一个消息可以通过计算得到。

这样就实现了具有上述性质的COT。Sender具有，且不知道消息的顺序（也就是不知道和）；Receiver得到Sender消息中的，且不知道另一个消息（因为对其未知）。

IKNP Extension：由到

注意到上面的COT实际上是次传递比特消息的OT（即），只需要将传递消息的长度拓展到来进行批量传递，也就是进行：

• 也就是Receiver有对这样的和，这里重新定义为（注意到这里的是比特的了）；
• 次OT中，Receiver作为发送方的消息对是，然后Sender作为OT接收方用的每一位作为选择，和上面一样。

经过次OT，Sender会收到个长度比特串，只需要将每个比特串对应位置的比特取出来，拼接在一起，即会得到个长度为的比特串，即。

下面将这个过程写出来直观说明一下，为了简洁，这里用表示Sender收到的每个比特，即第次OT收到的比特串中的第位，Sender收到的这个比特串是:

$$q_{0,0}||q_{1,0}||\cdots||q_{m-1,0}\\ q_{0,1}||q_{1,1}||\cdots||q_{m-1,1}\\ \cdots\\ q_{0,k-1}||q_{1,k-1}||\cdots||q_{m-1,k-1}$$

看成一个比特矩阵，每一列取出来就是：

$$r_0\oplus b_0\Delta =q_{0,0}||q_{0,1}||\cdots||q_{0,k-1}\\ r_1\oplus b_1\Delta =q_{1,0}||q_{1,1}||\cdots||q_{1,k-1}\\ \cdots\\ r_{m-1}\oplus b_{m-1}\Delta =q_{m-1,0}||q_{m-1,1}||\cdots||q_{m-1,k-1}$$

和上面一样，再加上一个就会得到。

这样，经过这种“反向”的，结果上，我们实现了：Sender得到对比特的消息，重新记为，并且他们对于关联；然后Receiver拥有其中一个消息，重新记为。

再故技重施，用一个随机Oracle将这些比特的消息，拉到比特，就实现了。

---

再捋一下IKNP如何拓展OT：基于少量（次）Base OT实现大量（次）OT的问题转化过程是。实际上可以进一步优化的开销（也就是的开销）到，一个简单的想法是：我们不必使用长度的Base OT来实现上述的每次COT，我们可以事先用传输随机长度为的比特串，然后故技重施，用随机Oracle将其拉到比特来实现，用这个来实现（记得OT和ROT可以互相转化，当然，需要一次额外的发送一对比特串的交互）。

大杀器：VOLE

IKNP曾一度是最优的OT Extension，直到最近几年一系列基于VOLE的OT Extension的出现。

VOLE (Vector Oblivious Linear Evaluation)实现的是Sender拥有，而Receiver有。注意到，VOLE可以看作一种COT，例如当的时候，它的运算变成了我们熟悉的模样（加和乘即是异或和与）；Sender发送的消息对即是，Receiver得到其中之一。

相比于IKNP，基于VOLE的OT能够带来非常显著的好处：IKNP的通信量是关于总的OT的数量线性增长的，而VOLE可以在一次性的VOLE Setup之后，借助PCG(Pseudorandom Correlation Generator)无需交互而拓展得到大量低成本OT（这种特性就是silent）。

这些技术的具体构造这里不再阐述，超出本文范围（最重要的是，我还没具体看这方面的内容）。

EnD

如果能够坚持读完本文，（再问一问大模型），相信已经能够对OT及其相关技术（至少到IKNP为止）有一个虽不全面但是通畅的理解了。