• 手动构建 2-选-1 不经意传输OT协议
  • 协议流程及原理
    • 加解密原理
    • 协议过程
  • 手动构建
    • 生成公私钥对
    • 接收者生成$P{K}_0$
    • 发送者加密数据
    • 接收者解密数据
  • 小结
  • 参考

手动构建 2-选-1 不经意传输OT协议

不经意传输协议(oblivious transfer, OT)是一种密码学协议，用于解决通信双方之间在信息交换中的隐私和保密性问题。OT协议能够确保发送者不知道接收者选择了哪条消息，这样保护了接收者的隐私；接收者只能获得他选择的那条消息，而无法获得其他消息，这为发送者的消息提供了保密性。

基于OT协议可以构建许多应用，尤其是在需要隐私保护和选择性信息共享的场景¹。比如在安全多方计算（SMPC）中，OT协议可以用于在多方之间进行计算，确保每个参与方只能得知其选择的相关信息，而不知道其他参与方的输入；OT协议可以用于构建零知识证明系统，确保证明者能够向验证者证明某些陈述的真实性，而不泄露额外的信息。

OT协议存在各类变体和OT扩展协议，其中包括 2-选-1 OT协议：发送者向接收者发送 2 条消息, 接收者通过 1 位选择比特能够选择性地接收其中一条消息。发送者无法确定接收者的选择比特, 而接收者对未选择消息一无所知。
本文选择Naor和Pinkas在《Efficient Oblivious Transfer Protocol》2.3节中提出的基础OT协议²进行分析并手动实现构建过程，希望能够对 2-选-1 OT协议的工作流程有一个基本的了解和认识，为实践应用做准备。

协议流程及原理

2-选-1 OT 协议有两方参与，发送者输入为$m_0,m_1$两条消息，接收者输入为选择项 σ ∈ { 0 , 1 } \sigma \in \{0, 1\} σ∈{ 0,1}，经过OT协议的运行，输出内容为接收者收到的 $m_{\sigma }$ 消息。

下面是《Efficient Oblivious Transfer Protocol》(后面简写为"Naor的协议")给出的 2-选-1 OT协议描述：

Input: The chooser’s input is $\sigma$ $\in$ {0,1}, and the sender’s input is two strings $M_0$, $M_1$.
Output: The chooser’s output is $M_{\sigma }$.
Preliminaries: The protocol operates over a group $Z_q$ of prime order. More specifically, $G_q$ can be a subgroup of order $q$ of $Z_p^{\ast }$, where $p$ is prime and $q|p-1$.
Let $g$ be a generator group, for which the computational Diffie-Hellman assumption holds. The protocol uses a funtion $H$ which is assumed to be a random oracle.
Initialization: The sender chooses a random element C $\in$ $Z_q$ and publishes it. (It is only important that the chooser will not know the discrete logarithm of $C$ to the base $g$. It is irrelevant whether the sender knows the discrete log of $C$.)
Protocol:

• The chooser picks a random 1 $\le k\le q$, sets public keys $P{K}_{\sigma }=g^k$ and $P{K}_{1-\sigma }$ = $C/P{K}_{\sigma }$, and sends $P{K}_0$ to the sender.
• The sender computes $P{K}_1$ = $C/P{K}_0$ and chooses random $r_0$, $r_1$ $\in$ $Z_q$. It encrypts $M_0$ by $E_0$ = $⟨g^{r_0},H(P{K}_0^{r_0})\oplus M_0⟩$, and encrypts $M_1$ by $E_1$ = $⟨g^{r_1},H(P{K}_1^{r_1})\oplus M_1⟩$, and sends the encryptions $E_0,E_1$ to the chooser.
• The chooser computes $H((g^{r_{\sigma }}{)}^k)$ = $H(P{K}_{\sigma }^{r_{\sigma }})$ and uses it to decrypt $M_{\sigma }$.

这个协议基于 Diffie-Hellman 假设，通过使用明文与底层 Diffie-Hellman 密钥的散列值进行异或操作，实现对消息加密。

