揭秘Rabin提出的不经意传输（Oblivious Transfer）技术：秘密交换的奇妙之道

之道"/>

揭秘Rabin提出的不经意传输（Oblivious Transfer）技术：秘密交换的奇妙之道

不经意传输（Oblivious Transfer Protocol ,OT）

1 Rabin 1981，The EOS(Exchange of Secrets) Protocol

1.1 假设

假设Alice拥有公钥 K A K_A KA​、私钥 S K A SK_A SKA​和Bob拥有公钥 K B K_B KB​、私钥 S K B SK_B SKB​，这将用于加密和数字签名。Alice和Bob之间传送的消息都使用私钥签名。另外，Alice拥有秘密值 S A S_A SA​，Bob拥有秘密值 S B S_B SB​，不失一般性，假设秘密值都为单个bit。 S B S_B SB​ 是Alice想要访问某个文件的密码 (称为：Alice的文件)，而 S A S_A SA​ 则是Bob的文件。

1.2 步骤

（1）Alice选择两个大质数 p p p， q q q并创建一个一次性密钥 n A = p ⋅ q n_A = p\cdot q nA​=p⋅q，并发送 n A n_A nA​给Bob。

（2）Bob随机选择一个 x ≤ n A x \le n_A x≤nA​，并计算 c = x 2 m o d n A c=x^2\ mod\ n_A c=x2 mod nA​。然后，给Alice发送 E K B ( x ) E_{K_B}(x) EKB​​(x)和 c c c。 E K B ( x ) E_{K_B}(x) EKB​​(x)即使用公钥 K B K_B KB​对 x x x进行加密的密文， c c c是 x x x在 m o d n A mod \ n_A mod nA​下的平方根。

（3）Alice利用 p p p， q q q， n A n_A nA​计算 x 1 2 = c m o d n A x_1^2=c\ mod\ n_A x12​=c mod nA​得到 x 1 x_1 x1​。然后，发送 x 1 x_1 x1​给Bob。

（4）Bob计算 ( x − x 1 , n A ) (x-x_1, n_A) (x−x1​,nA​)的最大公因数 d d d， d d d有 1 2 \frac{1}{2} 21​的概率是 p p p或者 q q q。也就是说，Bob有 1 2 \frac{1}{2} 21​的概率可以知道因数分解 n a = p ⋅ q n_a=p \cdot q na​=p⋅q。但是，Alice并不知道Bob的 x x x的真实值，所以也不知道Bob是否知道 n A n_A nA​的分解。（为什么 d d d 有 1 2 \frac{1}{2} 21​的概率是 p p p或者 q q q见1.6.1节）

以上这种传输信息的模式，即发送者不知道接受者是否接收到信息的模式，称为不经意传输（oblivious transfer, OT）。

