小结"/>
安全多方计算——不经意/茫然传输（Oblivious Transfer）构造方法小结
目录
- OT简介
- 概念
- 安全多方计算
- Yao's Two-Party Protocol
- 混淆电路
- 安全两方计算协议
- 构造方法
- Bellare-Micali（1990）
- 预备知识
- A simple Scheme
- A More Secure Scheme
- 2 out of 3 Non-Interactive OT
- Non-Interactive OT of More Bits: OT Channels
- 附录A：非交互式零知识证明
- Naor-Pinkas（2001）
- 预备知识
- A single 1-out-of-2 oblivious transfer
- O T 1 N OT_1^N OT1N with amortized complexity of a single exponentiation
- Bandwidth/Complexity tradoff for O T 1 2 OT_1^2 OT12
- How to avoid random oracles
- Y. Lindell（2008）
- Oblivious Transfer Under the DDH Assumption
- Oblivious Transfer from Homomorphic Encryption
- Hazay-Lindell（2010）
OT简介
概念
OT——Oblivious Transfer，不经意传输，也叫茫然传输，是一个密码学协议，消息发送者从一些待发送的消息中发送一部分给接收者，但不知道发送了哪部分消息（对发送者的隐私性），接收者也只能获得那部分消息，而不能获得其他消息的任何信息（对接收者的隐私性）。
另外有一种以概率传输，消息发送者发送一条消息，接收者以1/2的概率获得该消息，发送者不知道接收者是否获得了该消息，只有接收者知道它确实获得了该消息。
将不经意传递函数形式化定义为一个具有两个输入和一个输出的函数 f f f。第一个输入是对 ( m 0 , m 1 ) (m_0, m_1) (m0,m1)，第二个输入是位 σ \sigma σ. 输出是串 m σ m_\sigma mσ。 P 1 P_1 P1，也称为发送方，输入 ( m 0 , m 1 ) (m_0, m_1) (m0,m1)，不接收输出。相反， P 2 P_2 P2，也称为接收方，输入位 σ \sigma σ，接收输出 m σ m_\sigma mσ。形式上写为 f ( ( m 0 , m 1 ) , σ ) = ( λ , m σ ) f((m_0, m_1), \sigma)=(\lambda, m_\sigma) f((m0,m1),σ)=(λ,mσ)，其中 λ \lambda λ表示空串。换句话说，在不经意传输函数中， P 1 P_1 P1不接收输出，而 P 2 P_2 P2接收 m σ m_\sigma mσ且对 m 1 − σ m_{1-\sigma} m1−σ。
协议 0 0 0：（半诚实模型）
- 输入： P 1 P_1 P1有 x 0 , x 1 ∈ { 0 , 1 } x_0, x_1\in \{0, 1\} x0,x1∈{0,1}， P 2 P_2 P2有 σ ∈ { 0 , 1 } \sigma\in\{0, 1\} σ∈{0,1}
- 协议：
- P 1 P_1 P1随机选取一个陷门置换 ( f , t ) (f, t) (f,t)，将 f f f（不是 t t t）发送给 P 2 P_2 P2。
- P 2 P_2 P2在 f f f的定义域中选择随机数 v σ v_\sigma vσ计算 w σ = f ( v σ ) w_\sigma=f(v_\sigma) wσ=f(vσ)。另外，选择随机数 w 1 − σ w_{1-\sigma} w1−σ，然后将 ( w 0 , w 1 ) (w_0, w_1) (w0,w1)发送给 P 2 P_2 P2。
- P 1 P_1 P1用陷门 t t t计算 v 0 = f − 1 ( w 0 ) , v 1 = f − 1 ( w 1 ) v_0=f^{-1}(w_0), v_1=f^{-1}(w_1) v0=f−1(w0),v1=f−1(w1)，然后计算 b 0 = B ( v 0 ) ⊕ x 1 b_0=B(v_0)\oplus x_1 b0=B(v0)⊕x1，其中 B B B是 f f f中的困难比特（hard-core bit）。将 ( b 0 , b 1 ) (b_0, b_1) (b0,b1)发送给 P 2 P_2 P2。
- P 1 P_1 P1计算 x σ = B ( v σ ) ⊕ b σ x_\sigma=B(v_\sigma)\oplus b_\sigma xσ=B(vσ)⊕bσ并输出 x σ x_\sigma xσ。
目前常被用于安全多方计算中。
安全多方计算
下述摘抄自yuxinqingge的博客，读者可移步进行更详细的了解。
安全多方计算理论主要研究参与者间协同计算及隐私信息保护问题，其特点包括输入隐私性、计算正确性及去中心化等特性。
- 输入隐私性：安全多方计算研究的是各参与方在协作计算时如何对各方隐私数据进行保护，重点关注各参与方之间的隐私安全性问题，即在安全多方计算过程中必须保证各方私密输入独立，计算时不泄露任何本地数据。
- 计算正确性：多方计算参与各方就某一约定计算任务，通过约定MPC协议进行协同计算，计算结束后，各方得到正确的数据反馈。
- 去中心化：传统的分布式计算由中心节点协调各用户的计算进程，收集各用户的输入信息，而安全多方计算中，各参与方地位平等，不存在任何有特权的参与方或第三方，提供一种去中心化的计算模式。
Yao’s Two-Party Protocol
混淆电路
下述混淆电路的构造。
令 C C C是一个布尔电路，接收两个输入 x , y ∈ { 0 , 1 } n x, y\in\{0, 1\}^n x,y∈{0,1}n，输出 C ( x , y ) ∈ { 0 , 1 } n C(x, y)\in\{0, 1\}^n C(x,y)∈{0,1}n（为了简化，假设输入、输入、安全参数的长度都为 n n n）。如果电路输出线来自门 g g g，门 g g g就没有其他线输入到其他门；同理，如果电路输入线也是电路输出线，那么它不输入任何门。
从单个门 g g g的混淆电路 C C C讲起。电路 C C C是布尔型，因此门可以表示为函数 g : { 0 , 1 } × { 0 , 1 } → { 0 , 1 } g: \{0, 1\}\times\{0, 1\}\rightarrow\{0, 1\} g:{0,1}×{0,1}→{0,1}，记两个输入线为 w 1 , w 2 w_1, w_2 w1,w2，输出线记为 w 3 w_3 w3， k 1 0 , k 1 1 , k 2 0 , k 2 1 , k 3 0 , k 3 1 k_1^0, k_1^1, k_2^0, k_2^1, k_3^0, k_3^1 k10,k11,k20,k21,k30,k31是调用密钥生成算法 G ( 1 n ) G(1^n) G(1n)得到的6个密钥，假设其长度均为 n n n。希望从 k 1 α k_1^\alpha k1α和 k 2 β k_2^\beta k2β中计算出 k 3 g ( α , β ) k_3^{g(\alpha, \beta)} k3g(α,β)而不暴露其他三个值 k 3 g ( 1 − α , β ) , k 3 g ( α , 1 − β ) , k 3 g ( 1 − α , 1 − β ) k_3^{g(1-\alpha, \beta)}, k_3^{g(\alpha, 1-\beta)}, k_3^{g(1-\alpha, 1-\beta)} k3g(1−α,β),k3g(α,1−β),k3g(1−α,1−β)的信息。门 g g g被四个值定义： c 0 , 0 = E k 1 0 ( E k 2 0 ( k 3 g ( 0 , 0 ) ) ) c_{0, 0}=E_{k_1^0}(E_{k_2^0}(k_3^{g(0, 0)})) c0,0=Ek10(Ek20(k3g(0,0)))， c 0 , 1 = E k 1 0 ( E k 2 1 ( k 3 g ( 0 , 1 ) ) ) c_{0, 1}=E_{k_1^0}(E_{k_2^1}(k_3^{g(0, 1)})) c0,1=Ek10(Ek21(k3g(0,1)))， c 1 , 0 = E k 1 1 ( E k 2 0 ( k 3 g ( 1 , 0 ) ) ) c_{1, 0}=E_{k_1^1}(E_{k_2^0}(k_3^{g(1, 0)})) c1,0=Ek11(Ek20(k3g(1,0)))， c 1 , 1 = E k 1 1 ( E k 2 1 ( k 3 g ( 1 , 1 ) ) ) c_{1, 1}=E_{k_1^1}(E_{k_2^1}(k_3^{g(1, 1)})) c1,1=Ek11(Ek21(k3g(1,1)))，其中 E E E是私钥加密方案 ( G , E , D ) (G, E, D) (G,E,D)的加密算法，在选择明文攻击下具有不可区分性。实际的门被定义为上述值的随机置换，记为 c 0 , c 1 , c 2 , c 3 c_0, c_1, c_2, c_3 c0,c1,c2,c3，称为混淆表。给定 k 1 α , k 2 α k_1^\alpha, k_2^\alpha k1α,k2α和 c 0 , c 1 , c 2 , c 3 c_0, c_1, c_2, c_3 c0,c1,c2,c3，可以按如下步骤计算门的输出 k 3 g ( α , β ) k_3^{g(\alpha, \beta)} k3g(α,β)：
对每个 i i i，计算 D k 2 β ( D k 1 α ( c i ) ) D_{k_2^\beta}(D_{k_1^\alpha}(c_i)) Dk2β(Dk1α(ci))，如果超过1个解密返回非无效值，输出终止；否则，定义 k 3 γ k_3^\gamma k3γ为获得的唯一非无效值，如果只获得一个非无效值，那它就是 k 3 g ( α , β ) k_3^{g(\alpha, \beta)} k3g(α,β)，因为是用 k 1 α k_1\alpha k1α和 k 2 β k_2^\beta k2β加密的。
整个混淆电路的构造如下。令 m m m为电路 C C C中线路的数量， w 1 , . . . , w m w_1, ..., w_m w1,...,wm为线路的标记，这些标记选择如下：如果 w i w_i wi和 w j w_j wj都是来自同一个门 g g g的输出线，则 w i = w j w_i=w_j wi=wj。同样，如果一方输入的一个位进入多个门，那么与该位相关的所有电路输入线将具有相同的标签。接下来，为每个标签 w i w_i wi选择两个独立的密钥 k i 0 , k i 1 ← G ( 1 n ) k_i^0, k_i^1\leftarrow G(1^n) ki0,ki1←G(1n)；所有密钥都是独立于其他密钥选择的。现在，给定这些密钥，每个门的四个混淆值如上所述计算，结果随机置换，计算出该电路的输出或解密表。表格只是由值 ( 0 , k i 0 ) 和 ( 1 , k i 1 ) (0, k_i^0)和(1, k_i^1) (0,ki0)和(1,ki1)组成，其中 w i w_i wi是电路输出线（或者，输出门可以直接计算0或1，即在输出门中，对每个 α , β ∈ { 0 , 1 } \alpha, \beta\in\{0, 1\} α,β∈{0,1}定义 c α , β = E k 1 α ( E k 2 β ( g ( α , β ) ) ) c_{\alpha, \beta}=E_{k_1^\alpha}(E_{k_2^\beta}(g(\alpha, \beta))) cα,β=Ek1α(Ek2β(g(α,β)))）。
C C C的整个混淆电路（记为 G ( C ) G(C) G(C)）由每个门的混淆表，和输出表组成。给定 C C C的结构，通过指定输出表和属于每个门的混淆表，可以简单地定义 C C C的混淆版本，这就完成了对混淆电路的描述。
安全两方计算协议
- 输入： P 1 P_1 P1有 x ∈ { 0 , 1 } n x\in\{0, 1\}^n x∈{0,1}n， P 2 P_2 P2有 y ∈ { 0 , 1 } n y\in\{0, 1\}^n y∈{0,1}n
- 辅助输入：布尔电路 C C C使对每个 x , y ∈ { 0 , 1 } n x, y\in\{0, 1\}^n x,y∈{0,1}n都有 C ( x , y ) = f ( x , y ) C(x, y)=f(x, y) C(x,y)=f(x,y)成立，其中 f : { 0 , 1 } n × { 0 , 1 } n → { 0 , 1 } n f:\{0, 1\}^n\times\{0, 1\}^n\rightarrow\{0, 1\}^n f:{0,1}n×{0,1}n→{0,1}n。要求 C C C满足：如果电路输出线离开某个门 g g g，那么门 g g g就没有其他线引到其他门，即没有电路输出线也是门输入线。同样，作为电路输出线的电路输入线也不进入门。
- 协议：
- P 1 P_1 P1构造混淆电路 G ( C ) G(C) G(C)并发送给 P 2 P_2 P2。
- 令 w 1 , . . . , w n w_1, ..., w_n w1,...,wn为 x x x对应的电路输入线， w n + 1 , . . . , w 2 n w_{n+1}, ..., w_{2n} wn+1,...,w2n为 y y y对应的电路输入线，然后：
a. P 1 P_1 P1向 P 2 P_2 P2发送串 k 1 x 1 , . . . , k n x n k_1^{x_1}, ..., k_n^{x_n} k1x1,...,knxn。
b. 对每个 i i i， P 1 P_1 P1和 P 2 P_2 P2执行2选1不经意传输协议，其中 P 1 P_1 P1的输入等于 ( k n + i 0 , k n + i 1 ) (k_{n+i}^0, k_{n+i}^1) (kn+i0,kn+i1)， P 2 P_2 P2的输入等于 y i y_i yi。
上述不经意传输可以并行运行。 - P 2 P_2 P2获得混淆电路和对应着 C C C的 2 n 2n 2n个输入线的 2 n 2n 2n个密钥，计算电路，获得 f ( x , y ) f(x, y) f(x,y)。
构造方法
Bellare-Micali（1990）
原文下载链接
预备知识
Non-Interactive Oblivious Transfer（非交互式不经意传输）
A A A有 s 0 s_0 s0和 s 1 s_1 s1两个串。 A A A用 B B B的公钥 P B P_B PB加密某消息 m m m发送给 B B B。 B B B用自己的私钥解密消息 m m m，提取出 s 0 s_0 s0或 s 1 s_1 s1。
Oblivious Transfer Channel（OT Channel，不经意传输信道）
A A A到 B B B的不经意传输信道是一对信道 C = ( C 0 , C 1 ) C=(C^0, C^1) C=(C0,C1)，满足：
- A A A可以在 C 0 C^0 C0或 C 1 C^1 C1发送任意多位
- 其中一个信道对 B B B来说是透明的（从某种意义上说，他将看到发送到它上面的任何位），而另一个通道是不透明的
- A A A不知道哪个信道对B来说是透明的
虽然OT信道允许大量的比特被不经意传输，但是OT信道中的茫然性并不是独立的。也就是说，假设 A A A在 C 0 C^0 C0上发送 b 0 b_0 b0，在 C 1 C^1 C1上发送 b 1 b_1 b1，假设 B B B得到 b 0 b_0 b0。然后，如果 A A A现在在 C 0 C^0 C0上发送 c 0 c_0 c0，在 C 1 C^1 C1上发送 c 1 c_1 c1，那么 B B B将得到 c 0 c_0 c0。尽管 A A A不知道每对 B B B得到的是哪个位，但他知道它要么是 b 0 b_0 b0和 c 0 c_0 c0，要么是 b 1 b_1 b1和 c 1 c_1 c1。这既是优点也是缺点。
Non-Interactive Zero Knowledge（非交互式零知识）
公钥非交互式零知识系统：考虑一个用户群，其中每个用户 B B B有一个公钥 P B P_B PB和一个私钥 S B S_B SB。如果对于每一对用户 A A A和 B B B，对于每一个定理 T T T， A A A都可以给 B B B一个关于 T T T的非交互零知识证明，我们称为公钥非交互式零知识系统。 A A A根据定理的功能用 B B B的公钥 P B P_B PB计算消息 m m m，然后发送给 B B B。 B B B的私钥 S B S_B SB能够对 m m m进行解码，直到 B B B对定理的正确性感到满意为止。但 B B B只知道定理是正确的，且通信仅在一个方向： B B B不需要向 A A A发送任何内容。此外，不仅其他用户 C C C也可以向 B B B发送证明，而且可以向 B B B证明的定理个数不受限制。
A simple Scheme
以下方案基于模运算 m o d p \bmod p modp，为了方便，下述省略 m o d p \bmod p modp，例如将 g x m o d p g^x\bmod p gxmodp简记为 g x g^x gx。
- 选定一些公共参数：素数 p p p和 Z p ∗ Z_p^* Zp∗的生成元 g g g， Z p ∗ Z_p^* Zp∗中的某元素 C C C（其离散对数不知道）。
- 生成密钥： B B B随机选择 i ∈ { 0 , 1 } i\in\{0, 1\} i∈{0,1}， x i ∈ { 0 , . . . , p − 2 } x_i\in\{0, ..., p-2\} xi∈{0,...,p−2}，计算 β i = g x i \beta_i=g^{x_i} βi=gxi， β 1 − i = C ⋅ ( g x i ) − 1 \beta_{1-i}=C\cdot (g^{x_i})^{-1} β1−i=C⋅(gxi)−1。 B B B的公钥为 ( β 0 , β 1 ) (\beta_0, \beta_1) (β0,β1)，私钥为 ( i , x i ) (i, x_i) (i,xi)。
任何人在向 B B B发送证明之前都可以通过检查 β 0 β 1 = C \beta_0\beta_1=C β0β1=C来检查 B B B的公钥 ( β 0 , β 1 ) (\beta_0, \beta_1) (β0,β1)是否正确。假设 C C C的离散对数未知，那么 B B B不能同时知道 β 0 \beta_0 β0和 β 1 \beta_1 β1的离散对数。此外， ( β 0 , β 1 ) (\beta_0, \beta_1) (β0,β1)随机分布在 Z p ∗ Z_p^* Zp∗中所有乘积为 C C C的元素对集合上，因此公钥没有揭示B知道两个离散对数中的哪一个。这对于下面描述的非交互式OT来说是至关重要的。
用于该非交互式OT的机制类似于Diffie-Hellman密钥交换协议，并且基于相同的复杂性假设：
Diffie-Hellman Assumption： 给定 g x g^x gx和 g y g^y gy，在不知道 x x x和 y y y的情况下，很难计算得到 g x y g^{xy} gxy。
Non-Interactive OT ( s 0 , s 1 ) (s_0, s_1) (s0,s1)
沿用上述设置， B B B的公钥为 ( β 0 , β 1 ) (\beta_0, \beta_1) (β0,β1)，私钥为 ( i , x i ) (i, x_i) (i,xi)。
- A A A选择随机数 y 0 , y 1 ∈ { 0 , . . . , p − 2 } y_0, y_1\in\{0, ..., p-2\} y0,y1∈{0,...,p−2}并计算 α 0 = g y 0 \alpha_0=g^{y_0} α0=gy0， α 1 = g y 1 \alpha_1=g^{y_1} α1=gy1， γ 0 = β 0 y 0 \gamma_0=\beta_0^{y_0} γ0=β0y0， γ 1 = β 1 y 1 \gamma_1=\beta_1^{y_1} γ1=β1y1，然后计算 r 0 = s 0 ⊕ γ 0 r_0=s_0\oplus\gamma_0 r0=s0⊕γ0， r 1 = s 1 ⊕ γ 1 r_1=s_1\oplus\gamma_1 r1=s1⊕γ1。然后将 α 0 \alpha_0 α0、 α 1 \alpha_1 α1、 r 0 r_0 r0、 r 1 r_1 r1发送给 B B B。
- B B B收到 α 0 \alpha_0 α0、 α 1 \alpha_1 α1、 r 0 r_0 r0、 r 1 r_1 r1后，用私钥计算 α i x i = γ i \alpha_i^{x_i}=\gamma_i αixi=γi，然后计算 γ i ⊕ r i = s i \gamma_i\oplus r_i=s_i γi⊕ri=si得到 s i s_i si。
Diffie-Hellman假设保证了 B B B不能计算得到 γ 1 − i \gamma_{1-i} γ1−i（ B B B虽然知道 g x 1 − i g^{x_{1-i}} gx1−i和 g y 1 − i g^{y_{1-i}} gy1−i但不知道 x 1 − i x_{1-i} x1−i和 y 1 − i y_{1-i} y1−i，所以不能计算得到 γ 1 − i = g x 1 − i y 1 − i \gamma_{1-i}=g^{x_{1-i}y_{1-i}} γ1−i=gx1−iy1−i），故不能得到 s 1 − i s_{1-i} s1−i。 A A A成功进行了不经意传输，且该协议非交互，因为 B B B没有发送信息给 A A A。
A More Secure Scheme
上述方案虽然尽可能简化，但由于Diffie-Hellman假设没有说明位安全性，因此不清楚 s 1 − i s_{1-i} s1−i有多安全。Goldrich和Levin的理论证明：已知 g x g^x gx、 g y g^y gy和随机数 r r r预测 ⟨ g x y , r ⟩ \langle g^{xy}, r\rangle ⟨gxy,r⟩的位，和已知 g x g^x gx、 g y g^y gy计算 g x y g^{xy} gxy一样困难，其中 ⟨ g x y , r ⟩ \langle g^{xy}, r\rangle ⟨gxy,r⟩表示串 g x y g^{xy} gxy和 r r r的内积 m o d 2 \bmod 2 mod2。
Non-Interactive OT ( b 0 , b 1 ) (b_0, b_1) (b0,b1)
沿用上述设置， B B B的公钥为 ( β 0 , β 1 ) (\beta_0, \beta_1) (β0,β1)，私钥为 ( i , x i ) (i, x_i) (i,xi)。
- A A A选择随机数 y 0 , y 1 ∈ { 0 , . . . , p − 2 } y_0, y_1\in\{0, ..., p-2\} y0,y1∈{0,...,p−2}并计算 α 0 = g y 0 \alpha_0=g^{y_0} α0=gy0， α 1 = g y 1 \alpha_1=g^{y_1} α1=gy1， γ 0 = β 0 y 0 \gamma_0=\beta_0^{y_0} γ0=β0y0， γ 1 = β 1 y 1 \gamma_1=\beta_1^{y_1} γ1=β1y1，然后随机选取 r 0 , r 1 ∈ { 0 , 1 } k ( k = ∣ p ∣ ) r_0, r_1\in\{0, 1\}^k(k=|p|) r0,r1∈{0,1}k(k=∣p∣)以满足 ⟨ γ 0 , r 0 ⟩ = b 0 \langle\gamma_0, r_0\rangle=b_0 ⟨γ0,r0⟩=b0， ⟨ γ 1 , r 1 ⟩ = b 1 \langle\gamma_1, r_1\rangle=b_1 ⟨γ1,r1⟩=b1。然后将 α 0 \alpha_0 α0、 α 1 \alpha_1 α1、 r 0 r_0 r0、 r 1 r_1 r1发送给 B B B。
- B B B收到 α 0 \alpha_0 α0、 α 1 \alpha_1 α1、 r 0 r_0 r0、 r 1 r_1 r1后，用私钥计算 α i x i = γ i \alpha_i^{x_i}=\gamma_i αixi=γi然后计算 b i = ⟨ γ i , r i ⟩ b_i=\langle\gamma_i, r_i\rangle bi=⟨γi,ri⟩得到 b i b_i bi。
Goldreich-Levin定理和Diffie-Hellman假设可证明 b 1 − i b_{1-i} b1−i对 B B B是不可预测的。基于Diffie-Hellman假设，将该方案改为交互式的1-out-of-2（2选1）不经意传输协议也很容易。
2 out of 3 Non-Interactive OT
A A A有三个比特 ( b 0 , b 1 , b 2 ) (b_0, b_1, b_2) (b0,b1,b2)， B B B从中选择2个但 A A A不知道他选了哪两个，通过修改上述方案很容易实现。
- 生成密钥： B B B随机选择 i , j ∈ { 0 , 1 , 2 } i, j\in\{0, 1, 2\} i,j∈{0,1,2}和 x i , x j ∈ { 0 , . . . , p − 2 } x_i, x_j\in\{0, ..., p-2\} xi,xj∈{0,...,p−2}，其中 i ≠ j i\ne j i=j。然后计算 β i = g x i \beta_i=g^{x_i} βi=gxi， β j = g x j \beta_j=g^{x_j} βj=gxj， β l = C ⋅ ( g x i ) − 1 ( g x j ) − 1 \beta_l=C\cdot (g^{x_i})^{-1}(g^{x_j})^{-1} βl=C⋅(gxi)−1(gxj)−1，其中 l ∈ { 0 , 1 , 2 } l\in\{0, 1, 2\} l∈{0,1,2}但和 i , j i, j i,j都不相等。 B B B的公钥为 ( β 0 , β 1 , β 2 ) (\beta_0, \beta_1, \beta_2) (β0,β1,β2)，私钥为 ( i , j , x i , x j ) (i, j, x_i, x_j) (i,j,xi,xj)。
Non-Interactive 2 Out of 3 OT ( b 0 , b 1 , b 2 ) (b_0, b_1, b_2) (b0,b1,b2)
- A A A选择随机数 y 0 , y 1 , y 2 ∈ { 0 , . . . , p − 2 } y_0, y_1, y_2\in\{0, ..., p-2\} y0,y1,y2∈{0,...,p−2}并计算 α 0 = g y 0 \alpha_0=g^{y_0} α0=gy0， α 1 = g y 1 \alpha_1=g^{y_1} α1=gy1， α 2 = g y 2 \alpha_2=g^{y_2} α2=gy2， γ 0 = β 0 y 0 \gamma_0=\beta_0^{y_0} γ0=β0y0， γ 1 = β 1 y 1 \gamma_1=\beta_1^{y_1} γ1=β1y1， γ 2 = β 2 y 2 \gamma_2=\beta_2^{y_2} γ2=β2y2，然后随机选取 r 0 , r 1 , r 2 ∈ { 0 , 1 } k ( k = ∣ p ∣ ) r_0, r_1, r_2\in\{0, 1\}^k(k=|p|) r0,r1,r2∈{0,1}k(k=∣p∣)以满足 ⟨ γ 0 , r 0 ⟩ = b 0 \langle\gamma_0, r_0\rangle=b_0 ⟨γ0,r0⟩=b0， ⟨ γ 1 , r 1 ⟩ = b 1 \langle\gamma_1, r_1\rangle=b_1 ⟨γ1,r1⟩=b1， ⟨ γ 2 , r 2 ⟩ = b 2 \langle\gamma_2, r_2\rangle=b_2 ⟨γ2,r2⟩=b2。然后将 α 0 \alpha_0 α0、 α 1 \alpha_1 α1、 α 2 \alpha_2 α2、 r 0 r_0 r0、 r 1 r_1 r1、 r 2 r_2 r2发送给 B B B。
- B B B收到 α 0 \alpha_0 α0、 α 1 \alpha_1 α1、 α 2 \alpha_2 α2、 r 0 r_0 r0、 r 1 r_1 r1、 r 2 r_2 r2后，用私钥计算 α i x i = γ i \alpha_i^{x_i}=\gamma_i αixi=γi， α j x j = γ j \alpha_j^{x_j}=\gamma_j αjxj=γj然后计算 b i = ⟨ γ i , r i ⟩ b_i=\langle\gamma_i, r_i\rangle bi=⟨γi,ri⟩， b j = ⟨ γ j , r j ⟩ b_j=\langle\gamma_j, r_j\rangle bj=⟨γj,rj⟩得到 b i b_i bi和 b j b_j bj。
不难看出，该方案可以很容易推广到任意 t t t选 t − 1 t-1 t−1不经意传输协议。
Non-Interactive OT of More Bits: OT Channels
假设 A A A希望传输多个串，除了重复上述过程以外，可以用下述方法。
首先， A A A用非交互式不经意传输向 B B B传输一对随机 k k k位字符串 ( s 0 , s 1 ) (s_0, s_1) (s0,s1)，即对于每个 j = 1 , . . . , k j=1, ..., k j=1,...,k，执行上一小节的不经意传输 ( ( s 0 ) j , ( s 1 ) j ) ((s_0)_j, (s_1)_j) ((s0)j,(s1)j)，其中 ( s i ) j (s_i)_j (si)j表示 s i s_i si的第 j j j位。 A A A使用伪随机位发生器 G G G将这些种子扩展成一对长伪随机序列 G ( s 0 ) G(s_0) G(s0)和 G ( s 1 ) G(s_1) G(s1)。为了不经意地传输 ( s 0 , r 1 ) (s_0, r_1) (s0,r1)， A A A向 B B B发送 r 0 r_0 r0与 G ( s 0 ) G(s_0) G(s0)下一个未使用位的按位异或，以及 r 1 r_1 r1与 G ( s 1 ) G(s_1) G(s1)下一个未使用位的按位异或。因为 B B B知道种子 s i s_i si可以得到 r i r_i ri，但是没有 s 1 − i s_{1-i} s1−i，序列 G ( s 1 − i ) G(s_{1-i}) G(s1−i)对 B B B来说是随机的，不能得到关于 r 1 − i r_{1-i} r1−i的信息。
上述过程用一般方式建立了OT信道，可以通过附录A中的方法实现非交互式零知识证明系统。
附录A：非交互式零知识证明
假设 A A A想要证明某NP命题 T T T，首先将 T T T转换成有哈密顿回路的图 G = ( V , E ) G=(V, E) G=(V,E)，其中 V = 1 , . . . , n V={1, ..., n} V=1,...,n。 A G A_G AG是 G G G的邻接矩阵，哈密顿回路的边记为 ( u 1 , v 1 ) , . . . , ( u n , v n ) ∈ E (u_1, v_1), ..., (u_n, v_n)\in E (u1,v1),...,(un,vn)∈E， k k k是安全参数。假设 A A A到 B B B有 k k k个OT信道 C 1 = ( C 1 0 , C 1 1 ) , . . . , C k = ( C k 0 , C k 1 ) C_1=(C_1^0, C_1^1), ..., C_k=(C_k^0, C_k^1) C1=(C10,C11),...,Ck=(Ck0,Ck1)。
A A A选取 G G G顶点的随机置换 π \pi π，计算 G G G的同构像 G ′ = π ( G ) = ( V , π ( E ) ) G'=\pi(G)=(V, \pi(E)) G′=π(G)=(V,π(E))，然后选择加密函数 E ( ⋅ , ⋅ ) \mathcal{E}(\cdot, \cdot) E(⋅,⋅)1，按照以下步骤执行：
- 随机选择 r r r加密 π \pi π，即计算 y = E ( π , r ) y=\mathcal{E}(\pi, r) y=E(π,r)
- 随机选择 r i j r_{ij} rij并加密置换图 G ′ G' G′的邻接矩阵 A G ′ A'_G AG′，即：对每个 i , j = 1 , . . . , n i, j=1, ..., n i,j=1,...,n，计算 y i j = E ( a i j ′ , r i j ) y_{ij}=\mathcal{E}(a'_{ij}, r_{ij}) yij=E(aij′,rij)
A A A将 y y y和 y i j ( 1 ≤ i , j ≤ n ) y_{ij}(1\leq i, j\leq n) yij(1≤i,j≤n)发送给 B B B。
A A A投掷硬币，如果是正面，用 C 1 0 C_1^0 C10发送 r , r i j ( 1 ≤ i , j ≤ n ) r, r_{ij}(1\leq i, j\leq n) r,rij(1≤i,j≤n)， C 1 1 C_1^1 C11发送 r π ( u 1 ) π ( v 1 ) , . . . , r π ( u n ) π ( v n ) r_{\pi(u_1)\pi(v_1)}, ..., r_{\pi(u_n)\pi(v_n)} rπ(u1)π(v1),...,rπ(un)π(vn)；如果是反面，交换 C 1 0 C_1^0 C10和 C 1 1 C_1^1 C11发送的内容。
A A A重复上述整个过程 k k k次，获得 k k k个编码，并用 C i C_i Ci传输第 i i i个编码给 B B B。
在接收端， B B B要么知道置换和置换图，要么知道置换图的哈密顿回路。这是著名的哈密顿回路零知识证明。
Naor-Pinkas（2001）
原文下载链接
不经意传输（OT）协议允许一方，即发送方，将其部分输入传输给另一方，即选择方，以保护两者的方式：发送方被保证选择方接收的信息不会超过其应有的数量，而选择方被保证发送者不会知道它接收到的是哪部分输入。
预备知识
这一部分太数学理论化了，不深究OT可以跳过直接看协议。
不经意传输的安全性定义
1-out-of-2不经意传输（ O T 1 2 OT_1^2 OT12）的发送方的输入为两个串 ( M 0 , M 1 ) (M_0, M_1) (M0,M1)，选择方有一个比特 σ \sigma σ，选择方应获得 M σ M_\sigma Mσ但对 M 1 − σ M_{1-\sigma} M1−σ一无所知，同时发送方不知道 σ \sigma σ有关的任何信息。1-out-of-N OT也同理。
- 选择方安全： 假设在正常操作下，发送方不会从协议中获得任何输出，那么选择方的安全性定义很简单：对于任意 σ , τ ∈ { 0 , 1 } \sigma, \tau\in\{0,1\} σ,τ∈{0,1}及执行发送方协议的任何敌手 B ′ \mathcal{B}' B′，给定 M 0 M_0 M0和 M 1 M_1 M1， B ′ \mathcal{B}' B′试图获得 M σ M_\sigma Mσ且选择方试图获得 M τ M_\tau Mτ时，对 B ′ \mathcal{B}' B′来说在统计上是不可区分的。
- 发送方安全： 理想情况是有一个可信第三方，从发送方获得 M 0 M_0 M0和 M 1 M_1 M1，从选择方获得 σ \sigma σ，然后将 M σ M_\sigma Mσ给选择方。我们的要求是，对于输入 ( M 0 , M 1 ) (M_0, M_1) (M0,M1)和任何替代选择方的敌对概率多项式时间机 A \mathcal{A} A，存在一个模拟器——概率多项式时间机 A ′ \mathcal{A}' A′，它在理想模型中扮演选择方的角色，并接收与 A \mathcal{A} A相同的关于 M 0 M_0 M0和 M 1 M_1 M1的先验信息，对于给定 M 0 M_0 M0和 M 1 M_1 M1的多项式时间判别器， A \mathcal{A} A和 A ′ \mathcal{A}' A′的输出在计算上是不可区分的。
同时执行多个1-outof 2 OT协议的安全性：如果 n n n个协议同时执行，选择方安全为对任意 σ ⃗ , τ ⃗ ∈ { 0 , 1 } n \vec\sigma, \vec\tau\in\{0, 1\}^n σ ,τ ∈{0,1}n，当选择方的输入为 σ ⃗ \vec\sigma σ 或 τ ⃗ \vec\tau τ 时，发送方看到的分布在统计上是不可区分的；发送方安全要求对任意输入 M 0 ⃗ \vec{M_0} M0 、 M 1 ⃗ \vec{M_1} M1 ，任意子集 S ⊂ { 1 , . . . , n } S\subset\{1, ..., n\} S⊂{1,...,n}，以及任意敌对（概率多项式时间）机 A \mathcal{A} A（可以控制部分协议的选择方部分），存在一个概率多项式时机 A ′ \mathcal{A}' A′，在理想化模型中扮演选择方角色并接收有关 M ⃗ 0 \vec M_0 M 0和 M ⃗ 1 \vec M_1 M 1的先验信息，对于给定 M ⃗ 0 \vec M_0 M 0和 M ⃗ 1 \vec M_1 M 1的多项式时间判别器， A \mathcal{A} A和 A ′ \mathcal{A}' A′的输出在计算上是不可区分的。
假设
The Diffie-Hellman Assumption： 假设有概率算法生成群 Z q Z_q Zq和生成元 g g g。从计算角度（CDH）来说，对随机 g a , g b ∈ Z q g^a, g^b\in Z_q ga,gb∈Zq，任意概率多项式时间机正确计算出 g a b g^{ab} gab的可能性是可以忽略的。从决策角度（DDH）来说，对随机选择的 a , b , c a, b, c a,b,c，想要区分 ( g a , g b , g c ) (g^a, g^b, g^c) (ga,gb,gc)和 g a , g b , g a b g^a, g^b, g^{ab} ga,gb,gab是很难的。
基础不经意传输协议（Bellare-Micali）（OT using a random oracle）
设定：协议在阶为素数的群 Z q Z_q Zq上执行， G q G_q Gq是阶为 q q q的 Z p ∗ Z_p^* Zp∗的子群，其中 p p p是素数且 q ∣ p − 1 q|p-1 q∣p−1； g g g是生成群，Diffie-Hellman假设在 g g g上成立； H H H是一个随机机。
输入：选择方输入为 σ ∈ { 0 , 1 } \sigma\in\{0, 1\} σ∈{0,1}，发送方输入两个串 M 0 , M 1 M_0, M_1 M0,M1
输出：选择方输出为 M σ M_\sigma Mσ
初始化：发送方选择随机元素 C ∈ Z q C\in Z_q C∈Zq并公开，选择方不知道 C C C基于 g g g的离散对数。
协议 0 0 0：
- 选择方选择随机数 1 ≤ k ≤ q 1\leq k\leq q 1≤k≤q，计算公钥 P K σ = g k PK_\sigma=g^k PKσ=gk， P K 1 − σ = C / P K σ PK_{1-\sigma}=C/PK_\sigma PK1−σ=C/PKσ，将 P K 0 PK_0 PK0发送给发送方。
- 发送方计算 P K 1 = C / P K 0 PK_1=C/PK_0 PK1=C/PK0，选择随机数 r 0 , r 1 ∈ Z q r_0, r_1\in Z_q r0,r1∈Zq。加密 M 0 M_0 M0和 M 1 M_1 M1： E 0 = ⟨ g r 0 , H ( P K 0 r 0 ) ⊕ M 0 ⟩ E_0=\langle g^{r_0}, H(PK_0^{r_0})\oplus M_0\rangle E0=⟨gr0,H(PK0r0)⊕M0⟩， E 1 = ⟨ g r 1 , H ( P K 1 r 1 ) ⊕ M 1 ⟩ E_1=\langle g^{r_1}, H(PK_1^{r_1})\oplus M_1\rangle E1=⟨gr1,H(PK1r1)⊕M1⟩，将密文 E 0 , E 1 E_0, E_1 E0,E1发送给选择方。
- 选择方计算 H ( ( g r σ ) k ) = H ( P K σ r σ ) H((g^{r_\sigma})^k)=H(PK_\sigma^{r_\sigma}) H((grσ)k)=H(PKσrσ)，然后用它解密 M σ M_\sigma Mσ。
A single 1-out-of-2 oblivious transfer
发送方在两个加密中使用同一个随机数 r r r，即 r = r 0 = r 1 r=r_0=r_1 r=r0=r1。另外， P K 0 ⋅ P K 1 = C PK_0\cdot PK_1=C PK0⋅PK1=C成立，那么 ( P K 0 ) r ⋅ ( P K 1 ) r = C r (PK_0)^r\cdot(PK_1)^r=C^r (PK0)r⋅(PK1)r=Cr也成立。下面是 协议 1 1 1 过程（仅列出和上述协议 0 0 0不同的地方）：
- 初始化：选择随机数 r r r，计算 C r C^r Cr和 g r g^r gr。
- 传输：发送方收到 P K 0 PK_0 PK0后，计算 ( P K 0 ) r (PK_0)^r (PK0)r， ( P K 1 ) r = C r / ( P K 0 ) r (PK_1)^r=C^r/(PK_0)^r (PK1)r=Cr/(PK0)r。发送 g r g^r gr和两个消息密文 H ( ( P K 0 ) r , 0 ) ⊕ M 0 , H ( ( P K 1 ) r , 1 ) ⊕ M 1 H((PK_0)^r, 0)\oplus M_0, H((PK_1)^r, 1)\oplus M_1 H((PK0)r,0)⊕M0,H((PK1)r,1)⊕M1给选择方。
发送方的在线开销减少到一次指数运算，预计算开销则和原协议一样，为两次指数运算。
O T 1 N OT_1^N OT1N with amortized complexity of a single exponentiation
（Many simultaneous 1-out-of- N N N OT’s with the same g r g^r gr）
协议 2 2 2：
初始化：发送方选择 N − 1 N-1 N−1个随机常数 C 1 , C 2 , . . . , C N − 1 C_1, C_2, ..., C_{N-1} C1,C2,...,CN−1满足 P K 0 ⋅ P K i = C i PK_0\cdot PK_i=C_i PK0⋅PKi=Ci，同时选择随机数 r r r并计算 g r g^r gr。 C 1 , C 2 , . . . , C N − 1 C_1, C_2, ..., C_{N-1} C1,C2,...,CN−1和 g r g^r gr被发送给选择方并作为发送者公钥，所有传输都用同样的值。对每一个 1 ≤ i ≤ N − 1 1\leq i\leq N-1 1≤i≤N−1，发送方预计算 ( C i ) r (C_i)^r (Ci)r的值。
传输：发送方的输入是 M 0 , M 1 , . . . , M N − 1 M_0, M_1, ..., M_{N-1} M0,M1,...,MN−1，选择方的输入是 σ ∈ { 0 , . . . , N − 1 } \sigma\in\{0, ..., N-1\} σ∈{0,...,N−1}；选择方输出为 M σ M_\sigma Mσ
- 选择方选择随机数 k k k并计算 P K σ = g k PK_\sigma=g^k PKσ=gk。如果 σ ≠ 0 \sigma\neq0 σ=0，计算 C σ / P K σ C_\sigma/PK_\sigma Cσ/PKσ。发送 P K 0 PK_0 PK0给发送方，并计算解密密钥 ( g r ) k = ( P K σ ) r (g^r)^k=(PK_\sigma)^r (gr)k=(PKσ)r。
- 发送方计算 ( P K 0 ) r (PK_0)^r (PK0)r，并对每一个 1 ≤ i ≤ N − 1 1\leq i\leq N-1 1≤i≤N−1，计算 ( P K i ) r = ( C i ) r / ( P K 0 ) r (PK_i)^r=(C_i)^r/(PK_0)^r (PKi)r=(Ci)r/(PK0)r。发送方选择随机串2，然后用 H ( ( P K i ) r , R , i ) ⊕ M i H((PK_i)^r, R, i)\oplus M_i H((PKi)r,R,i)⊕Mi加密每个 M i M_i Mi，连同 R R R一起发送给选择方。
- 选择方用 H ( ( P K σ ) r , R , σ ) H((PK_\sigma)^r, R, \sigma) H((PKσ)r,R,σ)解密 M σ M_\sigma Mσ。
开销：初始化阶段，发送方包含 N N N次指数运算；初始化之后，在每次传输中，发送方只执行一次指数运算，加上 N − 1 N-1 N−1次乘法和 N N N次 H H H调用；选择方在收到发送方发送的密文前可以预计算解密密钥。从发送方到选择方的通信开销和 N N N个串的大小有关。
Bandwidth/Complexity tradoff for O T 1 2 OT_1^2 OT12
（Simultaneous transfer of l l l strings）
通过执行 l l l个 O T 1 2 OT_1^2 OT12，其传输过程与协议 2 2 2相同，可以减少 O T 1 2 OT_1^2 OT12的计算开销。其思想是将对 O T 1 2 OT_1^2 OT12的 l l l个调用转换单个1-out-of- L L L OT， L = 2 l L=2^l L=2l（另一篇文章将一个1-out-of-L OT转换成 O T 1 2 OT_1^2 OT12）。这减少了计算，增加了通信，因此得到了计算和通信的折衷。
设 l l l表示每批传输字符串数量，即如果 O T 1 2 OT_1^2 OT12的数量很大，则将它们划分为 l l l块。考虑一个块，在这个块中，发送方在每个消息对 { ( m i , 0 , m i , 1 ) } i = 1 l \{(m_{i, 0}, m_{i, 1})\}_{i=1}^l {(mi,0,mi,1)}i=1l中向选择方传输一个字符串，现在同时进行 l l l个传输。发送方定义 L = 2 l L=2^l L=2l个串 M 0 , . . . , M L − 1 M_0, ..., M_{L-1} M0,...,ML−1，对应从每个消息对中选出一个所有可能的组合，即 M j = ⟨ m 1 , j 1 , m 2 , j 2 , . . . , m l , j l ⟩ M_j=\langle m_{1, j_1}, m_{2, j_2}, ..., m_{l, j_l}\rangle Mj=⟨m1,j1,m2,j2,...,ml,jl⟩，其中 j i j_i ji是 j j j的第 i i i位。参与方只需执行单个1-out-of- L L L OT，而不是 l l l个 O T 1 2 OT_1^2 OT12。
协议 3 3 3：参与方执行协议 2 2 2的 O T 1 L OT_1^L OT1L。发送方输入为 L L L个串 M 0 , . . . , M L − 1 M_0, ..., M_{L-1} M0,...,ML−1，选择方输入为 σ ⃗ = σ 1 , . . . , σ l \vec\sigma=\sigma_1, ..., \sigma_l σ =σ1,...,σl，其中 σ i \sigma_i σi是选择方在第 i i i个OT中的选择。
开销：在初始化阶段，发送方执行 L L L次指数运算，在发送者发送的所有数据块中分摊；在传输阶段，发送方执行一次指数运算和 L = 2 l L=2^l L=2l次乘法；选择方在发送请求和收到密文后各执行一次指数运算。通信ka开销是输入大小的 l ⋅ L l\cdot L l⋅L倍，因为有 L L L条长为 l l l的消息 M i M_i Mi。但进行更精细的分析：首先区分群元素（可能有1000比特长）和私钥（可以短至100比特）。另一个区别是在线和离线通信，后者指的是可以独立于输入发送的消息，因此可以认为是在预处理阶段发送的（比如通信网络空闲，或者存储在DVD中）。从选择方到发送方只发送一个群元素。通过使用不同密钥对每个 m i m_i mi进行加密，并以密钥作为输入执行不经意传输，可以将发送方到选择方的在线通信从 O ( l ⋅ L ) O(l\cdot L) O(l⋅L)减少到 O ( L ) O(L) O(L)。
也就是说，执行下列协议：
- 对每个 1 ≤ i ≤ l 1\leq i\leq l 1≤i≤l和 σ ∈ { 0 , 1 } \sigma\in\{0, 1\} σ∈{0,1}，发送方选择一个随机密钥 k i , σ k_{i, \sigma} ki,σ（总共 2 l 2l 2l个）。对每个 1 ≤ j ≤ L 1\leq j\leq L 1≤j≤L，令 M j ′ = ⟨ k 1 , j 1 , k 2 , j 2 , . . . , k l , j l ⟩ M_j'=\langle k_{1, j_1}, k_{2, j_2}, ..., k_{l, j_l}\rangle Mj′=⟨k1,j1,k2,j2,...,kl,jl⟩为传输的值的密钥。
- 对每个 1 ≤ j ≤ L 1\leq j\leq L 1≤j≤L，发送方选择随机密钥 K j K_j Kj并用 H ( K j , R ) H(K_j, R) H(Kj,R)加密 M j ′ M_j' Mj′如 M j ′ ⊕ H ( K j , R ) M_j'\oplus H(K_j, R) Mj′⊕H(Kj,R)，这些密文被离线发送。
- 在传输阶段，发送方发送对所有 1 ≤ i ≤ l 1\leq i\leq l 1≤i≤l和 σ ∈ { 0 , 1 } \sigma\in\{0, 1\} σ∈{0,1}的密文 E k i , σ ( m i , σ ) E_{k_{i, \sigma}}(m_{i, \sigma}) Eki,σ(mi,σ)和所有密钥 ( K 1 , K 2 , . . . , K L ) (K_1, K_2, ..., K_L) (K1,K2,...,KL)，其中每个 K j K_j Kj都是用 H ( ( P K j ) r , R , j ) H((PK_j)^r, R, j) H((PKj)r,R,j)加密的。
- 选择方使用 K j K_j Kj解密对应串 M j ′ M_j' Mj′，然后用 M j ′ M_j' Mj′中的密钥 k i , j k_{i, j} ki,j解密元素 m i , j m_{i, j} mi,j。
以上，通信开销分析：
离线通信： 第2步中离线通信的总长度为 L l ∣ k i , σ ∣ Ll|k_{i, \sigma}| Ll∣ki,σ∣比特，密钥的长度 ∣ k i , σ ∣ |k_{i, \sigma}| ∣ki,σ∣可以设置成100比特，且不会随输入变长而增大，但如果 m i , σ m_{i, \sigma} mi,σ变短，就可以用与对应密钥 k i , σ k_{i, \sigma} ki,σ异或来加密，那么密钥可以缩短到和输入一样长。
在线通信：在传输阶段，发送方发送长为 L ∣ K j ∣ + 2 l ∣ m i , σ ∣ L|K_j|+2l|m_{i, \sigma}| L∣Kj∣+2l∣mi,σ∣比特的消息给接收方，其中密钥 K j K_j Kj的长度也可以设置为100比特。
与独立地运行 l l l次不经意传输协议的方案相比，在线通信中存在 L = 2 l L=2^l L=2l倍增长，并且在线通信中存在 L / l L/l L/l增加。与基本的Bellare-Micali协议（协议 0 0 0）相比，通信量的增加较小，因为该协议中的所有消息都包含Diffie-Hellman假设所适用的群元素。
How to avoid random oracles
本节讨论设计协议的方法，这些协议的分析不依赖于随机预言。第一个问题是是否有可能设计一个不依赖随机预言假设的两轮（Bellare和Micali称之为非交互的）OT协议。Dwork和Naor提出了（几乎3）符合两轮要求的协议，它依赖于NP语言中非交互零知识的通用协议，因此是非常不完善的。独立于这项工作，Aiello，Ishai和Reingold提出了一个类似的协议，用于解决相关问题。
协议的结构是选择方先发送给发送方然后发送方发送给选择方。和Bellare-Micali、Dwork-Naor中的协议不同，该协议不需要发送方设置公钥或公有值。它基于DDH4假设，为发送者提供信息论保护，为选择者提供计算不可区分性（与提到的Bellare-Micali方案和其他方案相反）。选择方创建两个加密密钥，至多有一个是合法的，如果一个密钥形式不对，对应的公钥就是一个随机值，这类似于DDH问题的随机自归约。
协议 4 4 4：（基础协议）
- 选择方生成随机值 g a , g b g^a, g^b ga,gb和 c 0 , c 1 c_0, c_1 c0,c1使 c σ = a b c_\sigma=ab cσ=ab且 c 1 − σ c_{1-\sigma} c1−σ是随机数。将 x = g a , y = g b , z 0 = g c 0 , z 1 = g c 1 x=g^a, y=g^b, z_0=g^{c_0}, z_1=g^{c_1} x=ga,y=gb,z0=gc0,z1=gc1发送给发送方。
- 发送方验证 z 0 ≠ z 1 z_0\neq z_1 z0=z1，然后生成随机值 ( r 0 , s 0 ) , ( r 1 , s 1 ) (r_0, s_0), (r_1, s_1) (r0,s0),(r1,s1)，并且：
- 计算 w 0 = x s 0 ⋅ g r 0 w_0=x^{s_0}\cdot g^{r_0} w0=xs0⋅gr0并用密钥 z 0 s 0 ⋅ y r 0 z_0^{s_0}\cdot y^{r_0} z0s0⋅yr0加密 M 0 M_0 M0， w 0 w_0 w0和密文发送给选择方。
- 计算 w 1 = x s 1 ⋅ g r 1 w_1=x^{s_1}\cdot g^{r_1} w1=xs1⋅gr1并用密钥 z 1 s 1 ⋅ y r 1 z_1^{s_1}\cdot y^{r_1} z1s1⋅yr1加密 M 1 M_1 M1， w 1 w_1 w1和密文发送给选择方。
- 选择方计算 ( w σ ) b (w_\sigma)^b (wσ)b来解密 M σ M_\sigma Mσ。
开销分析：
在计算 g a , g b g^a, g^b ga,gb和 g c σ = g a b g^{c_\sigma}=g^{ab} gcσ=gab时，选择方有3个指数运算，包括随机选择 g c 1 − σ g^{c_{1-\sigma}} gc1−σ的值，且 { g a , g b } \{g^a, g^b\} {ga,gb}可以反复使用，不用随传输变化。因此在每次传输中，选择方可以（离线）计算2次指数运算，并在收到发送方的消息后（在线）计算1次指数运算。发送方在每次传输中需要计算对两个不同值的两个双指数。
安全分析：
选择方的安全基于 c σ c_\sigma cσ和 c 1 − σ c_{1-\sigma} c1−σ的不可区分性，而这又基于DDH假设。发送方的安全是信息论的，且基于下述理论：
如果 z τ ≠ g a b z_\tau\neq g^{ab} zτ=gab，那么 ( x τ s τ ⋅ g τ r τ , z τ s τ ⋅ y τ r τ ) (x_\tau^{s_\tau}\cdot g_\tau^{r_\tau}, z_\tau^{s_\tau}\cdot y_\tau^{r_\tau}) (xτsτ⋅gτrτ,zτsτ⋅yτrτ)是均匀分布的。
因此，如果 z τ ≠ g a b z_\tau\neq g^{ab} zτ=gab，那么 m τ m_\tau mτ的相关信息就不会被传输，由于 { z 0 , z 1 } \{z_0, z_1\} {z0,z1}中至多有一个和 g a b g^{ab} gab相等，选择方至多只能得到 M 0 , M 1 M_0, M_1 M0,M1中的一个。
1-out-of- N N N protocol（推广）
这个推广可以在不增加选择方复杂度的情况下完成，关键是选择方不必显式地选择和发送 g c i g^{c_i} gci。设选择方想要获得 M i M_i Mi，选择 C i = a ⋅ b C_i=a\cdot b Ci=a⋅b并计算 z i = g c i z_i=g^{c_i} zi=gci，这反过来又定义所有的 z j z_j zj为 z j = z i ⋅ g j − i z_j=z_i\cdot g^{j-i} zj=zi⋅gj−i，特别地， z 0 = g c i − i z_0=g^{c_i-i} z0=gci−i。然后选择方发送 g a , g b g^a, g^b ga,gb和 z 0 = g c i / g i z_0=g^{c_i}/g^i z0=gci/gi。发送方仍然需要执行所有和之前一样的步骤。
安全分析：
发送方的安全性和协议 4 4 4中一样。对于选择方，基于DDH假设，对于固定的 i i i，没有概率多项式时间机可以区分 ( g a , g b , g a b − i ) (g^a, g^b, g^{ab-i}) (ga,gb,gab−i)和一个随机三元组。因此三元组 ( g a , g b , g a b − i ) (g^a, g^b, g^{ab-i}) (ga,gb,gab−i)和 ( g a , g b , g a b − i ′ ) (g^a, g^b, g^{ab-i'}) (ga,gb,gab−i′)是计算上不可区分的。
开销分析：
选择方的开销和协议 4 4 4中一样。发送方计算 2 N 2N 2N个双指数运算。选择方的通信开销是发送固定数量的运算并且接收 2 N 2N 2N个元素，因此和协议 2 2 2的工作量大致相等。
Y. Lindell（2008）
原文下载链接
Oblivious Transfer Under the DDH Assumption
该协议基于DDH假设并考虑有恶意敌手的存在。协议是上述Naor-Pinkas中两轮协议的一个变形，先回顾一下Naor-Pinkas的协议。
基本上，该协议工作原理是接收方生成一个元组 ( g a , g b , g c , g d ) (g^a, g^b, g^c, g^d) (ga,gb,gc,gd)，具有以下特性：
- 如果接收方的输入等于0，那么 c = a b c=ab c=ab且 d d d是随机的；
- 如果接收器方的输入等于1，那么d=ab和c是随机的。
发送方接收这个元组并使元组随机化，那么如果 c = a b c=ab c=ab，对 ( g a , g b , g c ) (g^a, g^b, g^c) (ga,gb,gc)随机化后的结果仍是DDH元组，对 ( g a , g b , g d ) (g^a, g^b, g^d) (ga,gb,gd)随机化后的结果是一个完全随机的元组（如果 d = a b d=ab d=ab，那么结果相反）。然后，发送方对 ( g a , g b , g c ) (g^a, g^b, g^c) (ga,gb,gc)和 ( g a , g b , g d ) (g^a, g^b, g^d) (ga,gb,gd)中的每一个元素导出密钥，使接收方能够从DDH元组导出相同的密钥，而来自非DDH元组的密钥保持完全随机。发送方使用从 ( g a , g b , g c ) (g^a, g^b, g^c) (ga,gb,gc)派生的密钥对其第一条消息进行加密，使用从 ( g a , g b , g d ) (g^a, g^b, g^d) (ga,gb,gd)派生的密钥对其第二条消息进行加密。接收方能够解密从DDH元组派生的消息，但没有关于另一个密钥的信息，因此无法了解关于另一个消息的任何信息。发送方验证 g c ≠ g d g^c\neq g^d gc=gd确保了 ( g a , g b , g c ) (g^a, g^b, g^c) (ga,gb,gc)和 ( g a , g b , g d ) (g^a, g^b, g^d) (ga,gb,gd)中只有一个是DDH元组。
从上述非DDH元组导出的密钥是对接收方隐藏的信息，使得为协议构造模拟器时出现问题，因为模拟器必须知道发送方的两个输入，才能将它们发送给可信方（并且对于模拟器发送的第一条消息，可信方只能知道发送方的一个输入）。如果使用重绕来获取这两条消息，那么这将导致一个问题，因为发送方可以使其输入依赖于来自接收方的第一条消息。因此，修改上述协议，以便接收方不发送 ( g a , g b , g c , g d ) (g^a, g^b, g^c, g^d) (ga,gb,gc,gd)（ c c c和 d d d中至多一个等于 a ⋅ b a\cdot b a⋅b），而是发送两个元组：一个元组是DDH类型，另一个不是。然后双方进行交互，以确保实际上只有一个元组是DDH类型的，这确保了接收方只获得一条消息。
下面的协议用了两个承诺方案：一个完全隐藏的承诺方案 C o m h \mathbf{Com}_h Comh和一个完全约束的承诺方案 C o m b \mathbf{Com}_b Comb，在离散对数和DDH假设下这样的承诺是存在的。发送方的输入值 m 0 , m 1 m_0, m_1 m0,m1在为DDH假设选择的群 G \mathcal{G} G中，如果它们不能映射到 G \mathcal{G} G（例如，太长），则可以使用不经意传输来交换分别用于加密 m 0 m_0 m0和 m 1 m_1 m1的密钥 k 0 k_0 k0和 k 1 k_1 k1。
协议 1 1 1：
- 辅助输入：参与方有阶为 q q q的群 G \mathcal{G} G及其生成元 g g g。另外，一个统计误差参数 l l l。
- 输入：发送方有一对群元素 ( m 0 , m 1 ) (m_0, m_1) (m0,m1)，接收方有一个位 σ \sigma σ。
- 协议：
- 对每个 i = 1 , . . . , l i=1, ..., l i=1,...,l，接收方 P 2 P_2 P2选择随机数 σ i ∈ R { 0 , 1 } \sigma_i\in_R\{0, 1\} σi∈R{0,1}和 a i 0 , b i 0 , c i 0 , a i 1 , b i 1 , c i 1 ∈ R { 1 , . . . , q } a_i^0, b_i^0, c_i^0, a_i^1, b_i^1, c_i^1\in_R\{1, ..., q\} ai0,bi0,ci0,ai1,bi1,ci1∈R{1,...,q}满足条件 c i σ i = a i σ i ⋅ b i σ i c_i^{\sigma_i}=a_i^{\sigma_i}\cdot b_i^{\sigma_i} ciσi=aiσi⋅biσi和 c i 1 − σ i ≠ a i 1 − σ i ⋅ b i 1 − σ i c_i^{1-\sigma_i}\neq a_i^{1-\sigma_i}\cdot b_i^{1-\sigma_i} ci1−σi=ai1−σi⋅bi1−σi。然后， P 2 P_2 P2计算元组 γ i 0 = ( g a i 0 , g b i 0 , g c i 0 ) , γ i 1 = ( g a i 1 , g b i 1 , g c i 1 ) \gamma_i^0=(g^{a_i^0}, g^{b_i^0}, g^{c_i^0}), \gamma_i^1=(g^{a_i^1}, g^{b_i^1}, g^{c_i^1}) γi0=(gai0,gbi0,gci0),γi1=(gai1,gbi1,gci1)，则 γ i σ i \gamma_i^{\sigma_i} γiσi是DDH元组而 γ i 1 − σ i \gamma_i^{1-\sigma_i} γi1−σi不是。 P 2 P_2 P2将所有对 ⟨ ( γ 1 0 , γ 1 1 ) , . . . , ( γ l 0 , γ l 1 ) ⟩ \langle(\gamma_1^0, \gamma_1^1), ..., (\gamma_l^0, \gamma_l^1)\rangle ⟨(γ10,γ11),...,(γl0,γl1)⟩发送给发送方 P 1 P_1 P1。
- 投掷硬币：
a. P 1 P_1 P1选择随机数 s ∈ R { 0 , 1 } l s\in_R\{0, 1\}^l s∈R{0,1}l并发送 C o m h ( s ) \mathbf{Com}_h(s) Comh(s)给 P 2 P_2 P2。
b. P 2 P_2 P2选择随机数 s ′ ∈ R { 0 , 1 } l s'\in_R\{0, 1\}^l s′∈R{0,1}l并发送 C o m b ( s ′ ) \mathbf{Com}_b(s') Comb(s′)给 P 1 P_1 P1。
c. P 1 P_1 P1和 P 2 P_2 P2分别向 C o m h ( s ) \mathbf{Com}_h(s) Comh(s)和 C o m b ( s ′ ) \mathbf{Com}_b(s') Comb(s′)发送解除承诺，设置 r = s ⊕ s ′ r=s\oplus s' r=s⊕s′，记 r = r 1 , . . . , r l r=r_1, ..., r_l r=r1,...,rl。 - 对 r i = 1 r_i=1 ri=1的每个 i i i，参与方 P 2 P_2 P2向 P 1 P_1 P1发送 a i 0 , b i 0 , c i 0 , a i 1 , b i 1 , c i 1 a_i^0, b_i^0, c_i^0, a_i^1, b_i^1, c_i^1 ai0,bi0,ci0,ai1,bi1,ci1。另外，对 r j = 0 r_j=0 rj=0的每个 j j j， P 2 P_2 P2向 P 1 P_1 P1发送 γ j 0 \gamma_j^0 γj0和 γ j 1 \gamma_j^1 γj1的重排，使所有 γ j σ \gamma_j^\sigma γjσ是DDH元组且所有 γ j 1 − σ \gamma_j^{1-\sigma} γj1−σ不是。这个重排用一个比特位表示，如果为0表示无重排，如果为1表示 γ j 0 \gamma_j^0 γj0和 γ j 1 \gamma_j^1 γj1互换。
- 对 r i = 1 r_i=1 ri=1的每个 i i i， P 1 P_1 P1检查是否接收到适当的值，以及是否定义了 γ i 0 \gamma_i^0 γi0和 γ i 1 \gamma_i^1 γi1。此外，检查 γ i 0 \gamma_i^0 γi0和 γ i 1 \gamma_i^1 γi1中一个是DDH元组，而另一个不是。如果任何检查失败， P 1 P_1 P1中止并输出 ⊥ \perp ⊥，否则继续如下：
a. 记 γ j 0 = ( x j 0 , y j 0 , z j 0 ) , γ j 1 = ( a j 1 , y j 1 , z j 1 ) \gamma_j^0=(x_j^0, y_j^0, z_j^0), \gamma_j^1=(a_j^1, y_j^1, z_j^1) γj0=(xj0,yj0,zj0),γj1=(aj1,yj1,zj1)，然后对 r j = 0 r_j=0 rj=0的每个 j j j， P 1 P_1 P1选择随机值 u i 0 , u i 1 , v i 0 , v i 1 ∈ R { 1 , . . . , q } u_i^0, u_i^1, v_i^0, v_i^1\in_R\{1, ..., q\} ui0,ui1,vi0,vi1∈R{1,...,q}并计算 w j 0 = ( x j 0 ) u i 0 ⋅ g v i 0 w_j^0=(x_j^0)^{u_i^0}\cdot g^{v_i^0} wj0=(xj0)ui0⋅gvi0， w j 1 = ( x j 1 ) u i 1 ⋅ g v i 1 w_j^1=(x_j^1)^{u_i^1}\cdot g^{v_i^1} wj1=(xj1)ui1⋅gvi1， k j 0 = ( z j 0 ) u i 0 ⋅ ( y j 0 ) v i 0 k_j^0=(z_j^0)^{u_i^0}\cdot (y_j^0)^{v_i^0} kj0=(zj0)ui0⋅(yj0)vi0， k j 1 = ( z j 1 ) u i 1 ⋅ ( y j 1 ) v i 1 k_j^1=(z_j^1)^{u_i^1}\cdot (y_j^1)^{v_i^1} kj1=(zj1)ui1⋅(yj1)vi1。
b. 令 j 1 , . . . , j t j_1, ..., j_t j1,...,jt是所有 r j = 0 r_j=0 rj=0的 j j j的指标。然后 P 1 P_1 P1用所有密钥 k j 0 k_j^0 kj0加密 m 0 m_0 m0， k j 1 k_j^1 kj1加密 m 1 m_1 m1： c 0 = ( ∏ i = 1 t k j i 0 ) ⋅ m 0 c_0=(\prod_{i=1}^t k_{j_i}^0)\cdot m_0 c0=(∏i=1tkji0)⋅m0， c 1 = ( ∏ i = 1 t k j i 1 ) ⋅ m 1 c_1=(\prod_{i=1}^t k_{j_i}^1)\cdot m_1 c1=(∏i=1tkji1)⋅m1。 P 1 P_1 P1将所有 w j 0 , w j 1 w_j^0, w_j^1 wj0,wj1和 ( c 0 , c 1 ) (c_0, c_1) (c0,c1)的值发送给 P 2 P_2 P2。 - 对每个 r j = 0 r_j=0 rj=0的 j j j， P 2 P_2 P2计算 k j σ = ( w j σ ) b j 0 k_j^\sigma=(w_j^\sigma)^{b_j^0} kjσ=(wjσ)bj0。然后， P 2 P_2 P2输出 m σ = c σ ⋅ ( ∏ i = 1 t k j i σ ) − 1 m_\sigma=c_\sigma\cdot(\prod_{i=1}^t k_{j_i}^\sigma)^{-1} mσ=cσ⋅(∏i=1tkjiσ)−1。
首先证明协议有效，即当 P 1 P_1 P1和 P 2 P_2 P2是诚实的时，输出是正确的。首先，有等式： ( w j σ ) b j σ = ( x j σ ) u j σ ⋅ b j σ ⋅ ( g v j σ ) = ( g a j σ ⋅ b j σ ) u j σ ⋅ ( g b j σ ) v j σ (w_j^\sigma)^{b_j^\sigma}=(x_j^\sigma)^{u_j^\sigma\cdot b_j^\sigma}\cdot (g^{v_j^\sigma})=(g^{a_j^\sigma\cdot b_j^\sigma})^{u_j^\sigma}\cdot (g^{b_j^\sigma})^{v_j^\sigma} (wjσ)bjσ=(xjσ)ujσ⋅bjσ⋅(gvjσ)=(gajσ⋅bjσ)ujσ⋅(gbjσ)vjσ。事实上， γ j σ \gamma_j^\sigma γjσ是DDH元组，则 g a j σ ⋅ b j σ = z j σ g^{a_j^\sigma\cdot b_j^\sigma}=z_j^\sigma gajσ⋅bjσ=zjσ成立，那么 ( w j σ ) b j σ = ( z j σ ) u j σ ⋅ ( y j σ ) v j σ (w_j^\sigma)^{b_j^\sigma}=(z_j^\sigma)^{u_j^\sigma}\cdot (y_j^\sigma)^{v_j^\sigma} (wjσ)bjσ=(zjσ)ujσ⋅(yjσ)vjσ。因此 P 2 P_2 P2正确地计算对每个 r j = 0 r_j=0 rj=0的 j j j的密钥 k j σ k_j^\sigma kjσ。给定所有密钥， P 2 P_2 P2可以立即解密 c σ c_\sigma cσ获得 m σ m_\sigma mσ。
Oblivious Transfer from Homomorphic Encryption
该协议基于Aiello，Ishai和Reingold的协议。设加性同态加密方案 ( G , E , D ) (G, E, D) (G,E,D)，其中 G ( 1 n ) G(1^n) G(1n)输出长为 n n n的密钥对， E E E是加密算法， D D D是解密算法。加性同态操作也包含数乘（相当于缩放）。
协议 2 2 2：
- 输入：发送方有一对已知长度的串 ( m 0 , m 1 ) (m_0, m_1) (m0,m1)，接收方有一个比特位 σ \sigma σ。双方有决定加密方案密钥长度的安全参数 n n n和一个单独的统计安全参数 l l l。
- 协议：
- 接收方的消息：
a. 接收方 P 2 P_2 P2从同态加密方案 ( G , E , D ) (G, E, D) (G,E,D)5中选择一对密钥 ( p k , s k ) ← G ( 1 n ) (pk, sk)\leftarrow G(1^n) (pk,sk)←G(1n)
b. 对每个 i = 1 , . . . , l i=1, ..., l i=1,...,l， P 2 P_2 P2选择随机位 b i ∈ R { 0 , 1 } b_i\in_R\{0, 1\} bi∈R{0,1}并定义 c i b i = E p k ( 0 ; r i b i ) c_i^{b_i}=E_{pk}(0; r_i^{b_i}) cibi=Epk(0;ribi)和 c i 1 − b i = E p k ( 1 ; r i 1 − b i ) c_i^{1-b_i}=E_{pk}(1; r_i^{1-b_i}) ci1−bi=Epk(1;ri1−bi)，其中 r i 0 r_i^0 ri0和 r i 1 r_i^1 ri1是随机串， E p k ( x ; r ) E_{pk}(x; r) Epk(x;r)表示用随机硬币 r r r加密消息 x x x
c. P 2 P_2 P2向 P 1 P_1 P1发送 p k , ⟨ c 1 0 , c 1 1 , . . . , c l 0 , c l 1 ⟩ pk, \langle c_1^0, c_1^1, ..., c_l^0, c_l^1\rangle pk,⟨c10,c11,...,cl0,cl1⟩ - 投掷硬币：
a. P 1 P_1 P1选择一个随机数 s ~ ∈ R { 0 , 1 } l \tilde{s}\in_R\{0, 1\}^l s~∈R{0,1}l并将 C o m h ( s ~ ) \mathbf{Com}_h(\tilde{s}) Comh(s~)发送给 P 2 P_2 P2。
b. P 2 P_2 P2选择一个随机数 s ^ ∈ R { 0 , 1 } l \hat{s}\in_R\{0, 1\}^l s^∈R{0,1}l并将 C o m b ( s ^ ) \mathbf{Com}_b(\hat{s}) Comb(s^)发送给 P 1 P_1 P1。
c. P 1 P_1 P1和 P 2 P_2 P2分别向 C o m h ( s ~ ) \mathbf{Com}_h(\tilde{s}) Comh(s~)和 C o m b ( s ^ ) \mathbf{Com}_b(\hat{s}) Comb(s^)发送解除承诺，并设置 s = s ~ ⊕ s ^ s=\tilde s\oplus\hat s s=s~⊕s^，记 s = s 1 , . . . , s l s=s_1, ..., s_l s=s1,...,sl。另外，令 S 1 S_1 S1为所有 s i = 1 s_i=1 si=1的 i i i的集合， S 0 S_0 S0为所有 s j = 0 s_j=0 sj=0的 j j j的集合， S 0 S_0 S0和 S 1 S_1 S1为 1 , . . . , l {1, ..., l} 1,...,l的分割。 - 接收方的消息：
a. 对每个 i ∈ S 1 i\in S_1 i∈S1， P 2 P_2 P2发送用来加密 c i 0 c_i^0 ci0和 c i 1 c_i^1 ci1的随机数 r i 0 , r i 1 r_i^0, r_i^1 ri0,ri1。
b. 对每个 j ∈ S 0 j\in S_0 j∈S0， P 2 P_2 P2发送比特 β j \beta_j βj：如果 σ = 0 \sigma=0 σ=0则 β j = b j \beta_j=b_j βj=bj，如果 σ = 1 \sigma=1 σ=1则 β j = 1 − b j \beta_j=1-b_j βj=1−bj。 - 发送方的消息：
a. 对每个 i ∈ S 1 i\in S_1 i∈S1， P 1 P_1 P1验证 c i 0 = E p k ( 0 ; r i 0 ) c_i^0=E_{pk}(0; r_i^0) ci0=Epk(0;ri0)和 c i 1 = E p k ( 1 ; r i 1 ) c_i^1=E_{pk}(1; r_i^1) ci1=Epk(1;ri1)，或 c i 0 = E p k ( 1 ; r i 0 ) c_i^0=E_{pk}(1; r_i^0) ci0=Epk(1;ri0)和 c i 1 = E p k ( 0 ; r i 1 ) c_i^1=E_{pk}(0; r_i^1) ci1=Epk(0;ri1)。即， P 1 P_1 P1验证每个对中一个是对 0 0 0加密的密文，一个是对 1 1 1加密的密文。如果上述条件不是对每一个 i i i都成立的， P 1 P_1 P1终止。如果全部验证通过，继续下一步骤。
b. 对每个 j ∈ S 0 j\in S_0 j∈S0， P 1 P_1 P1定义 c j c_j cj和 c j ′ c_j' cj′为：如果 β i = 0 \beta_i=0 βi=0则 c j = c j 0 , c j ′ = c j 1 c_j=c_j^0, c_j'=c_j^1 cj=cj0,cj′=cj1；如果 β i = 1 \beta_i=1 βi=1，则 c j = c j 1 , c j ′ = c j 0 c_j=c_j^1, c_j'=c_j^0 cj=cj1,cj′=cj0。这意味着如果 σ = 0 \sigma=0 σ=0则 c j = E p k ( 0 ) , c j ′ = E p k ( 1 ) c_j=E_{pk}(0), c_j'=E_{pk}(1) cj=Epk(0),cj′=Epk(1)，如果 σ = 1 \sigma=1 σ=1则 c j = E p k ( 1 ) , c j ′ = E p k ( 0 ) c_j=E_{pk}(1), c_j'=E_{pk}(0) cj=Epk(1),cj′=Epk(0)。6
c. 对每个 j ∈ S 0 j\in S_0 j∈S0， P 1 P_1 P1选择均匀分布在加密方案定义的群内的随机数 ρ j , ρ j ′ \rho_j, \rho_j' ρj,ρj′，然后用同态性质计算 c 0 = ( ∑ j ∈ S 1 ρ j ⋅ c j ) + E p k ( m 0 ) c_0=(\sum_{j\in S_1}\rho_j\cdot c_j)+E_{pk}(m_0) c0=(∑j∈S1ρj⋅cj)+Epk(m0)， c 1 = ( ∑ j ∈ S 1 ρ j ′ ⋅ c j ′ ) + E p k ( m 1 ) c_1=(\sum_{j\in S_1}\rho'_j\cdot c'_j)+E_{pk}(m_1) c1=(∑j∈S1ρj′⋅cj′)+Epk(m1)，其中加法表示密文的同态加，乘法表示标量乘。
d. P 1 P_1 P1向 P 2 P_2 P2发送 ( c 0 , c 1 ) (c_0, c_1) (c0,c1)。 - 接收方计算输出： P 2 P_2 P2输出 D s k ( c σ ) D_{sk}(c_\sigma) Dsk(cσ)。
- 接收方的消息：
正确性分析：
- σ = 0 \sigma=0 σ=0的情况：
如注释6所述，对每个 j j j， c j = E p k ( 0 ) , c j ′ = E p k ( 1 ) c_j=E_{pk}(0), c'_j=E_{pk}(1) cj=Epk(0),cj′=Epk(1)都成立，由0乘以标量等于0，得： c 0 = ( ∑ j ∈ S 1 ρ j ⋅ c j ) + E p k ( m 0 ) = E p k ( 0 ) + E p k ( m 0 ) = E p k ( m 0 ) c_0=(\sum_{j\in S_1}\rho_j\cdot c_j)+E_{pk}(m_0)=E_{pk}(0)+E_{pk}(m_0)=E_{pk}(m_0) c0=(∑j∈S1ρj⋅cj)+Epk(m0)=Epk(0)+Epk(m0)=Epk(m0)。因此， P 2 P_2 P2解密 c 0 c_0 c0将得到 m 0 m_0 m0。 - σ = 1 \sigma=1 σ=1的情况：
对每个 j j j， c j = E p k ( 1 ) , c j ′ = E p k ( 0 ) c_j=E_{pk}(1), c'_j=E_{pk}(0) cj=Epk(1),cj′=Epk(0)都成立。因此，和上一种情况类似，有： c 1 = ( ∑ j ρ j ′ ⋅ c j ′ ) + E p k ( m 1 ) = E p k ( 0 ) + E p k ( m 1 ) = E p k ( m 1 ) c_1=(\sum_{j}\rho'_j\cdot c'_j)+E_{pk}(m_1)=E_{pk}(0)+E_{pk}(m_1)=E_{pk}(m_1) c1=(∑jρj′⋅cj′)+Epk(m1)=Epk(0)+Epk(m1)=Epk(m1)。 P 2 P_2 P2解密 c 1 c_1 c1即可得到 m 1 m_1 m1。
Hazay-Lindell（2010）
原文下载链接
另外可以参考这本书，由大佬完成的，详细讲了安全计算协议和一些安全模型，以及不经意传输，数学理论性很强，一共200+页。。。
概率加密 ↩︎
R R R应该足够长，使不会有两次调用 R R R获得相同值的协议。也就是说，长度应该大于 2 log ( n ) 2\log(n) 2log(n)位，其中 n n n是协议的调用次数。或者，发送方可以使用计数器来设置 R R R的值，长度可以减少到 log n \log n logn。 ↩︎
该协议要求发送方提供一个公共字符串（不是密钥），或者依赖于非均匀性。 ↩︎
DDH：Decisional Diffie-Hellman ↩︎
假设可以验证公钥 p k pk pk在密钥生成算法 G G G的范围内。如果不能，则必须添加一个零知识证明。 ↩︎
如果 σ = 0 \sigma=0 σ=0那么 β j = b j \beta_j=b_j βj=bj。因此，如果 β j = b j = 0 \beta_j=b_j=0 βj=bj=0，有 c j = c j 0 = E p k ( 0 ) , c j ′ = c j 1 = E p k ( 1 ) c_j=c_j^0=E_{pk}(0), c'_j=c_j^1=E_{pk}(1) cj=cj0=Epk(0),cj′=cj1=Epk(1)。相反地，如果 β j = b j = 1 \beta_j=b_j=1 βj=bj=1，那么 c j = c j 1 = E p k ( 0 ) , c j ′ = c j 0 = E p k ( 1 ) c_j=c_j^1=E_{pk}(0), c'_j=c_j^0=E_{pk}(1) cj=cj1=Epk(0),cj′=cj0=Epk(1)。也就是说， σ = 0 \sigma=0 σ=0的所有情况都有 c j = E p k ( 0 ) , c j ′ = E p k ( 1 ) c_j=E_{pk}(0), c'_j=E_{pk}(1) cj=Epk(0),cj′=Epk(1)成立；同理， σ = 1 \sigma=1 σ=1则相反。 ↩︎
更多推荐
安全多方计算——不经意/茫然传输（Oblivious Transfer）构造方法小结
发布评论