\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<i<n$ �����, ��� \\$Pr[A^{H_i}=1]-Pr[A^{H_{i+1}}=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<i$, �� ����� $u$ ����� ������� �� ������ $i$
  ����� $x$, ������ ��������� ���������������� ���� ($y_i$, $z_i$), � ������� $l_{u0}=y_i � l_{u1}=z_i$.
  �������� $H(x)$ ����������� �� ����� ��������� $l_{u0}$ � $l_{u1}$.
  \item � ������ ������� $l_{u0}$ � $l_{u1}$ ������ ��� ���� �������������� ���������
  ��� ��������� ($y_i$, $z_i$). ����� ������� �� ���������  ��������������� H(x)
  \end{enumerate}
\end{enumerate}

�������, ��� ������ ����� ���� ������ �� �������������� �����, ������ ��� �� ������
�����������. ��������� ���� � �������� ������, ������� $A$ �� ����������, $�$ �����
������ $s$ �����, ��� ��� ����� ������������ ������ s ��������. �� �����������,
��������� ����, �������, ��� ���� $y_i$, $z_i$ - ��������� ������, �� ������������ $H$ �����
$H_{i+1}$, ��� ��� � $H$ ��� �� $i+1$ ������ ��������� ��������� �����. $�$ ���� $y_i$, $z_i$ - ���
������ ��������������� $PRG$, ��
$H$ ��������� � $H_i$, ��� ��� $i$-��� ������� �������, �� �������� �� $i+1$ ������ ������������
 $PRG$. ������� $A$ � ��������� ��������� $H_i$ � $H_{i+1}$,� ������������� $�'$ ����� ����������,
 ��� $F$ - ��������������� ��������� ��� �������, ��������� ��������, ������������.

\section{��������� ������ �������������� �����}
{\bf �����������:} ��������� ������� $F_k$ ���������� ������� ������ �������������� �����, ���� ��� ������ ���������������
���������� A �����, ���:
$$ Pr_{k\in K}[A^{F_k}=k]<\nu(|k|)$$

\newtheorem{theorems}{�������}
\begin{theorems}
��������������� ������� �������� ���������� ������ �������������� �����.
\end{theorems}
{\bf ��������������:}
\par \medskip 1) ����� $F:Keys(F)\times D \rightarrow R$, ����� ���������� �������, � ����� $B$ ����� ����������,
������� �������� ��������� �������� ��� ������� $g:D \rightarrow R$, � ������� ������. ���������� �����������( $Exp^{kr}_{F,B}$):
$$K\stackrel{R}{\leftarrow}Keys(F)$$
$$K'\leftarrow B^{F_K}$$
���� $K=K'$ ����� ���������� 1 ����� ���������� 0
\par \medskip kr-advantage ��� B ��������� ���
$$Adv^{kr}_{F,B}=P[Exp^{kr}_{F,B}=1].$$
��� ����� $t, q, �$ ��������� kr-advantage ��� $F$ ���:
$$Adv^{kr}_{F}(t,q,\mu)=max_B\{Adv^{kr}_{F,B}\}$$
��� �������� ������ �� ���� $B$, ������� ��������� ��������� $t$ � �������� �� �����
$q$ �������� ��������, ����� ���� ���� �������� ������ ���� $\mu$ ���.

