\documentclass{article}
\usepackage[russian]{babel}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{supertabular}
\usepackage{graphics}
\usepackage[cp1251]{inputenc}
\usepackage[T2A]{fontenc}
\title{Псевдослучайные генераторы}
\author{Ю. Лифшиц\thanks{Законспектировал Т.Брыксин.}.}

\begin{document}
\maketitle

\section*{План лекции}
\begin{enumerate}
\item Понятие псевдослучайного генератора
\item Односторонние функции и генераторы
\item Криптосистема на основе генератора
\end{enumerate}
\par

\section{Понятие псевдослучайного генератора}
\subsection{Основные понятия}
\quad Чтобы понять, что такое псевдослучайный генератор, нам нужно вспомнить понятие вычислительной неразличимости двух распределений. Формально, два распределения $D_1$, $D_2$ называются вычислительно неразличимыми, 
если для любого полиномиального вероятностного алгоритма $A$ 

\begin{center}
$ |Pr_{x\leftarrow D_1}[A(x)=1]-Pr_{x\leftarrow D_2}[A(x)=1]|=\nu(|x|)$
\end{center}

Неформальная постановка задачи: пусть у нас есть множества $X$ и $Y$. Мы хотим, чтобы по случайным образом выбиранному элементу $x$ из $X$ мы смогли с помощью некой специальной функции $G(x)$ породить якобы случайный элемент из $Y$. Мы будем рассматривать только случаи, когда мощность множества $Y$ намного больше мощности множества $X$, иначе задача существенно упрощается. Например, рассмотрим случай, когда $X=\{0...1000\}$, $Y=\{0...100\}$. Тогда, выбрав случайный $x \in X$, мы сможем легко вычислить $y= x$ div 10, который, очевидно, будет принадлежать $Y$ и будет случайным в силу случайности выбора $x$. 

Итак, пусть $|Y|>>|X|$. Функция $G: X\rightarrow Y$ называется псевдослучайным генератором, если $G(\mathcal{U}_X)$ и $\mathcal{U}_Y$ вычислительно неразличимы ($\mathcal{U}_X, \mathcal{U}_Y,$ равномерные распределения).

\subsection{Область применения}
\begin{itemize}
\item {Криптография} \par Каждый генератор можно использовать как криптосистему с секретным ключом. Также, они являются идельной моделью для блочных шифров.
\item {Построение алгоритмов} \par
Имеется ряд алгоритмов, использующих случайные биты. Имея генератор псевдослучайных чисел, мы могли бы брать лишь небольшое число случайных битов, а остальные получать, применяя к ним генератор. Алгоритм будет работать так же хорошо, т.к. иначе это дало бы возможность отличить случайные числа от псевдослучайных, что противоречит нашему предположению о существовании генератора.
\item {Теория сложности} \par
Класс BPP (bounded probability polynomial) - задачи, которые можно решить вероятностным алгоритмом за полиномиальное время. $\ $ DTIME($2^{n^\epsilon})$ - множество всех задач, которые можно решить детерминированным алгоритмом за время $O$($2^{n^\epsilon}$) без ограничений в памяти. Таким образом, если использовать генератор псевдослучайных чисел, будет иметь место следующее включение: $BPP\subset DTIME(2^{n^\epsilon})$
\end{itemize}

\subsection{О приложениях в криптографии}
\quad Пусть $P$ - класс полиномиальных задач. $NP$ - класс задач, решаемых недетерминированной машиной Тьюринга за полиномиальное время. Существует открытая проблема: $P=NP$ или $P\ne{}NP$? Все задачи взлома входят в класс NP, и если бы выполнялось равенство, то это бы означало, что каждая задача взлома имела бы свой полиномиальный алгоритм решения. Практически все, что мы изучали до этого, можно было бы легко взломать (нулевое разглашение, криптосистемы с открытым ключом, передача данных вслепую, электронные выборы). Пока мы не докажем, что $P\ne{}NP$, мы не сможем утверждать безопасность. Хотя, может так случиться, что $P\ne{}NP$, но при этом задачи взлома построенных систем не являются самыми сложными в своем классе и успешно взламываются.

Другое базовое предположение - существование односторонних функций. Стойкость многих решений доказана в том смысле, что мы строим их с помощью каких-то абстрактных односторонних функций. Такой подход и используется для построения псевдослучайных генераторов. 

