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

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

one-way function
Синонимы: функция сильно односторонняя

Говоря неформально, односторонней называется полиномиально вычислимая честная функция $f\colon\{0,1\}^*\to\{0,1\}^*$, задача инвертирования которой неразрешима за полиномиальное время. В настоящее время односторонняя функция — гипотетический объект.

Определение 1 односторонняя функция
Честная функция $f\colon\{0,1\}^*\to\{0,1\}^*$ называется односторонней, если
  1. $f$ полиномиально вычислима;
  2. для любого полиномиального вероятностного алгоритма $\mathcal A$ величина $\Pr\left(\mathcal A(f(\widetilde u_n))\in f^{-1}(f(\widetilde u_n))\right)$ пренебрежимо мала как функция от $n\in\mathbb N$.

Иногда в определении односторонней функции не требуют честности и предполагают, что на вход алгоритму $\mathcal A$ в условии 2 вместе с $f(\widetilde u_n)$ подается $1^n$ (см. [1]). Тогда очевидно, что если функция $f\colon\{0,1\}^*\to\{0,1\}^*$ удовлетворяет условиям определения 1, то она удовлетворяет также условиям данной модификации этого определения. Наоборот, если эта функция удовлетворяет условиям данной модификации определения 1, то функция $x\mapsto\left(1^{\lvert{x}\rvert},f(x)\right)$ ($x\in\{0,1\}^*$) удовлетворяет условиям определения 1.

Определение 1 очевидным образом переносится на случай, когда $f$ определена лишь на $\bigcup_{i\in I}\{0,1\}^i$, где $I$ — бесконечное подмножество $\mathbb N$. Пусть $I$ — полиномиально перечислимое множество, а $f\colon\bigcup_{i\in I}\{0,1\}^i\to\{0,1\}^*$ — односторонняя функция. Тогда $f$ может быть продолжена на все множество $\{0,1\}^*$ с сохранением односторонности (см. [1]).

В теории сложности вычислений известно понятие односторонней функции, формализующей трудность инвертирования в худшем случае. Это понятие не имеет значения для математической криптографии и поэтому в настоящем справочнике не рассматривается.

В настоящем справочнике упоминается понятие односторонней функции в неоднородной модели вычислений. Это определение получается из определения 1 заменой условия 2 на следующее:
  1. если $(C_n\,|\, n\in\mathbb N)$ — семейство булевых схем в произвольном конечном полном базисе такое, что для любого $n\in\mathbb N$ размер схемы $C_n$ не превосходит $p(n)$ (где $p$ — некоторый полином) и эта схема имеет $n$ битовых входов, то величина $\Pr\left(C_{\lvert{f(\widetilde u_n)}\rvert}(f(\widetilde u_n))\in f^{-1}(f(\widetilde u_n))\right)$ пренебрежимо мала как функция от $n\in\mathbb N$.
См. также [1]. Разумеется, функция, являющаяся односторонней в неоднородной модели вычислений, будет таковой и в однородной модели вычислений (см. также [1]).

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

Предложение 2
Если существуют односторонние функции, то существуют и односторонние функции, сохраняющие длину.
Важность понятия односторонней функции подчеркивается тем, что существование односторонних функций необходимо для существования почти всех важных криптографических примитивов и стойких криптографических протоколов (см. [2], [3]). С другой стороны, многие такие примитивы и протоколы (например, псевдослучайные генераторы, генераторы псевдослучайных функций, генераторы псевдослучайных перестановок, универсальные односторонние семейства хэш функций, протоколы доказательства с вычислительно нулевым разглашением для языков из $\mathrm{PSPACE}$, протоколы электронной подписи, стойкие против экзистенциальной подделки на основе адаптивной атаки с выбором сообщений) удалось построить, исходя из предположения о существовании произвольных односторонних функций (соответствующие результаты формулируются в статьях, посвященных этим примитивам и протоколам).

Литература

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

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