Неинтерактивный протокол
Неинтерактивный протокол - пара ($S$, $R$). $S$, $R$ - вероятностные полиномиальные алгоритмы. $R$ может быть и детерминированным при условии, что $S$ - полиномиальный в среднем. $S$ получает бит; при помощи этого бита делает две вещи: $c$ - привязку и $k$ - ключ. $$S\colon \sigma \mapsto c, k$$ $$R\colon c, k \mapsto \{0, 1, \perp\}$$ Требования:
$R(c_{\sigma}, k_{\sigma}) = \sigma$ (в вероятностном случае вероятность стремится быстрее любого полинома). Это требование в интересах получателя.
$R(c_{\sigma}, k^*) \in \{\sigma, \perp\}$ - так же требование получателя.
$c_0$ и $c_1$ - вычислительно не отличимы. (Из первых двух требований следует, что $c_0$ и $c_1$ должны принимать значения из разных множеств).
Конструкция на базе односторонеей перестановки. Если есть одностороняя перестановка, то можно построить перестановку с трудным битом. Пусть $g$ - односторонняя перестановка, а $h$ - трудный бит. Тогда: $$c_{\sigma} = (\sigma \oplus h(x), g(x))$$ $$k_{\sigma} = x$$ Из-за того, что $h$ - трудный бит, $(h(x), g(x))$ вычислительно не отличимо от $(r, g(x))$, то $(\sigma\oplus h(x), g(x))$ вычислительно не отличимо от $(\sigma \oplus r, g(x))$, что не отличимо от $(r, g(x))$. Отсюда следует $c_0$ вычислительно не отличимо от $c_1$.
$$R((b, y), k) = \begin{cases} b \oplus h(k) & \text{при } g(k) = y \\ \perp & \text{при } g(k) \ne y \end{cases}$$ $g$ - перестановка, следовательно $g(k) \ne g(k')$ при $k \ne k'$.