\documentstyle[12pt]{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

\def\prob#1#2{{\textstyle {\mathop{{\rm Pr}}_{#1}}}\left[\, #2\,\right]}
\newcommand{\mypmod}[1]{\,(\mbox{\rm mod}\,#1)}


\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
\catedra{18}{23 de Octubre}{Marcos Kiwi}

% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI

\section{Ejemplo de funciones de un sentido}
%
Hemos dado definiciones formales de funciones de un sentido (fuertes y
  d\'ebiles), como tambi\'en de colecci\'ones de funciones 
  de un sentido (fuertes y d\'ebiles).
Sin embargo, no hemos mostrado que estos tipos de funciones y colecciones
  de funciones existen.
A continuaci\'on veremos que bajo ciertos supuestos, se puede garantizar
  dicha existencia.
Probar la existencia incondicional de alguno de los tipos de funciones 
  criptogr\'aficas que hemos estudiado es un problema que permanece 
  abierto.

Por otro lado, sabemos que funciones fuertes de un sentido existen si y s\'olo
  si funciones d\'ebiles de un sentido existen. 
De aqu\'{\i}, que el siguiente resultado, de f\'acil demostraci\'on, implica
  que si alguna de las funciones o colecci\'on de funciones antes mencionada
  existen, entonces las otras tambi\'en.

\begin{theorem}
Existe una funci\'on de un sentido fuerte (respectivamente d\'ebil), 
  si y s\'olo si, existe una colecci\'on de funciones de un 
  sentido fuerte (respectivamente d\'ebil).
\end{theorem}

Los siguientes supuestos nos permitir\'an garantizar la existencia de 
  colecci\'ones de funciones de un sentido:
\begin{itemize}
\item {\bf Supuesto fuerte acerca del logaritmo discreto:\ }
Para todo polinomio $q$, cualquiera sea el adversario
  $A$, existe un entero no-negativo $k_{0}$, tal que si $k$ es 
  al menos $k_{0}$ se tiene que 
\begin{eqnarray*}
\prob{}{A(p,g,y)=x \mbox{ tal que } 
  y\equiv g^{x} \mypmod{p}, x\in \modulo_{p-1}}
  & \leq & \frac{1}{q(n)}\,,
\end{eqnarray*}
donde la probabilidad es sobre los primos $p$ tal que $|p|=k$,\footnote{\
  En el resto de esta c\'atedra, si $\phi$ es una expresi\'on denotaremos 
  por $|\phi|$ la cantidad 
  de bits necesarios para representar eficientemente $\phi$, e.g.
  si $n$ es un entero no-negativo $|n|=\lceil \log(n)\rceil$.} los 
  generadores $g$ de $\modulo_{p}^{*}$ y la fuente de aleatoreidad de $A$.

\item {\bf Supuesto d\'ebil acerca del logaritmo discreto:\ }
Existe un polinomio $q$ tal que cualquiera sea el adversario
  $A$, existe un entero no-negativo $k_{0}$, tal que si $k$ es 
  al menos $k_{0}$ se tiene que 
\begin{eqnarray*}
\prob{}{A(p,g,y)=x \mbox{ tal que } y\equiv g^{x}\mypmod{p}, 
  x\in \modulo_{p-1}}
& \leq & 1- \frac{1}{q(k)}\,,
\end{eqnarray*}
donde la probabilidad es sobre los primos $p$ tal que $|p|=k$, los 
  generadores $g$ de $\modulo_{p}^{*}$ y la fuente de aleatoreidad de $A$.
\end{itemize}

La demostraci\'on de que los supuestos anteriores implican la existencia
  de colecciones de funciones de un sentido se basa en los siguientes
  resultados, que adem\'as son de inter\'es por si mismos.
\begin{lemma}\label{le:caract-gen}
Si $p$ es un primo, entonces $g$ es un generador de $\modulo_{p}^{*}$,
  si y s\'olo si, cualquiera sea $q$ primo tal que $q|(p-1)$
  se tiene que $g^{p-1/q} \not\equiv 1 \mypmod{p}$.
\end{lemma}
\begin{proof}
Supongamos que $g$ es generador de $\modulo_{p}^{*}$.
Claramente si $q|(p-1)$, entonces
  $g^{(p-1)/q}\equiv 1 \mypmod{p}$ contradice el hecho que 
  $g$ tiene orden $(p-1)$, luego se debe tener que 
  $g^{(p-1)/q} \not\equiv 1 \mypmod{p}$ cualquiera sea el divisor $q$
  de $(p-1)$.

Por otro lado, supongamos que $g^{(p-1)/q} \not\equiv 1 \mypmod{p}$
  cualquiera sea $q$ primo tal que $q|(p-1)$.
Si $g$ no fuese generador de $\modulo_{p}^{*}$ entonces se tendr\'{\i}a
  que el subgrupo c\'{\i}clico de $\modulo_{p}^{*}$ generado por $g$
  tiene un orden $k<p-1$ tal que $k|(p-1)$ (por el Teorema de Lagrange).
Sea $q$ el menor primo que divide a $s=\frac{p-1}{k}$, notar que 
  dicho primo existe pues $s>1$.
Sigue que $g^{(p-1)/q}\equiv(g^{k})^{s/q} 
  \equiv 1\mypmod{p}$, lo que constituye una contradicci\'on. 
\end{proof}

\begin{lemma}\label{le:generador}
Existe un algoritmo del tipo Las Vegas que dado $p$ primo y la 
  factorizaci\'on de $p-1$ encuentra un generador de $\modulo_{p}^{*}$.
\end{lemma}
\begin{proof}
Sea $p$ primo, y supongamos conocidos los $q_{i}$ primos y $e_{i}$ enteros
  tales que $p-1=\prod_{i=1}^{k} q_{i}^{e_{i}}$.
Recordemos que $\modulo_{p}^{*}$ posee $\varphi(p-1)$ generadores distintos.
Luego, del \lemref{le:caract-gen}
  el algoritmo descrito a continuaci\'on tiene una probabilidad
  igual a $\varphi(p-1)/(p-1)$ de encontrar un generador de $\modulo_{p}^{*}$.
\begin{center}
   \makebox[0in]{\framebox[4.3in][l]{
      \vbox{
      \begin{enumerate}
      \item Elegir $g \in \modulo_{p}^{*}$ al azar.
      \item Si para todo $i\in \{1,\ldots,k\}$, 
	$g^{(p-1)/q_{i}}\not\equiv 1 \mypmod{p}$, \\
	entonces\\
	\hspace{15mm} $g$ es un generador de $\modulo_{p}^{*}$ \\
	en caso contrario\\ 
	\hspace{15mm} parar (fracaso).
      \end{enumerate}
      }
   }}
\end{center}
Iterando el algoritmo anterior se obtiene el 
  resultado deseado despu\'es de observar que 
  $\varphi(m)$ es al menos igual al n\'umero 
  de primos menores que $m$,
  que conjuntamente con el Teorema de los N\'umeros Primos
  implica que $\varphi(p-1)=\Omega(p/\log(p-1))$,\footnote{\ 
	M\'as aun, se sabe que $\varphi(m) > m/(6\log\log m)$ (J.~Rosser y
        L.~Schoenfeld, \emph{Approximate Formulas for Some Functions of 
        Prime Numbers}, Illinois Journal of Mathematics, Volume 6,
	1962, p\'aginas 64--94).}
  es decir
  $\varphi(p-1)/(p-1)=\Omega(1/\log(p-1))$.
\end{proof}

\begin{theorem}
Bajo el supuesto fuerte (respectivamente d\'ebil) 
  acerca del logaritmo discreto existe una colecci\'on
  de funciones de un sentido fuerte (respectivamente d\'ebil).
\end{theorem}
\begin{proof}
Sea el conjunto de \'{\i}ndices $I=\set{(p,g)}{p \mbox{ primo },
  g \mbox{ generador de } \modulo_{p}^{*} }$, y el
  conjunto de funciones 
  $EXP=\set{EXP_{(p,g)}\Colon \modulo_{p-1}\to \modulo_{p}^{*}}
	{(p,g)\in I, EXP_{(p,g)}(x)=g^{x}\bmod p}$.
Veamos que $EXP$ es una colecci\'on de funciones de un sentido fuerte.
\begin{enumerate}
\item Sea $S_{1}$ la m\'aquina de Turing probabilista que en la entrada
  $1^k$ elije un primo $p$ y un generador $g$ de $\modulo_{p}^{*}$
  tal que $|(p,g)|=k$. (La m\'aquina $S_{1}$ existe
  pues mediante un algoritmo del tipo Las Vegas conocido\footnote{\ 
	(E.~Bach,
        \emph{How to Generate Factored Random Numbers}, SIAM Journal
        co Computing, Volume 17, 1988, p\'aginas 179--193).} se
  puede encontrar un primo $p$ de un tama\~no dado
  junto con la factorizaci\'on de $p-1$, y por el \lemref{le:generador}
  tambi\'en sabemos existe un algoritmo del tipo Las Vegas que dado
  $p$ primo y la factorizaci\'on de $p-1$ encuentra 
  un generador de $\modulo_{p}^{*}$.)

\item Sea $S_{2}$ la m\'aquina probabilista que en la entrada 
  $(p,g)$ elije
  al azar (uniformemente) un elemento de $\modulo_{p-1}$.

\item Sea $A^{\prime}$ la m\'aquina de Turing polinomial determinista
  que en la entrada $(p,g)$ y 
  $x\in \modulo_{p-1}$ calcula mediante el m\'etodo
  de cuadrados iterados $EXP_{(p,g)}(x)=g^{x} \bmod p$.
\end{enumerate}
Claramente, bajo el supuesto fuerte acerca del logaritmo discreto se tiene
  que  
  para todo polinomio $q$, cualquiera sea el adversario
  $A$, existe un entero no-negativo $k_{0}$, tal que 
  si $k$ es al menos $k_{0}$ se tiene que 
\begin{eqnarray*}
\prob{}{A((p,g),EXP_{(p,g)}(x))=x }
& \leq & \frac{1}{q(k)}\,,
\end{eqnarray*}
donde la probabilidad es sobre los $(p,g)\in I$ elegidos
  por $S_{1}$ en la entrada $1^k$, los $x\in \modulo_{p-1}$ elegidos
  por $S_{2}$ en la entrada $(p,g)$, 
  y la fuente de aleatoreidad de $A$.
\end{proof}


\section{Colecci\'on de funciones de un sentido de puerta secreta}
%
Para construir un criptosistema de clave p\'ublica no s\'olo se 
  requiere contar con una funci\'on de un sentido.
No queremos que la funci\'on de encripci\'on sea de un sentido
  para el leg\'{\i}timo destinatario de los mensajes encriptados.
Es necesario que el leg\'{\i}timo destinatario de los mensajes
  encriptados pueda decriptar con la ayuda de cierta informaci\'on
  secreta que s\'olo \'el posee, i.e. con la ayuda de una puerta 
  secreta.
Informalmente decimos que una funci\'on es de un sentido de puerta
  secreta si es de un sentido, pero es f\'acil de invertir si
  se posee cierta informaci\'on adicional.

A continuaci\'on formalmente definimos lo que es una familia
  de funciones de un sentido de puerta secreta.
\begin{definition}
Sea $I$ un conjunto de \'{\i}ndices. 
Para todo $i\in I$ sean $D_{i}$ y $R_{i}$ conjuntos finitos.
Una colecci\'on  de funciones de un sentido fuerte 
  (respectivamente d\'ebil) de puerta secreta es un conjunto
\begin{eqnarray*}
F & = & \set{f_{i}\Colon D_{i}\to R_{i}}{i\in I}\,,
\end{eqnarray*}
tal que
\begin{enumerate}
\item Existe un polinomio $p$ y una m\'aquina de Turing probabilista
  $M_{1}$ que en la entrada $1^{k}$ encuentra una tupla $(i,t_{i})$ donde
  $|i|=k$, $|t_{i}| \leq p(k)$.
La informaci\'on $t_{i}$ se denomina puerta secreta.

\item Existe una m\'aquina de Turing probabilista $M_{2}$ 
  que en la entrada $i\in I$ encuentra $x\in D_{i}$.

\item Existe una m\'aquina de Turing probabilista  $M$ tal que
  para todo $i\in I$, $x\in D_{i}$, $M(i,x)=f_{i}(x)$.
  
\item {\bf Caso fuerte:\ } para todo adversario $A$,
  para todo polinomio $q$, existe un entero no-negativo
  $k_{0}$ tal que para todo $k> k_{0}$
\begin{eqnarray*}
\prob{}{A(i,f_{i}(x))\in f_{i}^{-1}(f_{i}(x))}
& \leq & \frac{1}{q(k)}\,,
\end{eqnarray*}
donde la probabilidad se toma sobre todos los 
  $i$ elegidos por $M_{1}$ sobre la entrada $1^{k}$, los $x$ 
  elegidos por $M_{2}$ sobre la entrada $i$ y la fuente 
  de aleatoreidad de $A$.

{\bf Caso d\'ebil:\ } existe un polinomio $q$,
  tal que para cualquier adversario $A$, existe un entero no-negativo
  $k_{0}$ tal que para todo $k> k_{0}$
\begin{eqnarray*}
\prob{}{A(i,f_{i}(x))\in f_{i}^{-1}(f_{i}(x))} & \leq & 1-\frac{1}{q(k)}\,,
\end{eqnarray*}
donde la probabilidad se toma sobre todos los 
  $i$ elegidos por $M_{1}$ sobre la entrada $1^{k}$, los $x$ 
  elegidos por $M_{2}$ sobre la entrada $i$ y la fuente 
  de aleatoreidad de $A$.

\item Existe una m\'aquina de Turing probabilista $M^{\prime}$
  tal que para todo $i\in I$, $x\in D_{i}$, 
  $M^{\prime}(i,t_{i},f_{i}(x))=x$, i.e. $f_{i}$ es f\'acil
  de invertir cuando $t_{i}$ es conocido.
\end{enumerate}
\end{definition}

Al igual que en la secci\'on anterior veremos que bajo ciertos supuestos
  podemos exhibir ejemplos de colecciones de funciones de un sentido
  de puerta secreta.
Primero enunciemos cuales son estos supuestos.
\begin{itemize}
\item {\bf Supuesto fuerte acerca de RSA:\ }
Sea $H_{k} = \set{n=pq}{p,q \mbox{ primos, } |p|\approx |q|}$.
Para todo polinomio $q$, cualquiera sea el adversario
  $A$, existe un entero no-negativo $k_{0}$, tal que si $k$ es 
  al menos $k_{0}$ se tiene que 
\begin{eqnarray*}
\prob{}{A(n,e,RSA_{n,e}(x))=x }
  & \leq & \frac{1}{q(k)}\,,
\end{eqnarray*}
donde la probabilidad es sobre los $n\in H_{k}$,
  los $e\in\modulo_{\varphi(n)}^{*}$, los $x\in \modulo_{n}$
  y la fuente de aleatoreidad de $A$

\item {\bf Supuesto d\'ebil acerca de RSA:\ }
Sea $H_{k} = \set{n=pq}{p,q \mbox{ primos, } |p|\approx |q|}$.
Existe un polinomio $q$ tal que cualquiera sea el adversario
  $A$, existe un entero no-negativo $k_{0}$, tal que si $k$ es 
  al menos $k_{0}$ se tiene que 
\begin{eqnarray*}
\prob{}{A(n,e,RSA_{n,e}(x))=x }
  & \leq & 1-\frac{1}{q(k)}\,,
\end{eqnarray*}
donde la probabilidad es sobre los $n\in H_{k}$,
  los $e\in\modulo_{\varphi(n)}^{*}$, los $x\in \modulo_{n}$
  y la fuente de aleatoreidad de $A$.
\end{itemize}

Definamos entonces el conjunto de \'{\i}ndices 
\begin{eqnarray*}
I & = & \set{(n,e)}{n=pq, p \mbox{ y } q \mbox{ primos tales que }
  |p|\approx|q|, e \in\modulo_{\varphi(n)}^{*} }\,,
\end{eqnarray*}
y el conjunto de funciones 
\begin{eqnarray*}
RSA & = & \set{RSA_{n,e}\Colon \modulo_{n} \to \modulo_{n}}
	{(n,e)\in I, RSA_{n,e}(x) = x^{e} \bmod n}\,.
\end{eqnarray*}
Del estudio que ya hemos realizado acerca del criptosistema 
  de RSA es f\'acil ver que se 
  tiene el siguiente resultado.
\begin{theorem}
Bajo el supuesto fuerte (respectivamente d\'ebil) acerca de \mbox{\rm RSA}, 
  RSA es una colecci\'on de funciones de un sentido fuerte (respectivamente
  d\'ebil) de puerta secreta.
\end{theorem}


\end{document}