Перечислим изученные нами понятия и рассмотрим связи между ними (см. Рис.1).
\begin{itemize}
\item Coin flipping - подбрасывание монет \par
\item Bit commitment - привязка к биту \par
\item Symmetric-key encryption - шифрование с симметричным ключом\par
\item OWP (one-way permutation) - односторонняя перестанока\par
\item OWF (one-way function) - односторонняя функция\par
\item PRG (pseudorandom generator) - псевдослучайный генератор\par
\item PRF (pseudorandom function) - псевдослучайная функция\par
\item PRP (pseudorandom permutation) - псевдослучайная перестановка\par
\item MAC (message authentication code) - код аутентификации сообщения\par
\end{itemize}
%\vfill
%\begin{figure}
\begin{center}
\scalebox{0.5}{
\includegraphics{assumptions.eps}}
Рис.1. Связи между изученными понятиями
\end{center}
%\end{figure}
%\vfill
\quad Если выполнено условие $P=PN$, то всего перечисленного не существует. Если кто-то докажет, что односторонних функций не существует, то это будет конец криптографии. Односторонние функции - очень важное понятие. Очень многое можно построить, зная хотя бы одну из таких функций. Если в криптографии что-то сводится к односторонним функциям, то считается, что это решение будет иметь достаточно высокую стойкость. 

Немного более слабое допущение - односторонние перестановки. Мы докажем, что если существуют псевдослучайные генераторы, то существуют и односторонние функции. Обратное утверждение будет получено позднее, а в этой лекции мы построим псевдослучайные генераторы на основе односторонних перестановок.

\subsection{Физические генераторы}
\quad Альтернатива генераторам - настоящие случайные числа. Для генерации случайных чисел можно использовать различные физические явления, помехи, траекторию движения мыши, частоту нажатия клавиш пользователем. Недостатки наблюдений физических явлений - их дороговизна по сравнению с математическими генераторами, также могут потребоваться усилия со стороны пользователя. К тому же нет никакой доказуемой случайности. Возможны также проблемы с балансом между частотой появляющихся значений, их корреляцией.

Поэтому часто на практике получают последовательность случайных битов одним из указанных способов, а потом проводят над ними дополнительные преобразования, чтобы быть полностью уверенным в отсутствии связей между ними.

\section{Односторонние функции и генераторы}
\quad Напомним, что функция $F:\{0,1\}^n\rightarrow \{0,1\}^m$ называется односторонней функцией, если
\begin{itemize}
 \item[1)] функция $F$ вычислима за полиномиальное время;
 \item[2)] не существует полиномиального алгоритма, который верно
 вычисляет $F^{-1}$ с {\it хорошей вероятностью};
 \item[2')] существует предикат $h:\{0,1\}^n\rightarrow \{0,1\}$,
 т.ч. по $F(x)$ {\it трудно} вычислить $h(x)$.
\end{itemize}

Односторонняя функция называется односторонней перестановкой, если она является биекцией.

\newtheorem{theorems}{Теорема}
\begin{theorems}[PRG $\Rightarrow$ OWF]
Псевдослучайный генератор $G:\{0,1\}^n\rightarrow \{0,1\}^{n+1}$ является односторонней функцией.
\end{theorems}
{\bf Доказательство.}

Итак, пусть есть функция-генератор, которая по строчкам длины $n$ выдает строчки длины $n+1$. Нужно доказать, что никакой алгоритм $A$ по второй строчке не смог бы получить первую. 

Предплолжим противное - существует алгоритм обращения. Докажем, что тогда бы существовал алгоритм, который бы отличал случайные числа $x$ от псевдослучайных $y$. Пусть алгоритм $A$ с вероятностью $\alpha$ определяет $x$ по $G(x)$: $P[A(G(x))=x]=\alpha$. Тогда построим алгоритм $A'$ следующим образом:
\begin{itemize}
\item $A'$ считает $A(y)$;
\item Если $G(A(y))=y$, то $A'$ выдает ответ "$y$ - псевдослучайное$"$, иначе - "$y$ - случайное".
\end{itemize}
\quad Если $y$ изначально было сгенерировано функцией G(x), то после проверки алгоритм $A'$ с вероятностью $\alpha$ выдаст ответ "$y$ - псевдослучайное". Иначе, рассмотрим 2 случая:
\begin{itemize}
\item $y\notin G(x)$. В этом случае не важно, что выдаст алгоритм $A$, функция $G$ на выходе никогда не получит $y$.
\item $y\in G(x)$. Вероятность того, что алгоритм $A'$ внутри этого случая скажет "$y$ - псевдослучайное", равна 1/2.
\end{itemize}
\quad Следовательно, итоговая вероятность того, что $A'$ ответит "$y$ - псевдослучайное"{}, равна $\alpha$/2. Построили алгоритм, который со значительной вероятностью отличает псевдослучайное число от случайного, что противоречит определению псевдослучайного генератора.
$\Box$

\begin{theorems}[OWP $\Rightarrow$ PRG] Если существуют односторонние перестановки, то можно построить и
псевдослучайный генератор $G:\{0,1\}^n\rightarrow \{0,1\}^{n+1}$
\end{theorems}
{\bf Доказательство.}

Пусть существует односторонняя перестановка $f(x)$, ее трудный бит $h(x)$. \par
Идея доказательства: покажем, что функция, которая строит по $x$ цепочки вида $f(x),h(x)$, является псевдослучайным генератором. При заданном $x$ возможны два варианта цепочек - $f(x),h(x)$ и $f(x),\bar{h}(x)$. Докажем, что если полученные с помощью такого псевдослучайного генератора биты можно отличить от случайных, то тогда можно было бы по $f(x)$ вычислить $h(x)$.

Предположим противное - пусть существует алгоритм $A$, который со значимой вероятностью отличает случайные биты от сгенерированных: $P_1(A(f(x),h(x))=1)-P_2(A(y)=1)=\mu{}>1/n^k$. Тогда по $A$ построим новый алгоритм $A'$, который будет вычислять $h(x)$. В зависимости от $h(x)$ и сгенерированной строчки получим 4 случая:

\begin{center}
\begin{supertabular}{|c|c|c|}
\hline
&$A$ думает, что $h(x)=0$&$A$ думает, что $h(x)=1$ \\ \hline
$h(x)=0$&$f(x),0$&$f(x),1$ \\ \hline
$h(x)=1$&$f(x),0$&$f(x),1$ \\ \hline
\end{supertabular}
\end{center}

В каждой группе должно быть поровну строк, т.к. $h(x)$ - сбалансированная функция (трудный бит обязан быть сбалансированным, т.к. иначе можно было бы точнее предсказать его значение). Пусть вероятность попадания строчки в одну из групп выражается следующей таблицей:

\begin{center}
\begin{supertabular}{|c|c|c|}
\hline
&$A$ думает, что $h(x)=0$&$A$ думает, что $h(x)=1$ \\ \hline
$h(x)=0$&$\alpha$&$\beta$ \\ \hline
$h(x)=1$&$\gamma$&$\delta$ \\ \hline
\end{supertabular}
\end{center}

\begin{figure}
Следовательно,

\begin{equation*}{
\left. 
\begin{aligned} 
P_1(A(f(x),h(x))=1)=\frac{\alpha+\delta}{2}, \\
P_2(A(y)=1)=\frac{\alpha+\beta+\gamma+\delta}{4} 
\end{aligned} \right\}
\quad \text{$\Rightarrow\quad \mu=\frac{\alpha+\delta-\beta-\gamma}{4}$}
}
\end{equation*}
\end{figure}

