\documentstyle[12pt,epsf,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

\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{16}{16 de Octubre}{Julio Aracena L.}

% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI
\section{Tipos de Algoritmos}
La idea intuitiva de algoritmo est\'a relacionada con el c\'alculo de ciertas funciones $f(x)$, donde $x$ es la entrada. Dicho c\'alculo se hace mediante una m\'aquina de Turing que recibe como entrada $x$. Por consiguiente, es necesario definir un algoritmo en base a un cierto tipo de m\'aquina de Turing. Consideremos una m\'aquina de Turing $M$, del siguiente tipo:
\epsfxsize=18cm
\\
\\
\epsfbox{c16-f1.ps}
\\
\\
Si $M$ se detiene en la entrada $x$, entonces el contenido de la cinta de salida lo denotamos $M(x)$ (indefinido si $M$ no se detiene en $x$).
 
 Ahora estamos en condiciones de definir un algoritmo y diferentes
tipos de algoritmos.
\begin{definition} Un algoritmo es una funci\'on $A: \{0,1 \}^* \rightarrow \{0,1\}^* $, tal que existe una m\'aquina de Turing $M$, tal que $M(x)=A(x),$ cualquiera sea $ x\in \{0,1 \}^*$.
\end{definition}
\begin{definition}
Diremos que un algoritmo $A$ es polinomial si existe 
 una m\'aquina de Turing $M$, y un polinomio $p(\cdot)$ tal que 
\begin{itemize}
\item [i)]$M(x)=A(x), \forall x\in \{0,1\}^*$, y
\item [ii)] El n\'umero de pasos que ejecuta $M$ antes de detenerse es menor o igul a  $p(n)$, en entradas de largo $n$
\end{itemize}
\end{definition}
Algunos tipos de algoritmos son:
\begin{itemize}
\item
{\bf Monte Carlo}: un algoritmo $A$ es Monte Carlo si existe una m\'aquina de Turing probabilista $M$, y un polinomio $p(\cdot)$ tal que :
\begin{itemize}
\item [i)] $P[ M(x)=A(x) ] \geq \frac{2}{3} \,\, ,\forall x \in \{0,1\}^*$
\item [ii)] El n\'umero de pasos que ejecuta $M$ antes de detenerse es menor o igual a $p(n)$, en entradas de largo $n$.
\end{itemize}
\item
{\bf Las Vegas}: un algoritmo $A$ es Las Vegas si existe una m\'aquina de Turing probabilista $M$, y un polinomio $p(\cdot)$ tal que:
\begin{itemize}
\item [i)] $M(x)=A(x), \forall x \in \{0,1\}^*$.
\item [ii)] El tiempo esperado que $M$ toma en detenerse en entradas de largo $n$ es a lo m\'as $p(n)$.
\end{itemize}
\item {\bf Polinomiales No-Uniformes}: Si existe una secuencia infinita de m\'aquinas de Turing: $ M_1,M_2, \ldots $ , y dos polinomios $p(\cdot)$ y $q(\cdot)$, tal que:
\begin{itemize}
\item [i)] $M_n(x)=A(x), \forall x \in \{0,1\}^n.$ 
\item [ii)] $ M_n$ se detiene en a lo m\'as $p(n)$ pasos en entradas de tama\~no $n$.
\item [iii)] La descripci\'on de $M_n$ (en alguna codificaci\'on standard de las m\'aquinas de Turing) est\'a acotada por $q(n)$.
\end{itemize}
\end{itemize}
 
De esta forma, la clase RP est\'a formada por aquellos lenguajes que son decidibles por un algoritmo tipo Monte Carlo, y la clase ZPP est\'a formada por los lenguajes de \\
RP $\cap$ coRP con algoritmo tipo Las Vegas que los deciden.
\footnote{{\em Computational Complexity}, C.H. Papadimitriou, Addison Wesley,1994.}\\
 Un criptosistema pude ser seguro para un cierto tipo de adversario y para otro no, dependiendo de la capacidad de cada adversario. Es necesario definir, por lo tanto, los tipos de adversarios que existen.
