Теорема о существовании генератора

Теорема

Если существует односторонняя перестановка, то существует и генератор псевдослучайных чисел.

Доказательство

Проводится в три этапа:

1. Односторонняя перестановка $\implies$ односторонняя перестановка с трудным битом: $g(x, y) = (f(x), y)$ $\beta(x, y) = x \odot y = \oplus_{i = 1}^{n} x_i y_i$
2. Односторонняя перестановка с трудным битом $\implies$ Генератор $n \rightarrow n + 1$
3. Генератор $n \rightarrow n + 1$ $\implies$ Генератор $n \rightarrow p(n)$

Идея последнего шага
$x \mapsto g(x)h(x) \mapsto g(g(x))h(g(x))h(x) \mapsto g(g(g(x)))h(g(g(x)))h(g(x))h(x) \mapsto \ldots$

---

Лемма 2

$\beta(x)$ - трудный бит для $f(x) \Leftrightarrow x \mapsto f(x)\beta(x)$ - генератор.

####Доказательство

Сперва построим генератор псевдослучайных чисел, отображающий $n$ битов в $p(n)$, имея генератор псевдослучайных чисел $(n \mapsto n + 1)$.

По генератору $G(x) = g(x)h(x)$ построим $G'(x) = h(x)h(g(x))h(g(g(x)))\ldots$

Утверждение

Если $G(x)$ - генератор псевдослучайных чисел, то $G'(x)$ - генератор псевдослучайных чисел.

Доказательство

Осталось по односторонней перестановке построить одностороннюю перестановку с трудным битом. Но сперва поговорим немного о кодах Адамара.

Теорема (Голдрайх-Левин)

Если $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^n$ - односторонняя перестановка, то $g: \{0, 1\}^{2n} \rightarrow \{0, 1\}^{2n}$, $g(x, y) = (f(x), y)$ - тоже односторонняя перестановка, а $h(x, y) = x \odot y$ - трудный бит для $g$.

Теорема(О кодах Адамара или о списочном декодировании)

Пусть $h_x(y) = x \odot y$ - код Адамара слова $x \in \{0, 1\}^n$. Пусть $\bar{h}(y)$ - такая функция, что доля $y$ удовлетоворяющих $\bar{h}(y) = h_x(y)$ больше либо равна $\frac{1}{2}$. Тогда существует вероятностный алгоритм, работающий $poly(\frac{n}{\varepsilon})$, имеющий произвольный доступ к $\bar{h}$, выдающий список слов длины $n$, с вероятностью $\ge \frac{1}{2}$ содержит $x$.

Почему это называется декодированием списка? Вообще кодирование нужно для исправления ошибок. Код Адамара - длинный код. Точного полиномиального алгоритма декодирования не существует. $h$ - код, $\bar{h}$ - испорченный код.

Теорема

Из теоремы о списочном декодировании выводится теорема Голдрайха-Левина.

Доказательство

Теорема (ЗБЧ для попарно независимых случайных величин)

Пусть $\xi_1, \ldots, \xi_N$ - попарно независимые одинакого распределенные, бернулиевские случайные величины. $E\xi_i = \frac{1}{2} - \varepsilon$. Тогда $$Pr\{\xi_1 + \ldots \xi_N \ge \frac{1}{2}N\} \le \frac{1}{\varepsilon^2}\frac{1}{N}$$

Доказательство ЗБЧ

Доказательство теоремы о списочном декодировании