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

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

weak(ly) one-way function
Определение 1 слабо односторонняя функция
Честная функция $f\colon\{0,1\}^*\to\{0,1\}^*$ называется слабо односторонней, если
  1. $f$ полиномиально вычислима;
  2. существует полином $p$ такой, что для любого полиномиального вероятностного алгоритма $\mathcal A$ неравенство \[ \Pr\left(\mathcal A(f(\widetilde u_n))\in f^{-1}(f(\widetilde u_n))\right) \leqslant1-\frac1{p(n)} \] выполняется для всех достаточно больших $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]), но имеет место следующий результат (см. [1], [2]).

Теорема 3
Если существуют слабо односторонние функции, то существуют и односторонние функции.
А именно, если $f$ — слабо односторонняя функция, то существует возрастающий полиномиальный параметр $k$ такой, что функция $\left(x_1,\dots,x_{k(n)}\right)\mapsto \left(f(x_1),\dots,f\left(x_{k(n)}\right)\right)$ ($x_1,\dots,x_{k(n)}\in\{0,1\}^n$, $n\in\mathbb N$) является односторонней. Существуют более эффективные способы построения односторонних перестановок из слабо односторонних перестановок (см. [3], [1], [2]).

Литература

  • [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)
  • [2] Luby, M. «Pseudorandomness and cryptographic applications» 1996
  • [3] Goldreich, O. and Impagliazzo, R. and Levin, L. and Venkatesan, R. and Zuckerman, D. «Security preserving amplification of hardness» 1990

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