OT协议介绍

MPC 协议中的两个关键技术是 OT（oblivious transfer）协议和秘密分享。这里先介绍 OT 协议，以参考文献 1 中的基础 1-out-of-2 OT 协议为样例。

OT 协议模型的参与角色包括发送者 sender 和接收者 chooser。其功能描述如下：发送者提供两个消息 $M_0$ 和 $M_1$，接收者根据输入比特 b∈{0,1}b \in \{0,1\}b∈{0,1} 选择接收 $M_b$。安全要求是 sender 无法获知 chooser 的 $b$ 值，chooser 无法获知 $M_{1-b}$ 的内容。也就是说，当 $b=0$ 时只能获取 $M_0$，无法获取 $M_1$；对 sender 来说也无法知道 chooser 获取的是 $M_0$ 还是 $M_1$。

下面介绍 OT 协议安全模型中的难题假设（primitive）。

离散对数相关难题（CDH/DDH）通常定义在大素数模数下的循环群上。记群为 ${\mathbb{Z}}_q^{\ast }$，生成元为 $g$。任选群元素指数 $a$，令 $m=g^a$；给定 $g,m$ 时不存在已知多项式时间算法恢复 $a$。判定 Diffie-Hellman（DDH）问题是：均匀随机选择 $a,b,c$，判断下面两个三元组是否可区分：

$$(g^a,g^b,g^{ab})$$

和

$$(g^a,g^b,g^c)$$

OT 协议的安全模型中还会用到随机预言机 Random Oracle（RO）。RO 对任意输入返回均匀随机输出，且对同一输入返回值保持一致。工程实现中常用哈希函数（如 SHA-256）近似实现 RO。

两轮 OT 协议可分为 4 个阶段（随机选择均指从 ${\mathbb{Z}}_q^{\ast }$ 中均匀选择，对数运算在对应群中进行）。

1. 阶段1：Setup

Sender 随机选择 $x$，计算

$$C=g^x$$

并将 $C$ 公开给 chooser。

2. 阶段2：Round1

Chooser 随机选择 $k$，计算

PKb=gk,PK1−b=CPKb,b∈{0,1} PK_b=g^k,\quad PK_{1-b}=\frac{C}{PK_b},\quad b\in\{0,1\} PKb​=gk,PK1−b​=PKb​C​,b∈{0,1}

并将与其选择对应的公钥信息发送给 sender（协议上 sender 可由 $C$ 和一个公钥恢复另一个公钥）。

3. 阶段3：Round2

1. Sender 输入两个消息集合

{M0, M1} \{M_0,\ M_1\} {M0​, M1​}

2. Sender 随机选择 $r_0,r_1$，计算

$$R_0=g^{r_0},R_1=g^{r_1}$$

以及加密密钥

$$K_0=P{K}_0^{r_0},K_1=P{K}_1^{r_1}$$

3. 通过哈希函数构造密文：

$$E_0=H(K_0)\oplus M_0,E_1=H(K_1)\oplus M_1$$

4. Sender 发送

$$(R_0,R_1,E_0,E_1)$$

给 chooser。

4. 阶段4：提取消息

Chooser 使用阶段 2 中的 $k$ 计算恢复密钥

$$K_b=R_b^k$$

并恢复消息

$$M_b=H(K_b)\oplus E_b$$

协议正确性分析

1. 当 $b=0$（chooser 选择 $M_0$）时：

$$P{K}_0=g^k,P{K}_1=\frac{C}{g^k}$$

Sender 在阶段 3 计算

$$K_0=P{K}_0^{r_0}=g^{k{r}_0},K_1=P{K}_1^{r_1}=\frac{C^{r_1}}{g^{k{r}_1}}$$

Chooser 在阶段 4 有

$$R_0^k=(g^{r_0}{)}^k=g^{r_{0}k}=K_0$$

因此可解出 $M_0$；而对 $M_1$ 对应密钥无法正确匹配。

2. 当 $b=1$（chooser 选择 $M_1$）时：

$$P{K}_0=\frac{C}{g^k},P{K}_1=g^k$$

Sender 在阶段 3 计算

$$K_0=P{K}_0^{r_0}=\frac{C^{r_0}}{g^{k{r}_0}},K_1=P{K}_1^{r_1}=g^{k{r}_1}$$

Chooser 在阶段 4 有

$$R_1^k=(g^{r_1}{)}^k=g^{r_{1}k}=K_1$$

因此可解出 $M_1$；而对 $M_0$ 无法正确恢复。

MPC 协议中的秘密分享及混淆电路方案中都会使用 OT 协议。上面介绍的是最基本的 1-out-of-2 OT。实际上 OT 的研究非常丰富：从功能上的 1-out-of-2 到 1-out-of-$N$，安全模型从 stand-alone 下的 RO 到 UC 下的 GRO、GPRO 等。详情可参考 IACR 最新 OT 相关论文。

参考文献

1. Efficient oblivious transfer protocols. Moni Naor, Benny Pinkas.
2. Efficient and Round-Optimal Oblivious Transfer and Commitment with Adaptive Security. Ran Canetti, Pratik Sarkar, Xiao Wang.