Построим алгоритм $A'_1$, который будет угадывать $h(x)$ по $f(x)$ следующим образом: если $A'_1(f(x),0)=1$, то ответ "$h(x)=0$"{}, иначе - "$h(x)=1$". С какой вероятностью $A_1'$ угадает трудный бит $h(x)$? Очевидно, он попадает в первый столбец таблицы. 
\begin{itemize}
\item Если $h(x)$ на самом деле равно 0, то алгоритм даст правильный ответ с вероятностью $\alpha$.
\item Если $h(x)=1$, то с вероятностью $\delta$ алгоритм ошибется. Следовательно, вероятность правильного ответа равна $1-\delta$.
Таким образом, этот алгоритм имеет вероятность угадать трудный бит, равную $\frac{\alpha+(1-\gamma)}2$.
\end{itemize}

Аналогично построим алгоритм $A'_2$: если $A(f(x),1)=1$, то ответ - "$h(x)=1$"{}, иначе - "$h(x)=0$".
Он будет угадывать правильный ответ с вероятностью $\frac{\delta+(1-\beta)}2$.

Алгоритм, который случайным образом выбирает между $A'_1$ и $A_2'$ и верит ему, будет угадывать трудный бит с существенной вероятностью $\frac1 2$+$\frac{\alpha+\delta-\beta-\gamma}4$, что противоречит существованию односторонней перестановки. 
$\Box$

\begin{theorems}[OWP $\Rightarrow$ PRG - часть 2]
Если есть псевдослучайный генератор $G:\{0,1\}^n\rightarrow \{0,1\}^{n+1}$, то можно построить и генератор
$G':\{0,1\}^n\rightarrow \{0,1\}^{f(n)}$ для любого полинома $f$
\end{theorems}
{\bf Доказательство.}

Будем генерировать последовательности битов следующим образом: 

$f(f(x)),h(x),h(f(x))$ \par
$f^{(3)}(x),h(x),h(f(x)),h(f^{(2)}(x))$ \par
... \par
$f^{(l)}(x),h(x),\cdots,h(f^{(l-1)}(x))$ \par

$f$-односторонняя перестановка. Пусть существует алгоритм $A$, который отличает эту строку от совсем случайной $x,b_1,\cdots,b_l$ с вероятностью $\mu$. Для доказательства используем гибридный метод из лекции о нулевом разглашении. Запишем промежуточные строки: 

