Протокол с закрытым ключом
Здесь будет две стороны $P$ - proover, и $V$ - verificator. Через закрытый канал они оба знают $d$ - закрытый ключ. Соответсвенно, есть протокол (вероятностный алгоритм) генерации ключей $K$. $P$, $V$ - интерактивные вероятностные алгоритмы. В конце $V$ выдает $0$ или $1$.
Условия:
Корректность: $$Pr\{V^{P(d)}(d) = 1\} \simeq 1$$
Надежность: Злоумышленник запустил программу $C$ она $k$ раз пообщалась с правильным $P$ после этого она пошла к верификатору и попыталась выступить в качестве прувера. Сделать это ей не должно удасться. $$\forall C\ \forall k\ Pr\{V^{C^{P^k(d)}}(d) = 1\} \simeq 0$$
Потребуются псевдослучайные функции. Что это такое? Что значит делать запросы к случайной функции? Это значит, что если зафиксированы области значения и определения, то случайно выбирается одна из понятно скольких (двойная экспонента). Псевдослучайных функций хорошо бы чтобы была одинарная экспонента, чтобы можно было записывать номер строкой полиномиальной длины.
ПСФ - семейство $f_e\colon \{0, 1\}^n \mapsto \{0, 1\}^n$, $e \in \{0, 1\}^{k(n)}$.
Вычислимость: $e, x \mapsto f_e(x)$ - вычисляется полиномиальным алгоритмом.
Неотличимость: пусть $C_n$ - схемы полиномиального размера с оракульным доступом к $f$ (то есть алгоритмы с подсказкой для всех входов данной длины и оракулом) $$\forall C_n\ Pr_e\{C_n^{f_e} = 1\} \simeq Pr_f\{C_n^f = 1\}$$ Идея в том, что эта схема может вычислить значения в полиномиальном числе точек и пытается отличить.
Конструкция: рассматривается генератор псеводослучайных чисел $G\colon \{0, 1\}^n \mapsto \{0, 1\}^{2n}$. Если $e = \varepsilon$, то $f_e(x) = x$. $G(x) = G_0(x)G_1(x)$ ($G_0(x), G_1(x)$ - два слова длины $n$). Если $|e| = 1$, то $f_e(x) = G_e(x)$. Если $|e| = 2, e = e_1 e_2$, то $f_e(x) = G_{e_2}(G_{e_1}(x))$. И так далее.
Закрытый ключ - индекс ПСФ. $P$ говорит $V$ вычисли функцию в такой то точке: $$P \xleftarrow{x} V$$ $$P \xrightarrow{f_d(x)} V$$