Односторонние функции

Определение

Функция $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)$.

---

Свойства

1. Если $f$ - односторонняя функция, то $h(x) = f(x)0\ldots0$ ($l(n)$ нулей) - односторонняя функция.

   Дан $y$, хотим найти $x\colon f(x) = y$. Запишем $y$ дополненный $l(n)$ нулями, обратим $h$, получим $x$.

2. Если $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$ - семейства схем полиномиального размера

---

Предложение

Сильно односторонняя функция является сильно односторонней в вероятностной схеме и наоборот

---

Примеры предположительно односторонних функций:

1. Умножение (cлабо односторонняя функция) 
   $f(x) = x \cdot y$ 
   $|x| = |y| = n$

2. 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)}$, мало.

---