Односторонние функции
Определение
Функция $f\colon \{0, 1\}^{k(n)} \rightarrow \{0, 1\}^{l(n)}$ называется сильно односторонней, если $f$ вычисляется за время $poly(n)$ и
$$\forall p\ \forall\{R_n\}_{n = 1}^{\infty}\ \exists N\ \forall n > N\ Pr_{x \in \{0, 1\}^{k(n)}}\{f(R_n(f(x))) = f(x)\} < \frac{1}{p(n)}$$
Здесь $R_n$ -- семейства схем полиномиального размера
Определение
Функция $f\colon \{0, 1\}^{k(n)} \rightarrow \{0, 1\}^{l(n)}$ называется слабо односторонней, если $f$ вычисляется за время $poly(n)$ и
$$\exists q\ \forall\{R_n\}_{n = 1}^{\infty}\ \exists N\ \forall n > N\ Pr_{x \in \{0, 1\}^{k(n)}}\{f(R_n(f(x))) = f(x)\} < 1 - \frac{1}{q(n)}$$
Здесь $R_n$ - семейства схем полиномиального размера
Замечание
Любая сильно односторонняя функция является слабо односторонней. Достаточно взять $p = 2$.
Утверждение
Если существует слабо одностороняя функция, то $P \ne NP$
Доказательство
Рассмотрим для произвольной функции $f$ язык $L = \{y \in \{0, 1\}^{l(n)} \colon \exists x \in \{0, 1\}^{k(n)} f(x) = y\}$. Очевидно, $L \in NP$.
Если $P = NP$, то соответствующая задача поиска решается за полиномиальное время. А эта задача обращает $f(x)$.
Свойства
-
Если $f$ - односторонняя функция, то $h(x) = f(x)0\ldots0$ ($l(n)$ нулей) - односторонняя функция.
Дан $y$, хотим найти $x\colon f(x) = y$. Запишем $y$ дополненный $l(n)$ нулями, обратим $h$, получим $x$.
-
Если $f$ - одностороння функция, то $h(x) = f(x)f(x)$ (конкатенация) - односторонняя функция.
Дан $y$, хотим найти $x\colon f(x) = y$. Запишем $y$ два раза подряд, обратим $g$, получим $x$.
Определение
Функция $f\colon \{0, 1\}^{k(n)} \rightarrow \{0, 1\}^{l(n)}$ называется сильно односторонней в вероятностной схеме, если $f$ вычисляется за время $poly(n)$ и $$\forall p \forall\{R_n\}_{n = 1}^{\infty} \exists N \forall n > N Pr_{x \in \{0, 1\}^{k(n)}, r}\{f(R_n(f(x), r)) = f(x)\} < \frac{1}{p(n)}$$
Здесь $R_n$ - семейства схем полиномиального размера
Предложение
Сильно односторонняя функция является сильно односторонней в вероятностной схеме и наоборот
Примеры предположительно односторонних функций:
Умножение (cлабо односторонняя функция)
$f(x) = x \cdot y$
$|x| = |y| = n$SUBSET-SUM
$(n_1,\ldots,n_k, s) \rightarrow (n_1,\ldots,n_k, N)$, $|s| = k$
$N = \sum_{i\colon s_i = 1}n_i$
Теорема
Если существует сильно односторонняя функция, то существует слабо одностороняя функция, не являющаяся сильно односторонней.
Доказательство
Пусть $f$ -- сильно односторонняя. Определим $g$ следующими равенствами:
$$g(x0) = f(x)0$$
$$g(x1) = x1$$
Такая $g$ - слабо односторонняя, ибо если ее можно обратить с вероятностью $\frac{2}{3}$, то ее можно обратить в первом случае с вероятностью $\frac{1}{3}$. Тогда и $f$ можно обратить с такой вероятностью, а значит, $f$ -- не сильно односторонняя.
Предложение
Посмотрим на два высказывания о функции $f$:
$$\forall \{R_n\}\ \exists p(\cdot)\ \exists N\ \forall n > N\ Pr\{f(R_n(f(x))) = f(x)\} < 1 - \frac{1}{p(n)}$$
$$\exists p(\cdot)\ \forall \{R_n\}\ \exists N\ \forall n > N\ Pr\{f(R_n(f(x))) = f(x)\} < 1 - \frac{1}{p(n)}$$
Второе из них -- определение того, что $f$ слабо непрерывна. Очевидно, что из второго следует первое. На самом деле, эти утверждения равносильны.
Теорема
Если существует слабо одностороняя функция, то существет сильно одностороняя функция.
Идея доказательства
$F(x_1,\ldots,x_N) = f(x_1)\ldots f(x_N)$
Пусть обратитель $F$ пытается обратить все компоненты по отдельности. Тогда вероятность успеха $\le \left(1 - \frac{1}{q(n)}\right)^N = l^{-n}$
Нужно по обратителю $F$ построить обратитель $f$.
$S(y)\colon$ запуск $R(y, f(x_2),\ldots,f(x_N))$, проверка успешности
запуск $R(y, f(x_2),\ldots,f(x_N))$, проверка успешности
запуск $R(y, f(x_2),\ldots,f(x_N))$, проверка успешности
Достаточно доказать следующее утверждение:
Если $R$ успешен с вероятностью $\ge \frac{1}{p(n)}$, то
$$\forall q\ \exists m\ S\ \text{успешен с вероятностью} \ge 1 - \frac{1}{q(n)}$$
Доказательство
$$S_1(x) = Pr_{x_2,\ldots,x_n}\{f(R_1(f(x), f(x_2),\ldots,f(x_N))) = f(x)\}$$
$$S_i(x) = Pr_{x_1,\ldots,x_{i - 1}, x_{i + 1},\ldots,x_N}\{f(R_1(f(x_1),\ldots,f(x_{i - 1}), f(x), f(x_{i + 1}),\ldots,f(x_N))) = f(x)\}$$ Вероятность успеха 1 шага $S \ge max\{S_1(x),\ldots,S_N(x)\}$
Если $max S_i(x) > \frac{1}{poly(n)}$, тогда за счет выбора $m$ можно повысить вероятность успеха до $1 - \frac{1}{q(n)}$ таких $x$, что $max S_i(x) < \frac{1}{poly(n)}$, мало.