接下来开始对Naor的协议原理和过程进行分析，看一看它是如何解决通信双方在信息交换中的隐私和保密性问题。

加解密原理

Naor协议基于 Diffie-Hellman 假设，所以首先需要准备一个大素数$p$和一个生成$g$，加解密双方共享这两个信息。解密方随机选择一个$x$作为私钥，同时生成公钥$h=g^x$给到加密方。加密方随机选择一个$k$作为私钥。
Naor协议提到的random oracle对应的中文叫做"随机预言机"，这里就可以将其等价为一个哈希函数$H$，它可以对输入字符内容或比特串生成指定长度的摘要信息。
加密过程中，加密方求得解密方的公钥$h$的$k$次幂，然后利用哈希函数$H$计算$h^k$的摘要信息，此摘要信息是与消息长度相同的比特串。然后使用这个比特串与同样长度的消息进行异或操作，以此来实现对消息进行加密。$(c_1,c_2)$构成密文发送给解密方。
$$c=(c_1,c_2)\leftarrow (g^k,m\oplus H(h^k))$$ 解密过程
$$c_2\oplus H({c_1}^x)=m\oplus H(g^{kx})=m\oplus H(h^k)=m$$ 解密方在拿到密文之后，求得对方发过来的$c_1$公钥的$x$次幂，然后与密文进行异或操作，就能够解密得到原始消息。
以上就是Naor协议中基本的加解密原理。接下来的协议过程将描述如何在这个加解密的基础上实现OT协议声明的"保护隐私和提供机密性"。

协议过程

完整协议过程可以通过下图来描述：

第1步，消息发送者准备$(G,g,C\leftarrow g^x)$三组，其中$G$为有限循环阿贝尔群，$g$是其生成，$C$由随机选定的$x$生成。

第2步，消息接收者需要创建两个公钥$P{K}_0$和$P{K}_1$,同时要求他本身只能够知道其中一个对应的私钥。接收者掌握的密钥对是通过和发送者共享的生成$g$及同余类中的随机变量$k$来决定的，即$(g^k,k)$。而另一个公钥是与最初发送者选择的$C$来共同计算生成。当接收者想要知道发送者的第 $\sigma$ 条消息的时候（ σ ∈ { 0 , 1 } \sigma \in \{0, 1\} σ∈{ 0,1}），接收者选择将自己生成的有对应私钥的公钥作为 $P{K}_{\sigma }$。另一个公钥通过 $P{K}_{1-\sigma }=C/P{K}_{\sigma }$ 生成，将这两个公钥给到发送者。当然，在真正协议过程中接收者只传输一个 $P{K}_0$，因为 $P{K}_1$ 可以由发送者进行计算得出。
这里就解释了 OT 协议如何实现发送者不知道接收者的选择，保护接收者的隐私了：如果接收者选择$\sigma =0$，他只需要将 $P{K}_0=g^k$ 计算出来给到发送者；如果接收者选择$\sigma =1$，他就再算一下 $P{K}_0=C/P{K}_1$ 给到发送者。发送者在接收到 $P{K}_0$ 之后，他无法知道接收者选择是什么。

第3步，发送者在得到$P{K}_0$和$P{K}_1$之后，将分别使用二者加密消息$M_0$和$M_1$。这里的加密原理和前面的描述一致。

Naor最初设计的协议中随机选取了$r_0$和$r_1$两个数作为私钥生成公私钥对$(g^{r_0},r_0)$和$(g^{r_1},r_1)$，然后进行了加密计算过程：
$$E_0\leftarrow (g^{r_0},M_0\oplus H(P{K}_0^{r_0}))$$ $$E_1\leftarrow (g^{r_1},M_1\oplus H(P{K}_1^{r_1}))$$

其中 $r_0,r_1\in (\mathbb{Z}/q\mathbb{Z})$。这里如果稍作变化，发送者可以使用相同的$r$值进行计算: $r=r_0=r_1$。即得到：
$$e_0\leftarrow (g^r,M_0\oplus H(P{K}_0^r))$$ $$e_1\leftarrow (g^r,M_1\oplus H(P{K}_1^r))$$