（5）定义：
v B = { 0 i f ( x − x 1 , n A ) = p o r q , 1 o t h e r w i s e v_B = \left\{ \begin{array}{lr} 0 & if (x-x_1,n_A)=p\ or\ q, \\ 1& otherwise \end{array} \right. vB​={01​if(x−x1​,nA​)=p or q,otherwise​
因此，当 v B = 0 v_B=0 vB​=0时当且仅当在上述不经意传输后，Bob知道了 n A n_A nA​的因数分解。

Bob计算 ϵ B = S B ⊕ v B \epsilon_B=S_B\oplus v_B ϵB​=SB​⊕vB​并发送给Alice。

（6）Alice将她的秘密值 S A S_A SA​作为中心比特放在一条随机消息 m A m_A mA​中。然后，使用任何需要因数 p p p和 q q q的公钥系统将 m A m_A mA​加密，即 d A = E n A ( m A ) d_A=E_{n_A} (m_A) dA​=EnA​​(mA​)，并发送给Bob。

同理，Alice作为接受者，Bob作为发送者，Bob收到 ϵ A \epsilon_A ϵA​，Alice收到 d B d_B dB​。

1.3 定理

以上协议执行，双方无法交换秘密值的概率为 1 4 \frac{1}{4} 41​。具体解释如下：

Alice有 1 2 \frac{1}{2} 21​的概率可以获得 n B n_B nB​的因数，Bob也有 1 2 \frac{1}{2} 21​的概率获得 n A n_A nA​的因数。

有以下四种情况：

第一，双方都不能获得相应一次性密钥的因数，故无法解密获得随机消息，也因此无法获得秘密值。

第二，Alice知道 n B n_B nB​的因数，而Bob不知道 n A n_A nA​的因数。因此，Alice可以解密获得随机消息 m B m_B mB​并因此获得秘密值 S B S_B SB​。随后，Alice将使用该秘密访问文件。Bob得知文件被访问，清楚Alice获得了 n B n_B nB​的因数，故 ϵ A = S A ⊕ v A = S A ⊕ 0 = S A \epsilon_A=S_A \oplus v_A=S_A \oplus 0 = S_A ϵA​=SA​⊕vA​=SA​⊕0=SA​。则Bob也获得了秘密值。

第三，Bob知道 n A n_A nA​的因数，Alice不知道 n B n_B nB​的因数，与二同理，最终双方可以交换秘密值。

第四，双方都获得了相应一次性密钥的因数，获得了秘密值。

1.4 安全性

（1）这一协议适用于半诚实模型，若在Alice或者Bob其中一方是恶意的，则协议无法运行。

在这里，半诚实是指协议参与方会遵守协议的执行，但是对其他方的数据好奇，想推断知道更多的信息；而恶意是指协议参与方可能不遵循协议的执行。比如说：Alice是恶意的，发送 ϵ A \epsilon_A ϵA​和 m A m_A mA​并不包含秘密值，则Bob永远无法读取自己的文件。

（2）如果协议未实现秘密交换，多轮执行该程序是不可能的。

假设协议多轮执行，一个参与者，比如Alice，可能在第一轮之后就获得了秘密值 S B S_B SB​，但故意在第二轮之后才访问她的文件。Bob在这两轮中都没有获得 n A n_A nA​，也就没有获得秘密值 S A S_A SA​。Alice在第二轮结束后访问文件，Bob无法得知是第一轮 v A = 0 v_A=0 vA​=0还是第二轮，因此可能无法访问文件。

1.5 改进

对协议进行修改，在Bob从Alice处收到 n A n_A nA​后，Bob将选择 x , y ≤ n A x,y \le n_A x,y≤nA​，并发送 x 2 m o d n A x^2\ mod\ n_A x2 mod nA​和 y 2 m o d n A y^2\ mod\ n_A y2 mod nA​给Alice，而Alice发送 x 1 m o d n A x_1\ mod\ n_A x1​ mod nA​和 y 1 m o d n A y_1\ mod\ n_A y1​ mod nA​给Bob。协议其余部分不变。

修改后，Bob将有 3 4 \frac{3}{4} 43​的概率获得 n A = p ⋅ q n_A=p \cdot q nA​=p⋅q。（ 3 4 \frac{3}{4} 43​如何求得见1.6.2节）

Alice从Bob处收到 n B n_B nB​同理。

综上，该协议不能实现秘密交换而终止协议的概率为 1 16 \frac{1}{16} 161​。

注意：这里的改善存在一个限制，超过该限制协议的增强将会失效。解释如下：

当经过协议的改进得到 P r [ v B = 1 ] ∼ 1 32 , 000 Pr[v_B=1]\sim\frac{1}{32,000} Pr[vB​=1]∼32,0001​时，有：
P r [ ϵ B = S B ] = P r [ ϵ B = S B ∣ v B = 0 ] ⋅ P r [ v B = 0 ] + P r [ ϵ B = S B ∣ v B = 1 ] ⋅ P r [ v B = 1 ] P r [ ϵ B = S B ] = 1 ⋅ ( 1 − 1 32 , 000 ) + 0 = 1 − 1 32 , 000 Pr[\epsilon _B=S_B]= Pr[\epsilon _B=S_B | v_B=0]\cdot Pr[v_B=0] +Pr[\epsilon _B=S_B | v_B=1]\cdot Pr[v_B=1] \\ Pr[\epsilon _B=S_B]= 1\cdot (1-\frac{1}{32,000})+0=1-\frac{1}{32,000} Pr[ϵB​=SB​]=Pr[ϵB​=SB​∣vB​=0]⋅Pr[vB​=0]+Pr[ϵB​=SB​∣vB​=1]⋅Pr[vB​=1]Pr[ϵB​=SB​]=1⋅(1−32,0001​)+0=1−32,0001​
备注：原论文中是 P r [ v B = 0 ] ∼ 1 32 , 000 Pr[v_B=0]\sim\frac{1}{32,000} Pr[vB​=0]∼32,0001​，个人认为是笔误。
因此，改进到一定程度， ϵ B \epsilon _B ϵB​有很大概率是 S B S_B SB​，Alice可以使用 ϵ B \epsilon _B ϵB​直接访问自己的文件，而不继续执行协议。

1.6 附录

1.6.1 为什么 d d d 有 1 2 \frac{1}{2} 21​的概率是 p p p或者 q q q？

（1）对于Alice：

Alice已知 n A = p ⋅ q n_A=p \cdot q nA​=p⋅q和Bob发送来的 c c c，求该同余式 c = x 1 2 m o d n A c=x_1^2\ mod\ n_A c=x12​ mod nA​可转化为求：
x 1 2 = c m o d p x 1 2 = c m o d q x_1^2 = c\ mod\ p \\ x_1^2 = c\ mod\ q\\ x12​=c mod px12​=c mod q
即 c c c是 p p p和 q q q的二次剩余。

构造等式获得一次同余方程组：
r 2 = x 1 2 = c m o d p ⇒ r = x 1 = c m o d p s 2 = x 1 2 = c m o d q ⇒ s = x 1 = c m o d q r^2 = x_1^2 = c\ mod\ p \Rightarrow r = x_1 = \sqrt{c}\ mod\ p\\ s^2 = x_1^2 = c\ mod\ q \Rightarrow s = x_1 = \sqrt{c}\ mod\ q\\ r2=x12​=c mod p⇒r=x1​=c ​ mod ps2=x12​=c mod q⇒s=x1​=c ​ mod q
由欧拉准则可知：对于奇质数 p p p，

a a a是模 p p p的二次剩余的充要条件为： a p − 1 2 ≡ 1 m o d p a^{\frac{p-1}{2}} \equiv 1\ mod \ p a2p−1​≡1 mod p

a a a是模 p p p的非二次剩余的充要条件为： a p − 1 2 ≡ − 1 m o d p a^{\frac{p-1}{2}} \equiv -1\ mod \ p a2p−1​≡−1 mod p

本文选取很大的质数 p p p和 q q q，故一定是奇质数。因此，有：
c p − 1 2 ≡ 1 m o d p c^{\frac{p-1}{2}}\equiv 1\ mod\ p c2p−1​≡1 mod p
代入同余方程可得：
r 2 = c = c ⋅ c p − 1 2 = c p + 1 2 = ( c p + 1 4 ) 2 m o d p r^2=c=c \cdot c^{\frac{p-1}{2}}=c^{\frac{p+1}{2}}=(c^{\frac{p+1}{4}})^2\ mod\ p r2=c=c⋅c2p−1​=c2p+1​=(c4p+1​)2 mod p
因此：
r = ± c p + 1 4 m o d p r=\pm c^{\frac{p+1}{4}}\ mod\ p r=±c4p+1​ mod p
同理，可得：
s = ± c p + 1 4 m o d q s=\pm c^{\frac{p+1}{4}}\ mod\ q s=±c4p+1​ mod q
不妨设 k = c p + 1 4 k=c^{\frac{p+1}{4}} k=c4p+1​，

则 r = ± k m o d p r = \pm k \ mod\ p r=±k mod p和 s = ± k m o d q s=\pm k\ mod\ q s=±k mod q

将其 r r r和 s s s代入同余方程组
x 1 = r m o d p x 1 = s m o d q x_1 = r\ mod\ p\\ x_1 = s\ mod\ q\\ x1​=r mod px1​=s mod q
得到四种情况：

第一， x 1 = + k m o d p x_1=+k\ mod\ p x1​=+k mod p或 x 1 = + k m o d q x_1=+k\ mod\ q x1​=+k mod q；

第二， x 1 = − k m o d p x_1=-k\ mod\ p x1​=−k mod p或 x 1 = − k m o d q x_1=-k\ mod\ q x1​=−k mod q；

第三， x 1 = + k m o d p x_1=+k\ mod\ p x1​=+k mod p或 x 1 = − k m o d q x_1=-k\ mod\ q x1​=−k mod q；

第四， x 1 = − k m o d p x_1=-k\ mod\ p x1​=−k mod p或 x 1 = + k m o d q x_1=+k\ mod\ q x1​=+k mod q。

使用中国剩余定理求解同余方程组，得 x 1 m o d n A x_1\ mod\ n_A x1​ mod nA​并发送给Bob。

（2）对于Bob：

记 d = g c d ( x − x 1 , n A ) d = gcd(x-x_1, n_A) d=gcd(x−x1​,nA​)（gcd为求最大公因数），则有：
d = g c d ( x − x 1 , n A ) = g c d ( x − x 1 , p ⋅ q ) d = gcd(x-x_1, n_A)=gcd(x-x_1, p \cdot q) d=gcd(x−x1​,nA​)=gcd(x−x1​,p⋅q)
引入一个定义：对于 0 ≤ y 1 , y 2 < n = p ⋅ q 0 \le y_1,y_2<n=p \cdot q 0≤y1​,y2​<n=p⋅q， y 1 ∼ y 2 y_1\sim y_2 y1​∼y2​表示为 y 1 2 = y 2 2 m o d n y_1^2=y_2^2\mod n y12​=y22​modn。
若 y 2 = r m o d p y_2=r\ mod\ p y2​=r mod p和 y 2 = s m o d q y_2 = s \ mod\ q y2​=s mod q，那么有 y 1 = ± r m o d p y_1=\pm r\ mod\ p y1​=±r mod p和 y 1 = ± s m o d q y_1=\pm s\ mod\ q y1​=±s mod q，即 y 1 = ± y 2 m o d p y_1=\pm y_2\ mod\ p y1​=±y2​ mod p和 y 1 = ± y 2 m o d q y_1=\pm y_2\ mod\ q y1​=±y2​ mod q。

显然，在 m o d n A mod\ n_A mod nA​下， x ∼ x 1 x\sim x_1 x∼x1​，所以有以下四种情况：

第一， x = x 1 m o d p x=x_1\ mod\ p x=x1​ mod p和 x = x 1 m o d q x=x_1\ mod\ q x=x1​ mod q；

第二， x = − x 1 m o d p x=-x_1\ mod\ p x=−x1​ mod p和 x = − x 1 m o d q x=-x_1\ mod\ q x=−x1​ mod q；

第三， x = x 1 m o d p x=x_1\ mod\ p x=x1​ mod p和 x = − x 1 m o d q x=-x_1\ mod\ q x=−x1​ mod q；

第四， x = − x 1 m o d p x=-x_1\ mod\ p x=−x1​ mod p和 x = x 1 m o d q x=x_1\ mod\ q x=x1​ mod q。

对于第一种情况，知道： x − x 1 = 0 m o d p x-x_1=0\ mod\ p x−x1​=0 mod p和 x − x 1 = 0 m o d q x-x_1=0\ mod\ q x−x1​=0 mod q。也就是说 x − x 1 x-x_1 x−x1​是由若干个 p p p和 q q q的乘积组成，因此 d = p ⋅ q d=p\cdot q d=p⋅q；

对于第二种情况，知道： x − x 1 m o d p = − 2 x 1 m o d p x-x_1\ mod\ p=-2x_1\ mod\ p x−x1​ mod p=−2x1​ mod p 和 x − x 1 m o d q = − 2 x 1 m o d q x-x_1\ mod\ q=-2x_1\ mod\ q x−x1​ mod q=−2x1​ mod q。因为 x 1 x_1 x1​是 ± k m o d p o r q \pm k \ mod\ p\ or\ q ±k mod p or q下的值，则 x 1 ≥ 0 x_1 \ge 0 x1​≥0，因此 − 2 x 1 -2x_1 −2x1​在 m o d p mod\ p mod p和 m o d q mod\ q mod q下一定小于 p p p和 q q q，不含有 p p p或者 q q q的倍数。

对于第三种情况，知道： x − x 1 = 0 m o d p x-x_1=0\ mod\ p x−x1​=0 mod p。也就是说， x − x 1 x-x_1 x−x1​是若干个 p p p的乘积组成，因此 d = p d=p d=p。

对于第四种情况，知道： x − x 1 = 0 m o d q x-x_1=0\ mod\ q x−x1​=0 mod q。也就是说， x − x 1 x-x_1 x−x1​是若干个 q q q的乘积组成，因此 d = q d=q d=q。

综上所述， d d d 有 1 2 \frac{1}{2} 21​的概率是 p p p或者 q q q。

1.6.2 3 4 \frac{3}{4} 43​如何求得?

对于Bob来说，引入 x x x和 y y y后，得知 n A = p ⋅ q n_A=p \cdot q nA​=p⋅q的选择增多，利用排列组合的思想，有：
4 + 4 + 2 + 2 4 × 4 = 3 4 \frac{4+4+2+2}{4\times 4}=\frac{3}{4} 4×44+4+2+2​=43​
进一步解释， d 1 = g c d ( x − x 1 , n A ) d_1 = gcd(x-x_1, n_A) d1​=gcd(x−x1​,nA​)或者 d 2 = g c d ( y − y 1 , n A ) d_2=gcd(y-y_1,n_A) d2​=gcd(y−y1​,nA​)有一个最大公因数是 p p p或者 q q q的都可以使Bob知道 n A n_A nA​的分解。因此， x 1 x_1 x1​有四种解的情况， y 1 y_1 y1​也有四种解的情况，两两组合 4 × 4 4 \times 4 4×4种所有的可能性，其中 x 1 x_1 x1​有两种可能使Bob得知 n A n_A nA​的分解，同理 y 1 y_1 y1​也是，两两组合中有其中一个能使Bob得知 n A n_A nA​的分解即或的关系就可以使Bob得知 n A n_A nA​的分解，那么便有分子的12种组合。

用概率的计算，可以有：
P r [ B o b k n o w s n A = p ⋅ q ] = 1 − P r [ n o t B o b k n o w s n A = p ⋅ q ] = 1 − 1 2 × 1 2 = 3 4 Pr[Bob\ knows\ n_A=p \cdot q] = 1-Pr[not\ Bob\ knows\ n_A=p \cdot q]=1-\frac{1}{2}\times \frac{1}{2}=\frac{3}{4} Pr[Bob knows nA​=p⋅q]=1−Pr[not Bob knows nA​=p⋅q]=1−21​×21​=43​

1.7 参考文献

[1] Rabin, M.O. (2005). How To Exchange Secrets with Oblivious Transfer. IACR Cryptol. ePrint Arch., 2005, 187.

[2] 王，巴德.(2022)Rabin加密原理.

[3] Rabin, M.O. (1979). DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION. Technical Report. Massachusetts Institute of Technology, USA.