基于仿真的半诚实对手不经意转移(OT)安全证明问题

Question

我目前正在阅读这个如何对其进行仿真--模拟验证技术教程。

在第10页，有一个对半诚实对手的1/2-OT模拟的证明.简单地说，播放器P_1保存消息b_0，b_1和播放器P_2保存选择位σ。因为P_1没有输出，所以它创建了一个仿真器(第11页底部-第12页中间)来模拟P_1的S视图。对于P_2，它再次创建一个模拟器(参见第12页，底部- p.14中间)，但是在模拟视图时，它不能完全输出B(α,x_{1-σ}) \oplus b_{1-σ}，所以它只输出B(α，x_{1-σ})。然后证明了后两个项的分布在计算上是不可区分的。它假设有一个区分器D (参见第13页，中间第14页，中间)，并且给D一个有效的算法A，可以打破找到B的预图像(这是一个硬核谓词)的概率可以忽略不计。

问题:基于以下定义。在第13页，它描述了假定的区分器D如下：

假设存在一个非均匀概率多项式时间区分器D，一个多项式p(·)和一个无限元组(σ, b_σ, n)，从而使得Pr[D(σ, r_0, r_1; α,(B(α, x_σ) \oplus b_σ, B(α, x_{1−σ}))) = 1] − Pr[D(σ, r_0, r_1; α,(B(α, x_σ) \oplus b_σ, B(α, x_{1−σ}) \oplus 1)) = 1] ≥ \dfrac{1}{p(n)}。

在第13页中间，它描述了算法\mathcal{A}：

算法\mathcal{A}在其通知磁带上给出σ，b_σ，并接收(1^n, α, r)作为输入。\mathcal{A}‘S的目标是猜测B(α, f^{−1}_{α}(S(α; r))。为了做到这一点，\mathcal{A}隐式地并且不知道它的实际值，通过设置r_{1−σ} = r (从它的输入)来设置D31。接下来，算法\mathcal{A}选择一个随机r_σ，并计算x_σ = S(α; r_σ)和β_σ = B(α, x_σ) \oplus b_σ。最后，\mathcal{A}选择一个随机的β_{1−σ}，在输入(σ, r_0, r_1; α,(β_σ, β_{1−σ}))上调用D，如果D输出为1，则输出β_{1−σ}，而1−β_1−σ则不然。请注意，如果\mathcal{A}正确地猜测了β_{1−σ}，那么它就会调用(σ, r_0, r_1; α,(B(α, x_σ) \oplus b_σ, B(α, x_{1−σ})))上的D，否则就会调用(σ, r_0, r_1; α,(B(α, x_σ) \oplus b_σ, B(α, x_{1−σ}) \oplus 1))上的D。因此，如果D输出1，那么\mathcal{A}假设它猜对了β_{1−σ} (因为D在给定B(α, x_{1−σ})时输出1的概率高于给定B(α, x_{1−σ}) \oplus 1)时的概率)。

为什么当\mathcal{A}选择一个随机的β_{1-σ}时，当它错误地猜测它就像用(σ, r_0, r_1; α,(B(α, x_σ) \oplus b_σ, B(α, x_{1−σ}) \oplus 1))调用D一样？为什么B(α, x_{1−σ}) \oplus 1)等同于随机β_{1-σ}？

Answer 1

为什么当\mathcal{A}错误地猜测时选择一个随机的\beta_{1-\sigma}时，它是使用(\sigma, r_0, r_1;\alpha, (B(\alpha, x_\sigma)\oplus b_\sigma, B(\alpha, x_{1-\sigma})\oplus 1))调用lik \mathcal{D}的呢？为什么(\alpha,x_{1−\sigma})\oplus1)等同于随机\beta_{1-\sigma}？

在这一部分中，我们对b_{1-\sigma}=1的仿真安全性进行了论证，定义如下：\underbrace{\{(..., B(\alpha, x_\sigma)\oplus b_\sigma, B(\alpha, x_{1-\sigma}))\}}_\text{ideal world} \approx \underbrace{\{(..., B(\alpha, x_\sigma)\oplus b_\sigma, B(\alpha, x_{1-\sigma}))\oplus 1)\}}_\text{real world} 然后通过矛盾证明，假设\mathcal{D}能够区分上述集合。另外，

在不失去通用性的情况下，我们假设对于无限多的n's，\mathcal{D}在接收B(\alpha, x_{1-\sigma})时输出1的概率大于或等于接收B(\alpha, x_{1-\sigma})\oplus 1时的概率。

在仿真过程中，\mathcal{A}生成\beta_\sigma和随机\beta_{1-\sigma} (不一定是均匀随机的)，然后将(\sigma, r_0, r_1; \alpha, (\beta_{\sigma}, \beta_{1-\sigma}))反馈给区分器\mathcal{D}。如果区分器输出1，则\mathcal{A}输出\beta_{1-\sigma}，如果区分器输出0，则\mathcal{A}输出1-\beta_{1-\sigma}。

在\mathcal{A}中，我们想证明：\underbrace{\{(..., B(\alpha, x_\sigma)\oplus b_\sigma, B(\alpha, x_{1-\sigma}))\}}_\text{ideal world} \approx \underbrace{\{\mathcal{A}(...)\}}_\text{real world} 回想起区分器\mathcal{D}的定义，

• 当\mathcal{D}(\cdot)=1，\mathcal{A}相信它以某种方式生成的\beta_{1-\sigma}是w.h.p。因此(在现实世界中)它输出B(\alpha, x_{1-\sigma})
• 当\mathcal{D}(\cdot)=0，\mathcal{A}相信它以某种方式生成的\beta_{1-\sigma}是w.h.p。因此(在现实世界中)它输出B(\alpha, x_{1-\sigma})\oplus 1