\section{Tipos de Adversarios}
Un adversario es un algoritmo eficiente (i.e., probabilista o polinomial), o un algoritmo polinomial no-uniforme. En el primer caso  hablamos simplemente de adversario, y en el segundo de adversario no-uniforme. En este \'ultimo caso un adversario puede usar diferentes algoritmos para diferentes tama\~nos de las entradas.\\
Es posible demostrar que un adversario no-uniforme, es m\'as fuerte que un simple adversario. Luego, probar que un criptosistema es seguro en presencia de un adversario no-uniforme es mejor que probarlo frente s\'olo a un adversario.
\section {Funciones de un sentido}
La m\'as d\'ebil hip\'otesis que se puede hacer en criptograf\'{\i}a frente a un adversario, es que $P \neq NP$. Sin embargo, esto no es suficiente, ya que suponiendo que existe $\ L \in NP, L \not \in P$, entonces tal vez, $ L \in BPP $, pues es un problema abierto que $BPP \subseteq NP$, pero nuestro adversario tiene acceso a algoritmos probabil\'{\i}sticos.\\
 Tampoco es suficiente suponer que : $BPP \neq NP $, pues esto s\'olo significa que si existe $ L \in NP, L \not \in BPP$, entonces todos los adversario deciden incorrectamente, con una probabilidad mayor que un tercio, sobre un n\'umero infinito de entradas $x$, si $x \in L$. Estas decisiones err\'oneas, aunque en un n\'umero infinito, pueden ocurrir muy infrecuentemente, por ejemplo, una por cada tama\~no de la entrada $x$, permitiendo de esta forma quebrar nuestro criptosistema en forma frecuente. Esto \'ultimo es contrario a la idea de un criptosistema seguro.\\
 De esta forma, necesitamos una hip\'otesis m\'as fuerte que nos garantice que todo adversario, para toda entrada de tama\~no suficientemente grande $n$, tome una decision equivocada con alta probabilidad de decidir si $x \in L$, para alg\'un $L \in NP$, es decir, que se equivoque frecuentemente sobre todas las entradas de tama\~no $n$. Y por otro lado, dado $n$ suficientemente grande, poder generar una entrada $x$ de tama\~no $n$ tal que todo adversario se equivoque en la decisi\'on sobre $x$. \\
La hip\'otesis que garantiza lo anterior es la existencia de funciones de un sentido y de puerta secreta. A continuaci\'on definimos la funciones de un sentido.\\
\begin{definition}
Una funci\'on  $f:\{0,1\}^* \rightarrow \{0,1\}^*$ se dice de un sentido fuerte si :
\begin{itemize}
\item [i)] Existe $M,$ m\'aquina de Turing determinista polinomial tal que $M(x)=f(x),$ \\
cualquiera sea $x \in \{0,1\}0^*$.
\item [ii)] Para todo polinomio p y para todo adversario A, $\exists n_0 \in  I\!\!N , \forall n \geq n_0$ \\
\[ Pr[A(f(x)) \in f^{-1}(f(x))] \leq \frac{1}{p(n)} ,\] 
donde la probabilidad es sobre los x en $\{0,1\}^n$ y la fuente de aleatoridad de $A$.
\end{itemize}
\end{definition}
Es decir, las funciones de un sentido fuerte son aquellas que son invertibles en una proporci\'on peque\~na (a lo m\'as $\frac{1}{q(n)}$) de ellas, en entradas de tama\~no $n$.\\  
Dado que $f(x)$ es calculable en un tiempo polinomial, $\exists c, \,\forall x\,; |f(x)| < |x|^c$. Por lo tanto, nuestro inter\'es est\'a basado en funciones tales que $\exists k, \, |f(x)| \geq |x|^k$ . De lo contrario, debiera ser f\'acil de invertir $f$.\\
Consideremos, por ejemplo, la funci\'on: $f:Z\!\!\!Z \times Z\!\!\!Z \rightarrow Z\!\!\!Z$ con $f(x,y)=x \cdot y$. Esta funci\'on puede ser f\'acilmente invertible en salidas de tipo par, que representan la mitad de sus salidas. Luego, no es una funci\'on de un sentido fuerte. Sin embargo, $f$ es dif\'{\i}cil de invertir en salidas que son productos de dos n\'umeros primos de tama\~no similares, que corresponde a una fracci\'on de tama\~no polinomial sobre el conjunto de enteros de largo $n$. Esto motiva la siguiente definici\'on:
 \begin{definition}
Una funci\'on  $f:\{0,1\}^* \rightarrow \{0,1\}^*$ se dice de un sentido d\'ebil si:
\begin{itemize}
\item [i)] Existe $M,$ m\'aquina de Turing determinista polinomial tal que $M(x)=f(x)$,\\
cualquiera sea $x \in \{0,1\}0^*$.
\item [ii)] Existe un polinomio $q(\cdot)$ y para todo adversario $A$, $\exists n_0 \in  I\!\!N , \forall n \geq n_0$ \\
\[ Pr[A(f(x)) \not \in f^{-1}(f(x))] \geq \frac{1}{q(n)} ,\] 
donde la probabilidad es sobre los x $\in \{0,1\}^n$ y la fuente de aleatoridad de $A$.
\end{itemize}
\end{definition}
Es decir, las funciones de un sentido d\'ebil, son aquellas que no son invertibles en una proporci\'on de $\frac{1}{q(n)}$ sobre el conjunto de entradas de tama\~no $n$.\\  
Si consideramos, de nuevo la funcion $f(x,y)=x\cdot y$, si $|x|=n$, entonces 
$P$[$x$ es primo] $\approx \frac{1}{n}$, luego $P$[$x,y$ son primos] $\approx \frac{1}{n^2}$, si $|x|=|y|=n$. As\'{\i}, para todo $n$, sobre $1- \frac{1}{n^2} $ de los pares de entradas de $f$ de largo $2n$ son primos de igual largo. Si aceptamos que ning\'un adversario puede invertir $f$ cuando $x$ e $y$ son primos de un mismo largo, entonces $f$ es una funci\'on de un sentido d\'ebil, con $q(n) = O(n^2)$.
\end{document}






