Список обозначений

Неотличимость вычислительная

computational indistinguishability
Синонимы: неотличимость за полиномиальное время

Говоря неформально, семейства дискретных распределений вероятностей вычислительно неотличимы, если для любого полиномиального вероятностного алгоритма они выглядят почти одинаково. Другими словами, произвольный полиномиальный вероятностный алгоритм почти не имеет шансов отличить одно из этих семейств от другого.

Пусть $(\mathfrak X_i\,|\, i\in I)$ и $(\mathfrak Y_i\,|\, i\in I)$ — семейства распределений вероятностей на множестве $\{0,1\}^*$, индексированные одним и тем же бесконечным множеством $I$, являющимся подмножеством $\{0,1\}^*$ или $\mathbb N$.

Определение 1 вычислительная неотличимость семейств распределений вероятностей
Вышеуказанные семейства распределений вероятностей $(\mathfrak X_i\,|\, i\in I)$ и $(\mathfrak Y_i\,|\, i\in I)$ называются вычислительно неотличимыми, если для любого полиномиального вероятностного алгоритма $\mathcal D$ величина \[ \lvert{\Pr(\mathcal D(i,x_i)=1)-\Pr(\mathcal D(i,y_i)=1)}\rvert\quad(\text{при }I\subseteq\{0,1\}^*), \] или \[ \left\lvert{\Pr\left(\mathcal D\left(1^i,x_i\right)=1\right)-\Pr\left(\mathcal D\left(1^i,y_i\right)=1\right)}\right\rvert\quad(\text{при }I\subseteq\mathbb N), \] где $x_i\leftarrow\mathfrak X_i$, $y_i\leftarrow\mathfrak Y_i$, пренебрежимо мала как функция от $i\in I$.

Определение вычислительной неотличимости естественным образом переносится на семейства случайных величин $(\widetilde x_i\,|\, i\in I)$ и $(\widetilde y_i\,|\, i\in I)$, принимающих значения в множестве $\{0,1\}^*$ и индексированных одним и тем же бесконечным множеством $I$, являющимся подмножеством $\{0,1\}^*$ или $\mathbb N$. А именно, указанные семейства случайных величин называются вычислительно неотличимыми, если вычислительно неотличимы семейства распределений вероятностей $(\mathfrak X_i\,|\, i\in I)$ и $(\mathfrak Y_i\,|\, i\in I)$, где $\mathfrak X_i$ и $\mathfrak Y_i$ — распределения вероятностей случайных величин $\widetilde x_i$ и $\widetilde y_i$ соответственно ($i\in I$).

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна