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

Функция дистрибутивно односторонняя

distributionally one-way function
Синонимы: функция информационно односторонняя
Определение 1 дистрибутивно односторонняя функция
Честная функция $f\colon\{0,1\}^*\to\{0,1\}^*$ называется дистрибутивно односторонней, если
  1. она полиномиально вычислима;
  2. существует полином $p$ такой, что для любого полиномиального вероятностного алгоритма $\mathcal A$ статистическое расстояние между случайными величинами $(\widetilde u_n,f(\widetilde u_n))$ и $(\mathcal A(f(\widetilde u_n)),f(\widetilde u_n))$ больше $1/p(n)$ всех достаточно больших $n\in\mathbb N$.

Неформально условие 2 этого определения означает, что для $x\in_{\mathfrak U}\{0,1\}^n$ задача генерации случайных элементов $f^{-1}(f(x))$ относительно распределения вероятностей, близкого к равномерному на этом множестве, вычислительно трудна.

Понятие дистрибутивно односторонней функции было введено в работах [1], [2] (см. также работу [3], где такие функции назывались информационно односторонними). Значение этого примитива состоит в том, что исходя из стойких криптографических протоколов, рассматриваемых в работах [1] и [2], можно построить дистрибутивно односторонние функции более простым способом, чем односторонние или слабо односторонние. В то же время, как показывает следующая теорема (см. [1], [2], [4]), существование дистрибутивно односторонних функций эквивалентно существованию односторонних функций.

Теорема 2
Всякая слабо односторонняя функция является дистрибутивно односторонней. Кроме того, если существуют дистрибутивно односторонние функции, то существуют и односторонние функции.

Литература

  • [1] Impagliazzo, R. and Luby, M. «One-way functions are essential for complexity based cryptography» 1989
  • [2] Impagliazzo, R. and Luby, M. «One-way functions are essential for complexity based cryptography» 1989
  • [3] Impagliazzo, R. and Luby, M. «Pseudo-random number generator from any one-way function» 1989
  • [4] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)

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