Теорема о существовании генератора
Теорема
Если существует односторонняя перестановка, то существует и генератор псевдослучайных чисел.
Доказательство
Проводится в три этапа:
- Односторонняя перестановка $\implies$ односторонняя перестановка с трудным битом: $g(x, y) = (f(x), y)$ $\beta(x, y) = x \odot y = \oplus_{i = 1}^{n} x_i y_i$
- Односторонняя перестановка с трудным битом $\implies$ Генератор $n \rightarrow n + 1$
- Генератор $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}$$