\documentclass{article} \usepackage[russian]{babel} \usepackage{amssymb} \usepackage{amsmath} \usepackage{supertabular} \usepackage{graphics} \title{Псевдослучайные функции} \author{Ю. Лифшиц\thanks{Законспектировал А. Калюкин.}.} \begin{document} \maketitle \section*{План лекции} \begin{enumerate} \item Предсказание следующего бита \item Псевдослучайные функции \item Стойкость против восстановления ключа \item Задачи \end{enumerate} \par \section{Предсказание следующего бита} {\bf Определение:} Функция $ G : X \mapsto Y$ называется псевдослучайным генератором, если $ G (\mathcal{U}_X)$ и $\mathcal{U}_Y$ вычислительно неразличимы ($\mathcal{U}_X$ ; $\mathcal{U}_Y$ : равномерные распределения). \par Неформально, генератор должен проходить все полиномиальные тесты на случайность. То есть никакой полиномиальный алгоритм не сможет отличить полностью случайную последовательность от созданной генератором. \par \medskip {\bf Вопрос:} Есть ли какой-нибудь конкретный тест, из которого следует случайность по всем остальным? \par {\bf Ответ:} Да, есть. Этот тест - предсказание следующего бита. \par \medskip {\bf Определение:} Распределение $D$ ( $D = G(X)$ - последовательность создаваемая генератором ) проходит тест на предсказание следующего бита, если для любого полиномиального алгоритма $A$ и любого $p$ верно: $$\textrm{Pr}_{t\in D}[A(t_1,\dots,t_p)=t_{p+1}]<\frac{1}{2}+\nu(|t|)$$ \par Пусть кто-то написал полиномиальный алгоритм $А$, который предсказывает следующий бит. Тогда возьмём последовательности, созданные генератором $G$, с вероятностями $a, b, c, d, \ldots{}$ Затем берём $p$ бит из одной и загружаем в $А$. Если алгоритм угадывает следующий бит, то получаем выигрыш = вероятности последовательности. Если общий выигрыш ($\textrm{Pr}_{t\in D}[A(t_1,\dots,t_p)=t_{p+1}]$) не слишком больше $\frac{1}{2}$, то генератор $G$ псевдослучаен. \par \medskip Говорят, что генератор $G$ проходит тест на следующий бит, если распределение его выходов проходит этот тест. \newtheorem{theorems}{Теорема} \begin{theorems} Если функция $G : \{0, 1\}^n \mapsto \{0, 1\}^N$ проходит тест на следующий бит $IFF$, то она является псевдослучайным генератором (проходит все полиномиальные тесты). \end{theorems} {\bf Доказательство:} {\bf (} $\Rightarrow$ {\bf )} Очевидно. \par {\bf (} $\Leftarrow$ {\bf )} Докажем, что если $G$ проваливает какой-то полиномиальный тест $А$, то $G$ проваливает и некоторый тест $A'$ на предсказание следующего бита. Используем для этого гибридный метод!!! \par \medskip У нас есть распределение $G_N$ , порожденное $G$. Определим $G'_k$ как распределение префиксов длины к на выходах $G$. Будем случайно и равновероятно дописывать каждый префикс случайными битами до длины $N$. Получим распределение $G_k$. \par \medskip {\bf Наблюдение:} $G_0 = U$, и при росте к распределение постепенно становится всё более "псевдослучайным". \par \medskip Применяем гибридный метод: алгоритм $А$ различает $G_0$ и $G_n$, значит для какого-то к он различает $G_k$ и $G_{k+1}$!!! \par \medskip Пусть $A = 1$ чаще на $G_{k+1}$. \par Тест $A'$: \begin{enumerate} \item Получает биты $t_1,\dots,t_k$ \item Выписывает строки $T_0=t_1,\dots,t_k,0,r_{k+2},\dots,r_N$ и \mbox{$T_1=t_1,\dots,t_k,1,r_{k+2},\dots,r_N$} \item Вычисляет $a_0=A(T_0)$ и $a_1=A(T_1)$ \item Если $a_0=0, a_1=1$, выдает ``$t_{k+1}=1$'' \item Eсли $a_0=1, a_1=0$, выдает ``$t_{k+1}=0$'' \item Eсли $a_0=a_1$, выдает случайный ответ \end{enumerate} \section{Псевдослучайные функции} {\bf Определение:} Функция $F:K\times D\rightarrow R$ называется псевдослучайной, если для любого полиномиального противника $A$ выполнено: $$|Pr[A^{F_k(\cdot)}=1]-Pr[A^{R(\cdot)}=1]|<\nu(log|D|)$$ \newtheorem{theorems}{Теорема} \begin{theorems} Если псевдослучайные генераторы существуют, то псевдослучайные функции тоже. \end{theorems} {\bf Доказательство:} \par \medskip Доказательство использует конструкцию двоичного дерева. Из предыдущей лекции, мы можем предположить без потери общности что \\ $G: \{0, 1\}^n \rightarrow \{0, 1\}^{2n}$. Пусть $G(x)=G_1(x)\parallel G_2(x)$, где $G_1(x), G_2(x) \in \{0, 1\}^n$, и ключ $s \in \{0, 1\}^n$. Мы определим нашу псевдослучайную функцию $F_s$ , которая работает как показано на Рисунке 1. \begin{center} \scalebox{0.35}{ \includegraphics{prf.eps}} \end{center} Рисунок 1: Конструкция перехода к $PRF$ от $PRG$ : на каждом уровне алгоритм выбирает верхнюю или нижнюю половину результата работы $G$, входными данными для которого являлась строка $x$. Конечный результат - это лист дерева. \par \medskip Как показано на Рисунке 1, на каждом шаге алгоритм решает, что выводить, основываясь на текущем бите строки $x$. Дана $n$-битная строка $x$. Определим $G_{x_i}(y)$, чтобы вывести верхнюю половину битов $G(y)$ (то есть, $G_1(y)$) если $x_i$ ($i$-тый бит $x$) равен 0, и нижнюю половину битов ($G_2(y)$), если $x_i$ равен 1. Повторение этого метода для $n$ (длина $x$) уровней моделирует псевдослучайную функцию как: $$F_s(x)=G_{x_1}(G_{x_2}(\dots G_{x_n}(s)\dots))$$ Заметим, что семейство функций $\{F_s\}$, определённое выше, действительно $PRF$. Предположим противное: $A$ - противник, работающий за время $\le s$, следовательно $Pr[A^fs(x)=1]-Pr[A^R(x)=1]>\epsilon$. Покажем, что по данному $A$, можно построить другого противника $А'$, который может различить $PRG G$ и случайную функцию с высокой вероятностью. Для доказательства будем использовать гибридный метод (см. Рисунок 2). Слева на Рисунке 2 находится представление двоичного дерева $F_s$, которое мы назовем $H_0$, где $S$ (0-ый уровень) случайно. Заметим, что первый уровень Ho заключает в себе выполнение $G(s)$ для получения двух псевдослучайных $n$-битных значений, чтобы затем использовать их как входные данные к следующему уровню. Если мы удалим этот уровень и зададим вместо него два случайных значения $r_0$, $r_1$, то получим новый гибрид, который назовем $H_1$ (все значения на 1-ом уровне случайны). Повторяя этот процесс, получим $H_2$ (4 случайных строки на уровне 2), $H_3$ (8 случайных входных строк на уровне 3), и так далее пока мы не достигаем $H_n$, на котором всё двоичное дерево исчезает, и $H_n$ становится случайной функцией $R$. Из того, что мы предполагали, что $А$ с хорошей вероятностью различает $F_s$(то есть, $H_0$) и $R$($H_n$), следует, что $А$ должен уметь отличать $H_i$ и $H_(i+1)$ для некоторого $i$. \begin{center} \scalebox{0.35}{ \includegraphics{hybrid}} Рисунок 2: Примеры гибридов \end{center} \par \medskip Запишем это формально: существует $1\epsilon/n$. \par \medskip Также определим $l_x$, где $1\le \module{x} \le n$, чтобы обозначить промежуточный вывод двоичного дерева на входную строку $x$. Таким образом для $F_s$, $l_{0x}=G_0(l_x)$ и $l_{1x}=G_1(l_x)$, где $l_0=G_0(s)$, $l_1=G_1(s)$. Теперь мы готовы, чтобы построить $А'$, моделируя $A$. По входным данным $F А'$ случайным образом генерирует список вывода $y_1, z_1,\dots, y_s, z_s$ , где $y_i, z_i\in \{0, 1\}^n$ и $s$ - верхняя граница времени выполнения $A$ и число запросов, которые может сделать $A$. Затем $A'$ строит новый гибрид $H$ следующим образом: \begin{enumerate} \item Пусть $H=H_0$ \item Смоделируем $А$ на $H$, где $А$ - это запросы $H(x)$, \begin{enumerate} \item Найдём самый длинный общий префикс $p$ между $x$ и $х_i$ , где $х_i$ - некоторое значение которое $H$ запрашивало до этого \item Если самый длинный общий префикс $p