安全多方计算之九：不经意传输

考虑这样的场景：A意欲出售许多个问题的答案，B打算购买其中一个问题的答案，但又不想让A知道他买的哪个问题的答案。即B不愿意泄露给A他究竟掌握哪个问题的秘密，此类场景可通过不经意传输协议实现。

不经意传输(OT，Oblivious Transfer)又称健忘传输或茫然传输，由Rabin于1981年提出。不经意传输是从一个消息集合秘密获取取部分消息的方法，该协议执行完毕后，接收方知道他是否收到这个秘密，但发送方却不知道。不经意传送是密码学中的基本构件，广泛应用于比特承诺、零知识证明、安全多方计算和电子支付等协议中。

不经意传输包括：1-out-of-2不经意传输、1-out-of-n不经意传输、m-out-of-n不经意传输。

1. Blum不经意传输

Blum不经意传输又称Rabin不经意传输，该协议中发送方以50%的概率传送一个秘密(整数n nn的因数分解)给接收者，接收者有50%的机会收到这个秘密，有50%的机会什么也没有收到。

• （1）A选择形式为4 r + 3 4r+34r+3的两个个大素数，发送Blum数n = p × q n=p\times qn=p×q给B，但将p , q p,qp,q作为秘密保留。
  
• （2）B随机选取一个整数x xx，满足0 < x < n , gcd ⁡ ( x , n ) = 1 0<x<n,\operatorname{gcd}(x, n)=10<x<n,gcd(x,n)=1，即x xx是比n nn小且与n nn互素的正整数，然后发送a ≡ x 2 (   m o d   n ) a \equiv x^{2}(\bmod n)a≡x2(modn)给A。
  
• （3）A根据已知的p , q p,qp,q求出x 2 ≡ a (   m o d   p ) x^{2} \equiv a(\bmod p)x2≡a(modp)对应的2 22个根，然后A随机选择其中的一个根发送给B。
  
• （4）如果B接收到的是y yy或n − y n-yn−y，则B通过已知的x xx和接收到的y yy就可以得出p pp和q qq：gcd ⁡ ( x + y , n ) = p \operatorname{gcd}(x+y, n)=pgcd(x+y,n)=p 或 gcd ⁡ ( x + y , n ) = q \operatorname{gcd}(x+y, n)=qgcd(x+y,n)=q。若 B 接收到的是x xx或n − x n-xn−x，则B得不出n nn的任何信息。
  

2. 1-out-of-2不经意传输

O T 1 2 OT_{1}^{2}OT12不经意传输：Alice拥有两个消息M 1 , M 2 M_1,M_2M1,M2，Bob得到其中的一份消息且Alice不知道是哪一个。

方法一

• (1) Alice产生两个公开密钥/私人密钥对，共4个密钥，她把两个公开密钥发进给Bob。
  
• (2) Bob生成一个对称算法(例如DES)密钥K KK，选择Alice的一个公开密钥加密他的DES密钥K KK，发送给 Alice（但不告诉她使用的是哪个公开密钥）。
  
• (3) Alice每次使用一个她的私人密钥来解密Bob的密钥。Alice要么使用了正确的密钥并成功地解密Bob的DES密钥K KK，要么使用了错误的密钥只是产生了一堆毫无意义而看上去又像一个随机DES密钥的位K ‘ K‘K‘。由于她不知道正确明文，所以不知道哪个是正确的。
  
• (4) Alice分别使用产生的两个DES密钥加密她的两个消息，假设使用K KK加密M 1 M_1M1，使用K ‘ K‘K‘加密M 2 M_2M2，将E K ( M 1 ) , E K ′ ( M 2 ) E_{K}(M_1),E_{K'}(M_2)EK(M1),EK′(M2)发送给 Bob。
  
• (5) Bob收到一个用正确DES密钥加密的消息E K ( M 1 ) E_{K}(M_1)EK(M1)和一个用无意义DES密钥加密的消息E K ′ ( M 2 ) E_{K'}(M_2)EK′(M2)，当Bob用他的DES密钥解密每一份消息时，他能读其中之一，另一份在他看起来毫无意义。
  

此时Bob现在有了Alice两份消息中的一个（本例中是M 1 M_1M1），而Alice不知道他能读懂哪一个。

方法二

• （1)Alice选择两个随机数r 0 , r 1 r_{0}, r_{1}r0,r1，发送给Bob。
  
• （2)Bob选择一个随机数r rr，用Alice的公钥d dd加密r rr: E d ( r ) = r d E_d(r)=r^{d}Ed(r)=rd，并且选择一个随机数（假设选择r 0 r_{0}r0），计算S = r 0 + E d ( r ) S=r_0+E_d(r)S=r0+Ed(r)，发送给Alice。
  