这样做可以减少一次指数幂计算，降低发送者的计算成本。同时，因为接收者只需要解密他选择的信息，所以，从安全角度讲应该是没有影响的。$e_0$和$e_1$这两个密文串将被发送给接收者。

第4步，接收者根据之前的$\sigma$值，选择对应的 $e_{\sigma }$ 进行解密。这里的解密原理和前面的描述一致。
要说明的一点是，接收者只能够解密他当时选择的那条信息。因为接收者不知道另一条加密信息的私钥，接收者无法获得关于$M_{1-\sigma }$的任何正确信息。这就是 OT 协议如何保证仅披露接收者选择的信息而实现其他信息保密的。

手动构建

以上过程描述了 2选1 基本OT协议的过程，协议本身不是很复杂，但其中用到的数学内容对于非数学出身的同学挑战不小。接下来展示如何手动构建(手算)这个协议（素数选取及消息内容都做简单处理，选取了小素数，工程实现应该选择大素数）：

生成公私钥对

1. 选择一个小素数$p$，比如这里选择 $p=11$ 得到循环群 G = Z 11 ∗ = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } G=Z_{11}^*=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\} G=Z11∗​={ 1,2,3,4,5,6,7,8,9,10}
2. 求模$p$的一个原根作为生成，$p=11$的一个生成是$g=2$
3. 从比$p$小的互素数中随机选取$x=7$，用于生成发送者初始公钥$C=g^x(mod7)=7$

接收者生成$P{K}_0$

第2步中，发送者将$C$、$g=2$和$G$的信息发送给接收者。接收者随机选择 $k=4$，因为按照约定，接收者会将$P{K}_0$发送给发送者用于后续计算，所以如果接收者选择第0条信息，直接将 $P{K}_0=g^k$ 给到发送者；如果接收者选择第1条信息，在计算 $P{K}_1=g^k$ 之后，再计算 $P{K}_0=C/P{K}_1$，将 $P{K}_0$ 给到发送者。
这里接收者选择接收第 $\sigma =1$ 条信息，$P{K}_{\sigma }=P{K}_1=g^k=2^4(mod11)=5$，$P{K}_{1-\sigma }=P{K}_0=C/P{K}_1=7/5(mod11)=8$。注意，这里计算的$P{K}_0$是通过求逆得到值。

发送者加密数据

第3步中，发送者在收到接收者发过来的$P{K}_0$之后，再次计算$P{K}_1=C/P{K}_0=7/8(mod11)=5$。到目前为止，发送者虽然拿到了$P{K}_0$和$P{K}_1$的值，但他不知道接收者的选择是什么。
发送者从$G$中选择随机选择一个 $r=6$，再次计算一个公钥$c_1=g^r=2^6(mod11)=9$。同时选择一个$H$哈希函数：

def H(pub_key, msg_length): 1. 获取公钥长度，将公钥比特长度转换为字节长度 2. 公钥转换为字节数组 3. 对公钥字节数组应用SHAKE-256哈希算法，生成msg_length长度的摘要 

操作过程中公钥哈希值要和发送者发送的消息进行异或操作，所以选择了SHAKE-256哈希算法。因为它是一种可扩展输出长度的哈希函数，可以生成不同长度的摘要。
接下来开始加密数据：
假设消息$M_0=b^{\prime }destinationisyunna{n}^{\prime }$，$M_1=b^{\prime }destinationisbeijin{g}^{\prime }$.

$P{K}_0^r=8^6(mod11)=3$
$H(P{K}_0^r,len(M_0))=H(3,21)=$b’\xdbBR3y\x00\xd8\xab\x7f`\x9d\x17\x015\xd4Y\xa6y\x89E\xd5’

$e_0$ = $M_0\oplus H(P{K}_0^r,len(M_0))=b^{\prime }destinationisyunna{n}^{\prime }$ $\oplus$ b’\xdbBR3y\x00\xd8\xab\x7f`\x9d\x17\x015\xd4Y\xa6y\x89E\xd5’ = b"\xbf’!G\x10n\xb9\xdf\x16\x0f\xf37hF\xf4 \xd3\x17\xe7$\xbb"

