\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{latexsym}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{fact}[theorem]{Fact}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{assumption}[theorem]{Assumption}

\newcommand{\qed}{\hfill \ensuremath{\Box}}

\newenvironment{proof}{
\vspace*{-\parskip}\noindent\textit{Proof.}}{$\qed$

\medskip
}

\newcommand{\alg}[1]{\mathsf{#1}}
\newcommand{\Prover}{\alg{P}}
\newcommand{\Verifier}{\alg{V}}
\newcommand{\Simulator}{\alg{S}}
\newcommand{\PPT}{\alg{PPT}}
\newcommand{\isom}{\cong}
\newcommand{\from}{\stackrel{\scriptstyle R}{\leftarrow}}
\newcommand{\handout}[5]{
   \renewcommand{\thepage}{#1-\arabic{page}}
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { {\bf CS 395T Advanced Cryptography} \hfill #2 }
       \vspace{4mm}
       \hbox to 5.78in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\ho}[5]{\handout{#1}{#2}{Instructor:#3}{Scribe: #4}{Lecture #1: #5}}
\newcommand{\al}{\alpha}
\newcommand{\Z}{\mathbb Z}

\begin{document}
\ho{2}{22-Jan-2009}{Brent Waters} {Rashid Kaleem} {Class Introduction}

%
% NOTE: If you want to scan in hand-drawings for figures, that is fine.
%

\section{Public Key Encyption}


The following scenario describes a public key encryption system in practice. 
\begin{enumerate}
\item
Bob decides to communicate  with alice@yahoo.com but fears an attacker.
\item
Bob would lookup Alice's public key from a trusted source.
\item
Bob would encrypt the email using the public key aquired in the above step.
\item
Alice would have the private key which she can use to decrypt the message.
\end{enumerate}

In an identity based encryption, the first step is not required. Today we will review some basic number theory and public key cryptosystems such as the El Gammal and prove it secure under a number theoretic assumption.

\section{Groups}
A group is a finite set of elements having the following properties
\begin{itemize}
\item
The order of the group is the number of elements in it.
\item
The group is closed under an operation  (addition, multiplication etc)
\item
The existence of an Identitiy element I such that $\forall h \in G, I*h=h*I=h$.
\item
Existence of an inverse for all elements, $\forall h \in G, \exists h^{-1}$ such that $h*h^{-1}=I$
\item
The operation under which the group is defined be commutative and associative.
\end{itemize}
For example, the following are groups:
\begin{itemize}
\item
$Z^{*}_{P}$ : for some prime $P$, is the set of elements $\{1,2,3,...P-1\}$ under the operation multiplication. The order of the group is $P-1$.
\item
$Z_{7}$: consists of $\{1,2,3,4,5,6\}$. For instance, $5*5 mod 7 = 25 mod 7 = 4$.\\
The inverse can be derived similarly, for instance $3^{-1}$ is represented by $5$ since $3*5 mod 7 = 15 mod 7 = 1$
\item
$G = \{1,2,4\}$ is a group under the operation multiplication modulo 7.
\item
$G = \{1,2,4,6\}$ is not a group under the operation multiplication modulo 7 because it does not obey the closure property.
\item
Elliptic Curve groups. More on this later, but they permit an equal strength cryptosecurity for smaller keys.
\end{itemize}
\subsection{Some usefull facts.}
Let $G$ be a group of prime order $P$, and let $g \in G$ 
\begin {enumerate}
\item
$g^{a} = g*g*g...g$
\item
$g^a*g^b=g^{a+b}$. Not $g^{ab}$.
\item
$g^{P}=1$, where P is the group order.
\item
$g^{a} = g^{a mod P}$.
\end{enumerate}

\subsection{Repeated Squaring for Exponentiation.}
In practice, $\|G\|\approx2^{160}$, and to compute $g^a$ for very very large $a$ would require extensive computing. It would take exponential time to compute $g^a$ using regular multiplication $a$ times. \\
In order to compute $g^a$ more efficiently, we use the following procedure:
\begin{enumerate}
\item
Detemine $n = log{a}_{2}$.
\item
Compute $g^{2i} = g^{i}*g^{i}$ for $i=1,2,4,...n$.
\item
Let the binary representation of $a$ be $a_n,a_{n-1},...a_2,a_1,a_0$.
\item 
Now use the following to determine $g^a$ : \\
\[ g^a = (g^{1})^{a_1} + (g^{2})^{a_2} +...+ (g^{2^n})^{a_n}   \]
\end{enumerate}

\section{Hard Problems}
Now we shall consider some hard problems, as well as show how to prove a cryptosystem secure. We will consider three hard problems :
\begin{itemize}
\item
Discrete Logarithm
\item
Computational Diffie Hellman
\item
Decisional Diffie Hellman
\end{itemize}
Now let us discuss each of these:
\subsection{Discrete Logarithm}
Given a group $G$ of order $P$ and a generator $g$, and let $a$ be randomly chosen from $Z_P$. Now consider $g\in G$. Let $h = g^a$. The discrete logarithm problem $T$ is to determince $a$ from $g$ and $g^a$.
\subsubsection{Assumption}
For all poly-time algorithms $A$, 
\[Pr[A(T(G,g,g^a))=a] = negligible \]
But we need to be specific by what we mean negligible and plynomial time algorithm with respect to what. Whenever we have a number theoretic assumption, it is always going to be parameterized with respect to a security parameter $\lambda$, so the algorithm $A$ is polynomial time with respect to $\lambda$. We also define a function $F$ to be negligile in $\lambda$ if for all plynomials $g(x)$, $\exists n$ such that $\forall x'>n$ \[f(x') < \frac{1}{g(x')}\]
Hence, as $\lambda$ becomes larger, the probability of solving the problem becomes smaller.
\subsection{Computational Diffie Hellman}
Given a group $G$ of order $P$ and a generator $g$, and let $a,b$ be randomly chosen from $Z_P$. Now consider $g\in G$. The computational Diffie Hellman problem $T$ is to determince $g^{ab}$ from $g, g^a,$ and $g^b$.
\\No polynomial time algorithm can compute $g^{ab}$ without negligible probability.

\subsubsection{Proof of Hardness}
We can show that a problem $A$ is harder than a problem $B$ if we can show that solving $B$ can be used to solve $A$ as well. In order to show that the Computational Diffie Hellman problem is harder than the Discrete Logarithm problem by showing that a solution to the latter can be used to solve the former.

Suppose that an algorithm (or procedure) A which can solve the Discrete Logarithm problem i.e, $A(g,g^a)=a$ with greater than negligible probability. We can construct an algorithm B that solves the computational Diffie Hellman problem : 
\begin{theorem}{Computational Diffie Hellman is harder than Discrete Logarithm}
\end{theorem}
\begin{proof}
We can construct an algorithm $B(g,g^a,g^b)$ that can compute $g^{ab}$ as follows:
\begin{itemize}
\item
Invoke $A(g,g^a)=a$, hence determine a.
\item
Simply compute $(g^b)^a$ to determine $g^{ab}$.
\end{itemize}
But the above assumption requires the following conditions:
\begin{enumerate}
\item
$A$ is a polynomial time algorithm.
\item
$A$ solves the Discrete Logarithm problem with greater than negligible probability.
\item
$B$ takes polynomial time (and hence invokes $A$ polynomial number of times).
\item
Probability of success for $B$ is equal to that of $A$.
\end{enumerate}
\end{proof}

\subsection{Decisional Diffie Hellman}
Given a group $G$ of order $P$ and a generator $g$, and let $a,b$ be randomly chosen from $Z_P$, also consider a randomly selected $\beta \in {0,1}$ such that if $\beta=0$ $ \chi= g^{ab}$ else $\chi$ is randomly selected from $G$. The decisional Diffie Hellman problem $T$ is to determince $\beta$ from $g,\chi, g^{a},$ and $g^b$ (i.e, is it a valid Diffie Hellman tuple?).

Note that $\beta$ is uniformly random, so the adversary can also randomly pick his guess for $\beta$ and get it correct half of the time. So we need to rephrase our definition of the hardness.

For all plynomial time algorithms $A$, the probability that $A(G,g,g^a,g^b,\chi)=\beta$ is less than $\frac{1}{2} +negligible(\lambda)$, i.e;

\[ Pr[A(g,g^a,g^b,\chi)=\beta] < \frac{1}{2} +negligible(\lambda) \]
\begin{theorem}{Decisional Diffie Hellman is harder than Computational Diffie Hellman}
\end{theorem}

\begin{proof}
If algorithm $A$ breaks computational Diffie Hellman, then there exists an algorithm $B$ that can break decisional Diffie Hellman algorithm as follows:
\begin{itemize}
\item
$B$ is passed the arguments $g, g^a, g^b and \chi$.
\item
$B$ invokes $A$ with the arguments $g, g^a$ and $g^b$ which returns $\chi'$.
\item
$B$ can check if $\chi'$ equals $\chi$ and outputs $0$ else outputs $1$.
\end{itemize}
\end{proof}

\end{document}