\par \medskip 2)����� $F:\{0, 1\}^k\time \{0, 1\}^l\rightarrow \{0, 1\}^L$ - ��������� �������.
����� ��� ����� $t, q$, ��� $q<2^l$, �� ������� ����������� (1):
$$Adv^{kr}_F(t,q,ql)\le Adv^{prf}_F(t',q+1,(q+1)l)+\frac{1}{2^L}$$
� ����� ����, ���� $L=l$, �� (2):
$$Adv^{kr}_{F}(t,q,ql)\le Adv^{prp-cpa}_F(t',q+1,(q+1)l)+\frac{1}{2^L-q},$$
��� �� ����� $t'$ ��� $t$ ���� ����� ��� ������ ���������� $F$.
\par \medskip 3)������� ����� 2.
\par �� ���������� ������ ��������� � ����� ������ ���������, ��� �������� ��������������,
����� ���������� ������ ���������.
�� �������, ��� �� ������ ��������� ���������� $B$, ������� �������� ���������� $t, q, ql$ ��
����� ��������� ���������� $A_B$, ��������� ������� $t', q+1, (q+1)l$, ����� ���(*):
$$Adv^{kr}_{F,B}\le Adv^{prf}_{F,A_B}+\frac{1}{2^L}$$
���� ��� ������� �����, �� ����� �������� ����������� $(*)$ ��������� �������:
$$Adv^{kr}_F(t,q,\mu)=max_B\{Adv^{kr}_{F,B}\}$$
$$\quad \quad \quad \quad \quad \quad \quad \quad \quad \; \, \le max_B\{Adv^{prf}_{F,A_B}+2^{-L}\}$$
$$\quad \quad \quad \quad \quad \quad \quad \quad \; \: \: \le max_A\{Adv^{prf}_{F,A}+2^{-L}\}$$
$$\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \, =Adv^{kr}_F(t,q+1,(q+1)l)+2^{-L}$$

��������, � ������ $B$, ���� �� ���� �����������, ������� ������� - $t, q, ql$. �� ������ ������,
�� ��������� ����������� $(*)$. � ������� ������, �� ������������� �� ���� $A$, ��� ������� - $t, q+1, (q+1)l$.
����������� �� ������� ������ �������, ������ ��� ���� ����� �������� ���� ����������� ���� $A_B$.
��������� ������ - ������ �� �����������. ����� �������, �������� ��������, ��� ������� $A_B$ ���,
����� ����������� $(*)$ �����������.

�������� ������ 1, ��������� $A_B$ ����� ��������� ��������� ��� ������� $g:\{0, 1\}^l\rightarrow \{0, 1\}^L$, � �����
�������� ����������, � ����� ������� ��� ����������. ����� ������� ��� ����� ������������
���������� $B$ ��� ������������. ���������� �������� �����, �������������� ����������� � ��������.

\noindent ��������� $A^g_B$\\
\begin{verse}
  \item \noindent$i\leftarrow0$
  \item \noindent ��������� ���������� $B$, ������� �� ��� ������� �������� ��������� �������
  \item \noindent ����� $B$ ������ ������ �������� $x$, ���������
  \begin{verse}
    \item \noindent$i\leftarrow i+1 ; x_i\leftarrow x$
    \item \noindent$y_i\leftarrow g(x_i)$
    \item \noindent ���������� $y_i$ � $B$ ��� �����
  \end{verse}
  \item \noindent ���� $B$ �� �������� � ������� ���� $K'$
  \item \noindent ����� $x$ - ��� $l$-������ ������ �� �� ������ $\{x_1, \dots, x_q\}$
  \item \noindent $y\leftarrow g(x)$
  \item \noindent ���� $F(K', x)=y$ ����� ���������� 1 ����� - 0
\end{verse}

��� ���� �������� $A_B$ ��������� $B$ � ���������������
������������ ������ �� ������� �������� $B$ ����� �������� $g$. ����� $B$ �����������, �� ����������
��������� $k$-������ ������ $K'$, ������� $A_B$ ���������, ��������� $F(K'x)$ � $g(x)$.
����� $x$ - ��������, �������� �� ������, �������������� $B$, �
�����, ��� ����� �������� ����� ���� �������, �.�. � ������������ ����������� �� �������, ����� $q<2^l$.
������ �� ��������� ���������:
$$P[Exp^{prf-1}_{F,A_B}=1]\ge Adv^{kr}_{F,B}$$
$$P[Exp^{prf-0}_{F,A_B}=1]=2^{-L}.$$
������� �������� ��� ����������, �� ������� �������� ���� ������������ ��, �����
 ���������. �� �������������� �������, ��� ��� ���������� �� �������:
$$Adv^{prf}_{F,A_B}=P[Exp_{F,A_B}^{prf-1}=1]-P[Exp_{F,A_B}^{prf-0}=1]\ge Adv_{F,B}^{kr}-2^{-L}$$
������������ ��������� ���� ��� ��������� $(*)$. �������� ��������� ��������� $(**)$.
\par \medskip ��������� $(**)$ �������, ������ ��� � $Exp^{prf-1}_{F,A_B} ��������
$g$ - ��� $F_K$ ��� ���������� $K$, ������� �������� ��������� ��� B ����� ��� �
 � $Exp^{kr}_{F,B}$. ���� $B$ ������� �����������, �.�. ���� $K'$, ������� ������� $B$, ��������� $K$, ��
$A_B$ ���������� 1. (��������, ��� $A_B$ ��� �� ���������� 1 ���� ��� ���, ��� $B$ ����������� �� ��������.
��� ��������� �� ���� $K'=K$, �� $F(K', x)=F(K, x)$. ������� ����� - ��, ��� \\
$P[Exp^{prf-1}_{F,A_B}=1]$\ge $Adv^{kr}_{F,B}$
������ ����, ����� ������ ���������.) ��������� (**) ������� ������ ��� � $Exp^{prf-0}_{F,A_B}$
������� $g$
�������� ���������, � �.�. $x$ ������� �� ������������� $B$,������� �������� $g(x)$ ��������������
��� $B$. �����������, ��� $g(x)$
���������� ������, ����� $x$ ������������� $g$. � ����� ������ $K'$, � �������������
� $F(K', x)$, ��� ���������. ����� ������� $g(x)$ ����� �����������
$2^{-L}$ �� �������� �����. �������, ��� ��� ������� ����������
�� ����, ��� ������ $B$ �������� ���������� $F(K', x)$ � $g(x)$.

\par \medskip ��� �������������� ��������� $(2)$ �� ����� ���������� $B\rightarrow A_B$ � ����� ���������, ��� $(**)$:
$$Adv^{kr}_{F,B}\le Adv^{prp-cpa}_{F,A_B}+\frac{1}{2^L-q}$$
���������� ��������� ����������� ����, �� ���� ��������� $A_B$ - ����� ��. ��������������� �� ���������, ���
$$P[Exp^{prp-cpa-1}_{F,A_B}=1]=Adv^{kr}_{F,B}$$
$$P[Exp^{prp-cpa-0}_{F,A_B}=1]\le \frac{1}{2^L-q}.$$
������� ��������� �������
$$Adv^{prp-cpa}_{F,A_B}=P[Exp{prp-cpa-1}_{F,A_B}=1]-P[Exp^{prp-cpa-0}_{F,A_B}=1]$$
$$Adv^{prp-cpa}_{F,A_B}\ge Adv^{kr}_{F,B}-\frac{1}{2^L-q}$$
� ������������ ������ ���� ��������� $(**)$. ������ ��������� ������� ��
��� �� �������,��� � ������. ������ ��������� �������, ������ ��� � ������� 0
����� $g$ ������ ��������� ������������ �� $l$-������ �
$l$-������. ����� ������� $g(x)$ ��������� ���� �� 2^L-q ��������� �������� �����
$y_1,\dots,y_q$. (��� $L = l$.)


\section{������}
\begin{enumerate}
\item ��������� �� ���������������� ���������� $G:B^n\rightarrow
B^N$ ��������������� ������� $F:n\times\log N\rightarrow \{0,1\}$.
\item ��������, ��� ���� ���������� ��������������� �������,
�� ��������������� ���������� ���� ����������.
\end{enumerate}

\section{���������}
\begin{enumerate}
\item ������������ ���������� ���� - ����������-�������, ���. 48-49\\
      ������: http://www.cs.ucsd.edu/users/mihir/papers/gb.pdf
\item ���������� ��������������� �������\\
      ������: http://www.cs.berkeley.edu/~luca/cs276/notes/lecture10.ps
\item ��������� ������ �������������� ����� - ����������-�������, ���. 70-75\\
      ������: http://www.cs.ucsd.edu/users/mihir/papers/gb.pdf
\end{enumerate}

\end{document}
