сейчас я читаю это Как смоделировать это — Учебное пособие по методу доказательства с помощью симуляции.
На стр. 10, есть доказательство с использованием моделирования для 1/2-OT против получестных противников. Вкратце, игрок $P_1$ держит сообщения $b_0$, $b_1$ и игрок $P_2$ держите бит выбора $Ï$. С $P_1$ не имеет выходных данных, он создает симулятор (стр. 11 внизу - стр. 12 посередине), который имитирует $P_1$взгляд. За $P_2$ он снова создает симулятор (см. стр. 12 внизу - стр. 14 посередине), но при имитации вида он не может точно выводить $B(α,x_{1-Ï}) \oplus b_{1-Ï}$ поэтому он просто выводит B(±,x_{1-Ï}). Затем это доказывает, что распределения последних двух членов вычислительно неразличимы. Предполагается, что существует отличительная черта $Д$ (см. стр. 13 середина - стр. 14 середина) и что дано $Д$ эффективный алгоритм $А$ может быть создано, что может сломать найти прообраз $В$ (что является жестким предикатом) с незначительной вероятностью.
Вопрос :
На основании следующих определений.
На стр.13 описывается, что предполагаемый отличительный признак $Д$ следующее :
Предположим от противного, что существует неравномерный
вероятностный полиномиальный различитель времени $Д$, многочлен $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{А}$ :
Алгоритм $\mathcal{А}$ дано $Ï$, $b_Ï$ по его совету ленты, и получает $(1^n, ±, г)$ для ввода. $\mathcal{А}$✓ цель - угадать $B(α, f^{â1}_{α}(S(α; r))$. Для того, чтобы сделать это, неявно и не зная его фактической стоимости, $\mathcal{А}$ наборы $x_{1âÏ} = f^{â1}_{α} (S(α; r))$ установив $r_{1âÏ} = r$ (с его входа).Далее алгоритм $\mathcal{А}$ выбирает случайный $r_Ï$, и вычисляет $x_Ï = S(α; r_Ï)$ и $β_Ï = B(α, x_Ï) \oplus b_Ï$. В заключение, $\mathcal{А}$ выбирает случайный $β_{1âÏ}$, вызывает $Д$ при вводе $(Ï, r_0, r_1; α,(β_Ï, β_{1âÏ}))$ и результаты $β_{1âÏ}$ если $Д$ выходы 1 и $1$ в противном случае. Заметьте, что если $\mathcal{А}$ догадки $β_{1âÏ}$ правильно, то он вызывает $Д$ на $(Ï, r_0, r_1; α,(B(α, x_Ï) \oplus b_Ï, B(α, x_{1âÏ})))$, а в противном случае он вызывает $Д$ на $(Ï, r_0, r_1; α,(B(α, x_Ï) \oplus b_Ï, B(α, x_{1âÏ}) \oplus 1))$. Таким образом, если
D выводит 1, затем $\mathcal{А}$ предполагает, что угадал $β_{1âÏ}$ правильно (поскольку $Д$
выводит 1 с большей вероятностью, когда задано $B(α, x_{1âÏ})$ чем когда дано $B(α, x_{1âÏ}) \oplus 1)$.
Почему пока $\mathcal{А}$ выбирает случайный $β_{1-Ï}$, когда он угадывает неправильно, это похоже на $Д$ вызывается с $(Ï, r_0, r_1; α,(B(α, x_Ï) \oplus b_Ï, B(α, x_{1âÏ}) \oplus 1))$? Почему $B(α, x_{1âÏ}) \oplus 1)$ эквивалентно случайному $β_{1-Ï}$?
