Интерактивный протокол
В предыдущем подходе получатель играл пассивную роль. Построим протокол в котором он будет что-то делать.
Интерактивный протокол - 3 алгоритма: $R$, $S$, $T$. $R$, $S$ - вероятностные полиномиальные алгоритмы. $T$ - детерминированный полиномиальный алгоритм, котороый получает протокол общения и должен сказать, что же там было запечатано. Он возвращает $0, 1$ либо ошибки $\perp_R, \perp_S$.
2 фазы протокола:
Привязка . $< R, S(\sigma) >$- протокол общения $R$ и $S$.
Раскрытие. $S$ посылает свои биты $S$.
Требования:
$T(, S) = \sigma$ - требование корректности.
$T(, s) \in \{\sigma, \perp_R\}$ - усиленная корректность. (Жульничающий $R$ не может заставить $S$ привязаться к другому биту).
$\forall S^*\ \exists \sigma^*\ \forall s^*\ T(, S^*) \in \{\sigma^*, \perp_S\}$ - требование надежности.
$< R^*, S(0) >$ и $< R^*, S(1) >$ вычислительно не отличимы. (До раскрытия R ничего не узнает о бите, то есть все, что он увидит будет вычислительно неотличимо друг от друга.)
Конструкция на базе генератора $G\colon \{0, 1\}^{n} \mapsto \{0, 1\}^{3n}$: $$S \xleftarrow{r\in \{0, 1\}^{3n}} R,\ \text{r - случайное}$$ $S$ выбирает случайное $s \in \{0, 1\}^n$ $$S \longrightarrow R$$ $T$ получает $q$ - сообщение $R$, $m$ - сообщение $S$, $s$ - случайные биты $S$. $$T(q, m, s) = \begin{cases} 0 & \text{при } m \oplus G(s) = 0^{3n} \\ 1 & \text{при } m \oplus G(s) = q \\ \perp_S & \text{иначе} \end{cases}$$ Вычислительная неотличимость: $(q, G(s)) \sim (q, t) \sim (q, t \oplus q) \sim (q, G(s) \oplus q)$, где $t$ - случайное, длины $3n$.
Надежность - выполнена с вероятностью (по $r \in \{0, 1\}^{3n}$) не меньше $1 - \frac{1}{2^n}$. Покажем это рассмотрев неоднозначное раскрытие:
$\exists s_1\ m \oplus G(s_1) = 0^{3n}$ и $\exists s_2\ m \oplus G(s_2) = r$.
При выполнении обоих условий $\exists s_1, s_2\ G(s_1) \oplus G(s_2) = r$. Вероятность этого не превосходит $\frac{2^{2n}}{2^{3n}} = 2^{-n}$.