• （3)Alice计算S 0 = S − r 0 , S 1 = S − r 1 S_{0}=S-r_{0},S_{1}=S-r_{1}S0=S−r0,S1=S−r1，并用私钥e ee解密计算D e ( S 0 ) , D e ( S 1 ) D_e(S_{0}),D_e(S_{1})De(S0),De(S1)，然后发送M 0 ′ = M 0 ⊕ D e ( S 0 ) , M 1 ′ = M 1 ⊕ D e ( S 1 ) M_{0}'=M_{0} \oplus D_e(S_{0}),M_{1}'=M_{1} \oplus D_e(S_{1})M0′=M0⊕De(S0),M1′=M1⊕De(S1) 给Bob。
  
• （4）Bob计算M 0 ′ ⊕ r , M 1 ′ ⊕ r M_{0}'\oplus r,M_{1}'\oplus rM0′⊕r,M1′⊕r，其中M 0 ′ ⊕ r = M 0 ⊕ D e ( S 0 ) ⊕ r = M 0 ⊕ D e ( S − r 0 ) ⊕ r = M 0 ⊕ D e ( r 0 + E d ( r ) − r 0 ) ⊕ r = M 0 ⊕ D e ( E d ( r ) ) ⊕ r = M 0 ⊕ r ⊕ r = M 0 \begin{aligned} M_{0}' \oplus r &= M_{0} \oplus D_e(S_{0}) \oplus r \\ &= M_{0} \oplus D_e(S-r_0)\oplus r \\ &= M_{0} \oplus D_e(r_0+E_d(r)-r_0)\oplus r \\ &= M_{0} \oplus D_e(E_d(r)) \oplus r \\ &= M_{0} \oplus r \oplus r \\ &= M_{0}\end{aligned}M0′⊕r=M0⊕De(S0)⊕r=M0⊕De(S−r0)⊕r=M0⊕De(r0+Ed(r)−r0)⊕r=M0⊕De(Ed(r))⊕r=M0⊕r⊕r=M0Bob恢复了消息M 0 M_0M0，同时Alice不知道Bob恢复的哪个消息。
  

3. 1-out-of-n不经意传输

O T 1 n OT_{1}^{n}OT1n不经意传输：Alice拥有n nn个消息( M 1 , M 2 , … , M n ) (M_{1}, M_{2}, \ldots, M_{n})(M1,M2,…,Mn)，Bob得到其中某一个M i M_{i}Mi且Alice不知道是哪一个。

系统参数：设p , q p,qp,q均为素数，p = 2 q + 1 p=2q+1p=2q+1，G q G_{q}Gq是Z P ∗ Z_{P}^{*}ZP∗的一个q qq阶子群，g , h g,hg,h为G q G_{q}Gq的两个生成元，Z q Z_{q}Zq表示模q qq的最小剩余集，协议两个参与方Alice和Bob都知道( g , h , G q ) \left(g, h, G_{q}\right)(g,h,Gq)。

• （1) Bob选择r ∈ R Z q r \in_{R} Z_{q}r∈RZq和i ( 1 ≤ i ≤ n ) i(1 \leq i \leq n)i(1≤i≤n)，计算y = g r h i   m o d   p y=g^{r} h^{i} \bmod py=grhimodp 发送给Alice;
  
• （2) Alice对所有1 ≤ j ≤ n , k j ∈ z q 1 \leq j \leq n, k_{j} \in z_{q}1≤j≤n,kj∈zq，计算a j = g k j   m o d   p , b j = M j ( y / h i ) k j   m o d   p a_{j}=g^{k_{j}} \bmod p, b_{j}=M_{j}\left(y / h^{i}\right)^{k_{j}} \bmod paj=gkjmodp,bj=Mj(y/hi)kjmodp将 ( a 1 , b 1 ) , ( a 2 , b 2 ) , … , ( a n , b n ) \left(a_{1}, b_{1}\right),\left(a_{2}, b_{2}\right), \ldots,\left(a_{n}, b_{n}\right)(a1,b1),(a2,b2),…,(an,bn) 发送给Bob;
  
• （3) Bob 计算b i / a i r   m o d   p = M i ( y / h i ) k i / a i r   m o d   p = M i ( g r h i / h i ) k i / ( g k j ) r   m o d   p = M i \begin{aligned} b_{i} /a_{i}^{r} \bmod p &= M_{i}\left(y/h^{i}\right)^{k_{i}}/a_{i}^{r} \bmod p \\ &= M_{i}\left(g^{r} h^{i}/h^{i}\right)^{k_{i}}/{(g^{k_{j}})}^{r} \bmod p \\ &= M_{i} \end{aligned}bi/airmodp=Mi(y/hi)ki/airmodp=Mi(grhi/hi)ki/(gkj)rmodp=MiBob恢复了消息M i M_iMi，同时Alice不知道Bob恢复的哪个消息。
  

m-out-of-n不经意传输

O T k n OT_{k}^{n}OTkn不经意传输：Alice有n nn个秘密，( M 1 , M 2 , … , M n ) (M_{1}, M_{2}, \ldots, M_{n})(M1,M2,…,Mn)，Bob得到其中k kk个且Alice不知道是哪一个。

通过执行k kk次O T 1 n OT_{1}^{n}OT1n协议m，来实现m-out-of-n的不经意传输。