\documentstyle[12pt, spanish]{article}

\textwidth=6in
\oddsidemargin=0.25in
\evensidemargin=0.25in
\topmargin=-0.1in
\footskip=0.8in
\parindent=0.0cm
\parskip=0.3cm
\textheight=8.00in
\setcounter{tocdepth} {3}
\setcounter{secnumdepth} {2}
\newtheorem{theorem}{Teorema}
\newtheorem{exercise}{Ejercicio}
\newtheorem{corollary}{Corolario}
\newtheorem{lemma}{Lema}
\newtheorem{observation}{Observaci\'on}
\newtheorem{comentary}{Comentario}
\newtheorem{proposition}{Proposici\'on}
\newtheorem{definition}{Definici\'on}
\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\newcommand{\qedbox}{\vbox{\hrule\hbox{\vrule\squarebox{.667em}\vrule}\hrule}}
\newcommand{\qed}{\nopagebreak\mbox{}\hfill\qedbox\smallskip}
\newcommand{\startproof}{\noindent{\em Dem:}\hspace{1em}}
\newenvironment{dem}{\startproof}{\qed}
\newenvironment{proof}{{\bf Dem:}\hspace{1em}}{\qed\newline}


\newcommand{\catedra}[4]{
   \pagestyle{headings}
   \thispagestyle{plain}
   \newpage
   \noindent
   \begin{center}
   \makebox[0in]{\framebox{
      \vbox{
    \hbox to 6in { {\bf MA-53G Intr. a la Criptograf\'{\i}a
                        \hfill Semestre Primavera, 1996}  }
       \vspace{4mm}
       \hbox to 6in { {\Large \hfill C\'atedra No. #1 : #2 \hfill} }
       \vspace{2mm}
       \hbox to 6in { {\it Transcriptor: #3 \hfill} }
      }
   }}
   \end{center}
   \markboth{C\'atedra No. #1 : #2}{C\'atedra No. #1 : #2}
   \vspace*{4mm}
}

% LISTA DE MACROS PERSONALES COMIENZA AQUI

\renewcommand{\emph}[1]{{\em #1}}
\newcommand{\plain}{{\cal P}}
\newcommand{\cipher}{{\cal C}}
\newcommand{\key}{{\cal K}}
\newcommand{\encrip}{{\cal E}}
\newcommand{\decrip}{{\cal D}}

\newcommand{\modulo}{{\cal Z}}
\newcommand{\kernel}{\mbox{\rm Ker}}
\newcommand{\determ}[1]{\mbox{\rm det}(#1)}
\newcommand{\mcd}[2]{\mbox{\rm mcd}(#1,#2)}
\newcommand{\mcm}[2]{\mbox{\rm mcm}(#1,#2)}
\newcommand{\set}[2]{\{#1\,|\,#2\}}
\newcommand{\smidge}{{\kern .05em}}	
\newcommand{\Colon}{{\smidge\colon\;\:}}
\newcommand{\eqdef}{\stackrel{\rm def}{=}}

\newcommand{\chapref}[1]{\mbox{Capitulo~\ref{#1}}}
\newcommand{\secref}[1]{\mbox{Secci\'on~\ref{#1}}}
\newcommand{\ssecref}[1]{\mbox{Secci\'on~\ref{#1}}}
\newcommand{\apref}[1]{\mbox{Ap\'endice~\ref{#1}}}
\newcommand{\thref}[1]{\mbox{Teorema~\ref{#1}}}
\newcommand{\defref}[1]{\mbox{Definici\'on~\ref{#1}}}
\newcommand{\corref}[1]{\mbox{Corolario~\ref{#1}}}
\newcommand{\lemref}[1]{\mbox{Lema~\ref{#1}}}
\newcommand{\propref}[1]{\mbox{Proposici\'on~\ref{#1}}}
\newcommand{\figref}[1]{\mbox{Figura~\ref{#1}}}
\newcommand{\tablref}[1]{\mbox{Tabla~\ref{#1}}}
\newcommand{\eqref}[1]{\mbox{(\ref{#1})}}
\newcommand{\ineqref}[1]{\mbox{(\ref{#1})}}
\newcommand{\comref}[1]{\mbox{Comentario~\ref{#1}}}

% FIN LISTA DE MACROS PERSONALES

\begin{document}

% LOS DATOS IDENTIFICATORIOS DE LA CATEDRA TRANSCRITA VAN AQUI
% (modificar los parametros en invocacion de la siguiente macro:
%	primer parametro: No. de catedra transcrita
%	segundo parametro: fecha de catedra transcrita
%	tercer parametro: Nombre del transcriptor
\catedra{17}{22 de Octubre}{Julio Aracena L.}

% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI
 Ya se han definido las funciones de un sentido d\'ebil y las funciones de un sentido fuerte. Claramente, es m\'as conveniente tener una funci\'on de un sentido d\'ebil que una funci\'on de un sentido fuerte. Pero, si tenemos una funci\'on de sentido d\'ebil podemos construir una funci\'on de sentido fuerte, como lo muestra el siguiente teorema.
\begin{theorem} 
Existen funciones de un sentido d\'ebil  si y s\'olo si existen funciones de un  sentido fuerte
\end{theorem}
\begin{proof}
La implicancia  hacia la izquierda es evidente a partir de las definiciones.\\
La demostraci\'on de la implicancia en el otro sentido la haremos por contradicci\'on.\\
 Sea  $f:\{0,1\}^* \rightarrow \{0,1\}^*, $ funci\'on de un sentido d\'ebil, luego existe un polinomio $q(\cdot)$, tal que para todo adversario $A$ existe un  $n_0 \in I\!\!N$  tal que  $\forall n \geq n_0$
\begin{center}
$ Pr_{x \in \{0,1\}^*}[ A $  tiene \'exito en $f] \leq 1 - \frac{1}{q(n)}$ \\
\end{center}
 (entenderemos por $A$ tiene \'exito en $f$ el evento $\{x\,:\, A(f(x))\in f^{-1}(f(x)) \})$ \\
\\
De ahora en adelante, las probabilidades durante la demostraci\'on son calculadas uniformemente sobre todos los valores posibles del string $x \in \{0,1\}^n$ y sobre las fuentes de aleatoriedad de los algoritmos probabil\'{\i}sticos.\\
\\
Fijemos el polinomio $q(\cdot)$, que sin p\'erdida de generalidad podemos considerar creciente, y definamos la funci\'on: $g: \{0,1\}^* \rightarrow \{0,1\}^*$, tal que si $x \in \{0,1 \}^m$, y \\
$x = x_1x_2\cdots x_Nu$, con  $N=2nq(n)$, donde $n$ es tal que:
\[  2n^2q(n) \leq m < 2(n+1)^2q(n+1)\], entonces $g(x)=g(x_1x_2 \ldots x_Nu)= \, f(x_1) \circ f(x_2) \circ \cdots \circ f(x_N), 
\,\, \,\,\,\, x_i \in \{0,1\}^n$
. Luego, la imagen de $x$ por $g$ corresponde a una cadena de largo $Nn$.\\
\\
\newpage
{\bf Afirmaci\'on:} $g $ es una funci\'on de un sentido fuerte.\\
\\
\begin{proof} (Afirmaci\'on)
Supongamos que $g$ no es de un sentido fuerte, i.e. que exis\-te un adversario $A'$ y un polinomio $q'(\cdot)$, tal que para una infinidad de $m$'s :\\
$Pr[A'$ tenga \'exito en $g]\geq \frac{1}{q'(m)}$. ($A'$ tiene \'exito en $g$ significa que si la salida de $A'$ es $z_1z_2\cdots z_N$, entonces $f(z_i)=f(x_i), \forall i\leq N$).
 Fijemos $m$ y consideremos el siguiente algoritmo $A$ que, como veremos, invierte $f$ con una probabilidad que contradice el hecho de que $f$ es funci\'on de un sentido d\'ebil. Este algoritmo recibe como entrada $y=f(x)$, y usa un valor arbitrario fijo $u$ de largo $m-Nn$.\\
\\
\\
\makebox[6.5in]{\framebox[6.5in][l]{
 \vbox{
\begin{enumerate}
\item  Para $i=1,\ldots,N$ hacer
\item \hspace*{1em} Repetir $2nNq'(m)$ veces
\item  \hspace*{2em}  Elejir $x_1,x_2, \ldots , x_{i-1},x_{i+1},\ldots,x_N \in \{0,1\}^n$ al azar.
\item  \hspace*{3em} Calcular $g(x_1\cdots x_{i-1}xx_{i+1}\cdots x_Nu)=f(x_1) \cdots f(x_{i-1})f(x)f(x_{i+1})\cdots f(x_N)$\\
\hspace*{4em} sea $z= A'(g(x_1x_2\cdots x_{i-1}xx_{i+1}\cdots x_Nu))$.
\item \hspace*{4em}Si $A'$ tiene \'exito, entonces $z=z_1z_2 \cdots z_i \cdots z_N$, donde $f(z_j)=f(x_j), \,\,\\
\hspace*{4em} \forall j \not = i$ y $ f(z_i)=f(x)=y,$ entonces entregamos como salida $z_i$,
\\ \hspace*{4em}en caso contrario, continuamos con la pr\'oxima iteraci\'on.
\end{enumerate}
}
}}
\\
\\
Queremos demostrar que $Pr[A$ tenga \'exito en $f]$ sea mayor o igual a $1-\frac{1}{q(n)}$. \\
Para ello demostraremos que existe un indice $i \in \{1, \ldots N\}$ y un $x \in \{ 0,1\}^n $, tal que 
\begin{center}
$Pr[A'(x_1x_2\ldots x_{i-1}xx_{i+1} \ldots x_{N})$ tenga \'exito $] \geq \frac{1}{2Nq'(m)}$
\end{center}
 Con este objeto, definamos a continuaci\'on, para cada $ i=1,\ldots ,N, \,$ y para todo $x\in \{0,1\}^n :\\
\varphi _{i,n}(x)= P[A'$ tiene \'exito en $g(x_1x_2\ldots x_{i-1}xx_{i+1}\ldots x_N)]$, y\\ $E_n=\{x\in \{0,1\}^n: \forall i=1,\ldots,N, \varphi _{i,n}(x) < \frac{1}{2Nq'(m)} \}$. \\
$(i.e., E_n $ representa el conjunto de los puntos en los cuales $A$ tendr\'a una baja probabilidad de tener \'exito). Supongamos por el momento que $|E_n|< \frac{2^n}{2q(n)} $. Luego
\begin{center}
$ Pr[A(f(x)) \not \in f^{-1}(f(x))] = Pr[A(f(x)) \not \in f^{-1}(f(x))|x\in E_n]Pr[x\in E_n] $\\
\hspace*{7em} $+ Pr[A(f(x)) \not \in f^{-1}(f(x))| x\not\in E_n]Pr[x \not \in E_n] $\\
\end{center}
Pero, $Pr[x \in E_n]= \frac{|E_n|}{|x \in \{0,1\}^n|}= \frac{1}{2q(n)}$, y 
sea $a$ tal que $a \not \in E_n$, luego existe un $i_0 \in \{1,\ldots ,N\}$, tal que $\varphi _{i_0,n}(a) \geq \frac{1}{2Nq'(m)}$, por lo tanto
\begin{center}
$Pr[ A'(x_1x_2\ldots x_{i_0-1}ax_{i_0+1} \ldots x_N)$ no tenga \'exito]$ \leq (1-\frac{1}{2Nq'(m)})$, luego \\
$Pr[ A$ no tenga \'exito $|x\in E_n] \leq (1-\frac{1}{2Nq'(m)})^{2Nq'(m)n}$,
\end{center}
 pues son $2nNq'(m)$ iteraciones del algoritmo $A' $ con entrada $g(x_1x_2\ldots x_{i_0-1}ax_{i_0+1} \ldots x_Nu)$.
\\ Por consiguiente
\begin{center}
$ Pr[A(f(x)) \not \in f^{-1}(f(x))] $
$\leq 1 \cdot \frac{1}{2q(n)} + (1-\frac{1}{2Nq'(n)})^{2Nq'(n)n}\cdot 1
\leq \frac{1}{2q(n)} + e^{-n} < \frac{1}{q(n)} $ 
\end{center}
donde $(1-\frac{1}{2Nq'(n)})^{2Nq'(n)n} \leq e^{-n} $ para $n$ suficientemente grande. Por lo tanto, \\
$Pr[A$ tenga \'exito] $> 1-\frac{1}{q(n)}$. Pero, esto contradice el hecho que $f$ es una funci\'on de un sentido d\'ebil, pues el mismo resultado lo podemos tener para una infinidad de $n$'s, as\'{\i} $g$ es una funci\'on de un sentido fuerte.
\end{proof} 
\\
 Nosotros ahora s\'olo necesitamos demostrar que $|E_n| < \frac{2^n}{2q(n)}$. Supongamos que no se tiene, entonces \\
\\
$\frac{1}{q'(m)} \leq Pr[A'$ tenga \'exito en $g$] =$ Pr[A'$ tenga \'exito en $g$ y $\exists x_i;\varphi_{i,n}(x_i) < \frac{1}{2Nq'(m)}] + Pr[A'$ tenga \'exito en $g$ y  $\forall x_i;\varphi_{i,n}(x_i) \geq \frac{1}{2Nq'(m)}]$\\
$\leq \sum_{i=1}^{N} Pr[A'$ tenga \'exito en $g$ y $\varphi_{i,n}(x_i) < \frac{1}{2Nq'(m)}] + Pr[\forall x_i,\,\, \varphi_{i,n}(x_i) \geq \frac{1}{2Nq'(m)}]\\
\leq N \frac{1}{2Nq'(m)}+(Pr[x_i\not \in E_n ])^N \leq \frac{1}{2q'(m)}+ (1-\frac{1}{2q(n)})^N = \frac{1}{2q'(m)} + (1-\frac{1}{2q(n)})^{2nq(n)}\leq \frac{1}{2q'(m)} + e^{-n} <\frac{1}{q'(m)}$,  para $n$ suficientemente grande.\\
\\
Esto es una contradicci\'on, luego $|E_n| < \frac{2^n}{2q(n)}$.
\end{proof}\\
 Hay dos problemas asociados con la construcci\'on de la funci\'on $g$ en la demostraci\'on.
\begin{itemize}
\item [i)] El tama\~no de la entrada de $g$ depende del valor de $q(\cdot)$, el cual puede que ser no conocido.
\item[ii)] El tama\~no de la entrada de $g$ depende de la funci\'on $f$. En la demostraci\'on, $m=O(n^2q(n))$.
\end{itemize}
Existen, sin embargo, construcciones m\'as eficientes de una funci\'on de un sentido fuerte a partir de una funci\'on de un sentido d\'ebil.\\
\newpage
\section{Colecci\'on de funciones de un sentido}
En muchas ocasiones se tiene un conjunto de funciones, mas bien que una sola, luego es necesario tener un concepto de colecci\'on de funciones de un sentido.
 \begin{definition} Sea $I$ un conjunto de \'{\i}ndices , y $\forall i\in I$, sean $D_i,R_i$, conjuntos finitos. Una colecci\'on de funciones de un sentido es un conjunto $F=\{f_i: D_i \rightarrow R_i\}_{i \in I}$, satisfaciendo las siguientes condiciones:
\begin{itemize}
\item [1)] Existe una m\'aquina de Turing probabilista $S_1,$ que en la entrada: $1^k$ encuentra $i\in \{0,1\}^k \cap I$.
\item[2)] Existe una m\'aquina de Turing probabilista $S_2$, que con entrada $i\in I$ arroja como salida $x\in D_i$.
\item [3)] Existe una m\'aquina de Turing probabilista $A'$, tal que $\forall i\in I, \forall x \in D_i, A'(i,x)=f_i(x)$.
\item [4)] Para toda m\'aquina de Turing  probabilista $A$, para todo polinomio $q(\cdot)$, $\exists n_0 \in I\!\!N, \forall n \geq n_0 $ tal que \\
\[Pr[A(i,f_i(x)) \in f_i^{-1}(f_i(x))] \leq \frac{1}{q(n)}, \]\\
donde la probabilidad es tomada sobre los $i$ elegidos por $S_1$, los $x$ elegidos por $S_2$ y la fuente de aleatoriedad de $A$.
\end{itemize}
\end{definition}
\end{document}