$P{K}_1^r=5^6(mod11)=5$
$H(P{K}_1^r,len(M_1))=H(5,22)=$b’\x8bF\x0b\xfc\xa6\xff\x17}V\x1d\n\xfc\x88=\xf6TVx\x16\xbd\x83\x14’

$e_1$ = $M_1\oplus H(P{K}_1^r,len(M_1))=b^{\prime }destinationisbeijin{g}^{\prime }$ $\oplus$ b’\x8bF\x0b\xfc\xa6\xff\x17}V\x1d\n\xfc\x88=\xf6TVx\x16\xbd\x83\x14’ = b’\xef#x\x88\xcf\x91v\t?rd\xdc\xe1N\xd663\x11|\xd4\xeds’

此时发送者将$(c_1,e_0,e_1)$发送给接收者。

接收者解密数据

接收者在收到$(c_1,e_0,e_1)$后，就开始解密数据过程了。当时接收者选择的$k=4$。因为接收者选择第 $\sigma =1$ 条消息，所以对$e_{\sigma }=e_1$进行解密。

$c_1^k=9^4(mod11)=5$
$H(c_1^k,len(e_1))=H(5,22)=$ b’\x8bF\x0b\xfc\xa6\xff\x17}V\x1d\n\xfc\x88=\xf6TVx\x16\xbd\x83\x14’

$m_{\sigma }=m_1=e_{\sigma }\oplus H(c_1^k,len(e_1))=e_1\oplus H(c_1^k,len(e_1))=$ b’\xef#x\x88\xcf\x91v\t?rd\xdc\xe1N\xd663\x11|\xd4\xeds’ $\oplus$ b’\x8bF\x0b\xfc\xa6\xff\x17}V\x1d\n\xfc\x88=\xf6TVx\x16\xbd\x83\x14’ = b’destination is beijing’

整个过程中，发送者不知道接收者选择的是$M_1$消息；接收者在解密出他选择的$M_1$消息之后，对于另外一条$M_0$消息并不知道消息内容。这也就实现了 OT 协议的目标。

小结

本文分析了《Efficient Oblivious Transfer Protocol》2.3节中提出的基础OT协议，同时以实际消息交互为例，展示了OT协议的工作过程，说明 OT 协议是如何实现：a. 消息发送者不知道接收者的选择；b. 消息接收者只能获得他选择的那条消息，而无法获得其他消息。

在实现协议的过程中，还有另外三点值得注意：

1. 本文中的基础协议以 Deffie-Hellman 假设为基础，接收者基于发送者的 $C$ 进行$P{K}_{1-\sigma }$ 计算。这一点实现了 OT 协议由"半诚实模型"向"恶意敌手模型"的改进，它限制了接收者可能出现的不遵守协议的行为（比如给到发送者两个都有对应私钥的公钥，造成接收者能够解开两条消息内容）；
2. 本文中的基础协议出现了多次指数幂计算，在工程实现的时候，大素数选择及指数幂计算将会成为主要计算开销，高效的数学库是一个选择参考；
3. 虽然文中选择的示例消息长度接近，但发送者发送消息长度的不匹配可能会影响整个OT协议通信过程，后续会跟踪相关研究方向论文。

本文只是基本的 2-选-1 不经意传输实现，未来会构建n-选-1和n-选-k的不经意传输以及一系列OT扩展协议。

参考

1. 高莹, 陈洁. 《不经意传输协议研究综述》. 软件学报 34, 期 4 (2023年): 1879.

2. Naor M, Pinkas B. 《Efficient Oblivious Transfer Protocols》. In: Proc. of the 2001 ACM SODA, 2001年, 448~457.