1
$\begingroup$

I'm currently reading this How To Simulate It – A Tutorial on the Simulation Proof Technique.

On p. 10, there is a proof using simulation for 1/2-OT, against semi-honest adversaries. Briefly, the player $P_1$ holds the messages $b_0$, $b_1$ and the player $P_2$ hold the choice bit $σ$. Since $P_1$ has no output, it creates a simulator (p.11 bottom - p.12 middle) that simulates the $P_1$'s view. For $P_2$ it creates again a simulator (see p.12 bottom - p.14 middle) but while simulating the view it cannot output exactly $B(α,x_{1-σ}) \oplus b_{1-σ}$ so it just outputs B(α,x_{1-σ}). Then it proves that the distributions of the last two terms are computationally indistinguishable. It assumes that there is a distinguisher $D$ (see p. 13 middle - p. 14 middle) and that given $D$ an efficient algorithm $A$ can be created that can break find the pre-image of $B$ (which is a hardcore predicate) with negligible probability.

Question : Based on the following definitions. On p.13 it describes that assumed distinguisher $D$ as follows :

Assume by contradiction that there exists a non-uniform probabilistic polynomial time distinguisher $D$, a polynomial $p(·)$ and an infinite series of tuples $(σ, b_σ, n)$ such that $$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)}$$ .

On p. 13 middle it describes algorithm $\mathcal{A}$ :

Algorithm $\mathcal{A}$ is given $σ$, $b_σ$ on its advice tape, and receives $(1^n, α, r)$ for input. $\mathcal{A}$’s aim is to guess $B(α, f^{−1}_{α}(S(α; r))$. In order to do this, implicitly and without knowing its actual value, $\mathcal{A}$ sets $x_{1−σ} = f^{−1}_{α} (S(α; r))$ by setting $r_{1−σ} = r$ (from its input). Next, algorithm $\mathcal{A}$ chooses a random $r_σ$, and computes $x_σ = S(α; r_σ)$ and $β_σ = B(α, x_σ) \oplus b_σ$. Finally, $\mathcal{A}$ chooses a random $β_{1−σ}$, invokes $D$ on input $(σ, r_0, r_1; α,(β_σ, β_{1−σ}))$ and outputs $β_{1−σ}$ if $D$ outputs 1, and $1−β_1−σ$ otherwise. Observe that if $\mathcal{A}$ guesses $β_{1−σ}$ correctly then it invokes $D$ on $(σ, r_0, r_1; α,(B(α, x_σ) \oplus b_σ, B(α, x_{1−σ})))$, and otherwise it invokes $D$ on $(σ, r_0, r_1; α,(B(α, x_σ) \oplus b_σ, B(α, x_{1−σ}) \oplus 1))$. Thus, if D outputs 1, then $\mathcal{A}$ assumes that it guessed $β_{1−σ}$ correctly (since $D$ outputs 1 with higher probability when given $B(α, x_{1−σ})$ than when given $B(α, x_{1−σ}) \oplus 1)$.

Why while $\mathcal{A}$ chooses a random $β_{1-σ}$, when it guesses incorrectly it is like $D$ is invoked with $(σ, r_0, r_1; α,(B(α, x_σ) \oplus b_σ, B(α, x_{1−σ}) \oplus 1))$? Why is $B(α, x_{1−σ}) \oplus 1)$ equivalent to a random $β_{1-σ}$?

$\endgroup$

1 Answer 1

2
$\begingroup$

Why while $\mathcal{A}$ chooses a random $\beta_{1-\sigma}$ when it guesses incorrectly, it is lik $\mathcal{D}$ is invoked with $(\sigma, r_0, r_1;\alpha, (B(\alpha, x_\sigma)\oplus b_\sigma, B(\alpha, x_{1-\sigma})\oplus 1))$?

Why is $𝐵(\alpha,x_{1−\sigma})\oplus1)$ equivalent to a random $\beta_{1-\sigma}$?

During this part, we are proving the simulation security for the case of $b_{1-\sigma}=1$, the definition is as follows, $$ \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} $$ Then prove by contradiction, we assume $\mathcal{D}$ could distinguish the above ensembles. Also,

Without loss of generality, we assume that for infinitely many $n$'s, $\mathcal{D}$ outputs 1 with greater or equal probability when receiving $B(\alpha, x_{1-\sigma})$ than when receiving $B(\alpha, x_{1-\sigma})\oplus 1$

During the simulation process, $\mathcal{A}$ generates $\beta_\sigma$ and a random $\beta_{1-\sigma}$ (not necessarily to be uniformly random), then feed $(\sigma, r_0, r_1; \alpha, (\beta_{\sigma}, \beta_{1-\sigma}))$ to the distinguisher $\mathcal{D}$. And if distinguisher outputs $1$, $\mathcal{A}$ outputs $\beta_{1-\sigma}$, and if distinguisher outputs $0$, $\mathcal{A}$ outputs $1-\beta_{1-\sigma}$.

With $\mathcal{A}$, we want to prove that: $$ \underbrace{\{(..., B(\alpha, x_\sigma)\oplus b_\sigma, B(\alpha, x_{1-\sigma}))\}}_\text{ideal world} \approx \underbrace{\{\mathcal{A}(...)\}}_\text{real world} $$ Recall the definition of distinguisher $\mathcal{D}$,

  • When $\mathcal{D}(\cdot)=1$, $\mathcal{A}$ believe that its somehow generated $\beta_{1-\sigma}$ is w.h.p. close to $B(\alpha, x_{1-\sigma})$, therefore (in the real world) it outputs $\beta_{1-\sigma}$
  • When $\mathcal{D}(\cdot)=0$, $\mathcal{A}$ believe that its somehow generated $\beta_{1-\sigma}$ is w.h.p. close to $B(\alpha, x_{1-\sigma})\oplus 1$, therefore (in the real world) it outputs $1-\beta_{1-\sigma}$
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.