$f(x),b_1,b_2,\cdots,b_{l-3},b_{l-2},b_{l-1},h(x)$ \par
$f^2(x),b_1,b_2,\cdots,b_{l-3},b_{l-2},h(x),h(f(x))$ \par
$f^3(x),b_1,b_2,\cdots,b_{l-3},h(f(x)),h(f(x)),h(f^2(x))$ \par
$\cdots$

Тогда алгоритм должен отличать какие-то 2 соседние строки с вероятностью $\mu{}/l$. Запишем эти 2 соседних распределения: \par
$f^{(i)}(x),b_1,\cdots,b_{l-i-1},b_{l-i},h(x),\cdots,h(f^{i-1}(x))$ \par
$f^{(i+1)}(x),b_1,\cdots,b_{l-i-1},h(x),h(f(x)),\cdots,h(f^{i}(x))$ \par

Подставим в верхнее распределение вместо $x$ $f(x)$ и перепишем: \par
$f^{(i+1)}(x),b_1,\cdots,b_{l-i-1},b_{l-i},h(f(x)),\cdots,h(f^{i}(x))$ \par 
$f^{(i+1)}(x),b_1,\cdots,b_{l-i-1},h(x),h(f(x)),\cdots,h(f^{i}(x))$ \par

Они отличаются одним битом. Докажем, что можно построить алгоритм $A'$, который по $x$ и $f(x)$ будет вычислять $h(x)$. Пусть $A'$ действует следующим образом: 
\begin{itemize}
\item вычисляет $f^{i+1}(x)$;
\item выбирает случайно бит $b^{*}$ и строит последовательность \par $f^{(i+1)}(x),b_1,\cdots,b_{l-i-1},b^{*},h(f(x)),\cdots,h(f^{i}(x))$
\item применяет алгоритм $A$. Если $A$ выдает ответ 1, то он принимает в качестве $h(x)$ бит $b^{*}$, Если 0, то 1- $b^{*}$. 
\end{itemize}

Вероятность того, что $A'$ угадает нужную пару битов, равна $1/l$, после чего алгоритм $A$ с вероятностью $\mu/l$ даст правильный ответ. Итак, построили алгоритм, который со значитительной вероятностью $\mu/l^2$ вычиляет трудный бит $h(x)$ односторонней перестановки $f(x)$. $\Box$
%\smallskip

\begin{center}
\scalebox{0.5}{
\includegraphics{PRG.eps}}\par
Рис.2. Механизм постоения псевдослучайных строк любой длины
\end{center} 

Для построения псевдослучайного генератора $G^{*}:\{0,1\}^n\rightarrow \{0,1\}^{f(n)}$ будем использовать генератор $G$ из теоремы 1, увеличивающий длину строки на 1, следующим образом: 
\begin{enumerate}
\item пусть $x$ - случайная строка длины $n$. Применим $G(x)$, получаем строку длины $n+1$, отщепляем последний бит $y$;
\item остаток будет иметь длину $n$, обозначим его $x'$. Повторяем шаг 1 для $x=x'$ до тех, пока не получим достаточное количество псевдослучайных битов.
\end{enumerate}


\section{Криптосистема на основе генератора}

\quad Как можно использовать псевдослучайный генератор для построения симметричных криптосистем? Один из способов - послать $m\oplus{}G(k)$ ($k$ - секретный ключ), но тогда, перехватив 2 сообщения, злоумышленник сможет вычислить разность двух сообщений. Более безопасный способ - посылать пару $(r, G(k\oplus{}r))$, меняя $r$ при каждой пересылке. 

Пусть $f$ --- односторонняя перестановка c секретом, $f$ имеет параметр $k$ и вычисляется за полиномиальное время. Зная $k$, $f^{-1}$ также считается за полиномиальное время. Не зная $k$, посчитать $f^{-1}$ - вычислительно сложная задача (пример - $\ x^e\ mod\ n$ в RSA). 

Пусть $f$ --- односторонняя перестановка c секретом. Для
кодирования строки $b_1b_2\dots b_k$ возьмем случайное $x$ и определим \par
\begin{center}
 $E_f(b_1b_2\dots b_k)=f^{(k)(x)}\cdot(h(x)\oplus b_1)\cdot\dots\cdot(h(f^{(k-1)}(x))\oplus b_k)$
\end{center}

Алгоритм шифрования $E$ называется семантически стойким, если для любой пары $x,y$ распределения $E(x)$ и $E(y)$ являются
вычислительно неразличимыми.

\textbf{Следствие из Теоремы 3:} Криптосистема на основе псевдослучайного генератора является семантически стойкой.


\end{document}