不经意传输

  • 1. Blum不经意传输
  • 2. 1-out-of-2不经意传输
    • 方法一
    • 方法二
  • 3. 1-out-of-n不经意传输
    • m-out-of-n不经意传输

考虑这样的场景: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%的概率传送一个秘密(整数 nnn的因数分解)给接收者,接收者有50%的机会收到这个秘密,有50%的机会什么也没有收到。

  • (1)A选择形式为 4 r + 34r+34r+3的两个个大素数,发送Blum数 n = p × qn=p\times qn=p×q给B,但将 p , qp,qp,q作为秘密保留。

  • (2)B随机选取一个整数 xxx,满足 0 < x < n , gcd ⁡ ( x , n ) = 10<x<n,\operatorname{gcd}(x, n)=10<x<n,gcd(x,n)=1,即 xxx是比 nnn小且与 nnn互素的正整数,然后发送 a ≡ x2( m o d   n )a \equiv x^{2}(\bmod n)ax2(modn)给A。

  • (3)A根据已知的 p , qp,qp,q求出 x2≡ a ( m o d   p )x^{2} \equiv a(\bmod p)x2a(modp)对应的 222个根,然后A随机选择其中的一个根发送给B。

  • (4)如果B接收到的是 yyy n − yn-yny,则B通过已知的 xxx和接收到的 yyy就可以得出 ppp qqq 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 接收到的是 xxx n − xn-xnx,则B得不出 nnn的任何信息。

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

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

方法一

  • (1) Alice产生两个公开密钥/私人密钥对,共4个密钥,她把两个公开密钥发进给Bob。

  • (2) Bob生成一个对称算法(例如DES)密钥 KKK,选择Alice的一个公开密钥加密他的DES密钥 KKK,发送给 Alice(但不告诉她使用的是哪个公开密钥)。

  • (3) Alice每次使用一个她的私人密钥来解密Bob的密钥。Alice要么使用了正确的密钥并成功地解密Bob的DES密钥 KKK,要么使用了错误的密钥只是产生了一堆毫无意义而看上去又像一个随机DES密钥的位 K ‘K‘K。由于她不知道正确明文,所以不知道哪个是正确的。

  • (4) Alice分别使用产生的两个DES密钥加密她的两个消息,假设使用 KKK加密 M1 M_1M1,使用 K ‘K‘K加密 M2 M_2M2,将 EK( M1) , E K ′( M2)E_{K}(M_1),E_{K’}(M_2)EK(M1),EK(M2)发送给 Bob。

  • (5) Bob收到一个用正确DES密钥加密的消息 EK( M1)E_{K}(M_1)EK(M1)和一个用无意义DES密钥加密的消息 E K ′( M2)E_{K’}(M_2)EK(M2),当Bob用他的DES密钥解密每一份消息时,他能读其中之一,另一份在他看起来毫无意义。

此时Bob现在有了Alice两份消息中的一个(本例中是 M1 M_1M1),而Alice不知道他能读懂哪一个。

方法二

  • (1)Alice选择两个随机数 r0, r1 r_{0}, r_{1}r0,r1,发送给Bob。

  • (2)Bob选择一个随机数 rrr,用Alice的公钥 ddd加密 rrr: Ed( r ) = rd E_d(r)=r^{d}Ed(r)=rd,并且选择一个随机数(假设选择 r0 r_{0}r0),计算 S = r0+ Ed( r )S=r_0+E_d(r)S=r0+Ed(r),发送给Alice。

  • (3)Alice计算 S0= S − r0, S1= S − r1 S_{0}=S-r_{0},S_{1}=S-r_{1}S0=Sr0,S1=Sr1,并用私钥 eee解密计算 De( S0) , De( S1)D_e(S_{0}),D_e(S_{1})De(S0),De(S1),然后发送 M0′= M0⊕ De( S0) , M1′= M1⊕ De( S1)M_{0}’=M_{0} \oplus D_e(S_{0}),M_{1}’=M_{1} \oplus D_e(S_{1})M0=M0De(S0),M1=M1De(S1) 给Bob。

  • (4)Bob计算 M0′⊕ r , M1′⊕ rM_{0}’\oplus r,M_{1}’\oplus rM0r,M1r,其中 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} M0r=M0De(S0)r=M0De(Sr0)r=M0De(r0+Ed(r)r0)r=M0De(Ed(r))r=M0rr=M0Bob恢复了消息 M0 M_0M0,同时Alice不知道Bob恢复的哪个消息。

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

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

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

  • (1) Bob选择 r ∈RZq r \in_{R} Z_{q}rRZq i ( 1 ≤ i ≤ n )i(1 \leq i \leq n)i(1in),计算 y = grhi  m o d   py=g^{r} h^{i} \bmod py=grhimodp 发送给Alice;

  • (2) Alice对所有 1 ≤ j ≤ n , kj∈ zq 1 \leq j \leq n, k_{j} \in z_{q}1jn,kjzq,计算 a j= g kj mod  p, b j= M j (y/ h i)kj mod  pa_{j}=g^{k_{j}} \bmod p, b_{j}=M_{j}\left(y / h^{i}\right)^{k_{j}} \bmod p aj=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  mod  p = M i (y/ h i)ki / a i r  mod  p = M i ( g r h i/ h i)ki / ( g kj )r  mod  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恢复了消息 Mi M_iMi,同时Alice不知道Bob恢复的哪个消息。

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

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

通过执行 kkk O T1n OT_{1}^{n}OT1n协议m,来实现m-out-of-n的不经意传输。