\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 CS395T 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{3}{1/27/2009}{Brent Waters} {Allison Bishop} {El Gamal Encryption}

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

\section{Comparing CDH and DDH}
\hspace*{0.5cm}Last time, we claimed that CDH was a weaker assumption than DDH, meaning that an algorithm $A$ which breaks CDH can be used to build an algorithm $B$ which breaks DDH. When we say ``$A$ breaks CDH," we mean that $A$ is polynomial time algorithm which solves the CDH problem with non-negligible probability. In the DDH problem, we have a finite group $G$ of order $p$, generated by $g$. We randomly choose two exponents $a, b \in \mathbb{Z}_p$ and a bit $\gamma \in \{0,1\}$. If $\gamma = 0$, we set $T = g^{ab}$. If $\gamma = 1$, we set $T$ to be a random group element. Given $g, g^a, g^b, T$, the DDH problem is to guess $\gamma$. Assuming we have $A$, we give an algorithm $B$ which guesses $\gamma$ correctly with probability $\frac{1}{2}$ plus a quantity which is non-negligible in terms of the security parameter $\lambda$.

We define $B$ as follows. Given input $(g, g^a, g^b, T)$, $B$ gives $A$ input $(g, g^a, g^b)$. $A$ outputs some value $d$, which equals $g^{ab}$ with probability $\epsilon$, which is non-negligible. $B$ then compares $T$ to $d$. If $T=d$, then $B$ outputs its guess $\gamma' = 0$. If $T$ does not equal $d$, then $B$ outputs $\gamma' = 1$.

To analyze the probability that $B$ succeeds ($B$ succeeds when $\gamma' = \gamma$), we consider conditional probabilities:
\[Pr[B \textit{ succeeds}] = Pr[\gamma = 0]Pr[B \textit{ succeeds}|\gamma = 0] + Pr[\gamma = 1]Pr[B \textit{ succeeds} | \gamma = 1].\]
We note that $Pr[\gamma = 0] = Pr[\gamma = 1] = \frac{1}{2}$. Also, when $\gamma = 0$, $B$ succeeds if and only if $A$ succeeds, which occurs with probability $\epsilon$. If $\gamma = 1$, then $T$ is set to be a random group element which algorithm $A$ never sees. So whatever $A$ outputs, the probability that it matches $T$ is $\frac{1}{p}$ (since $p$ is the size of the group). Thus, the probability that $B$ will succeed in this case is $1-\frac{1}{p}$. Hence,
\[Pr[B \textit{ succeeds}] = \frac{1}{2}\epsilon + \frac{1}{2}\left(1-\frac{1}{p}\right).\]

Since $p$ will be very large, $\frac{1}{p}$ will be exponentially small, so this is roughly $\frac{1}{2} + \frac{\epsilon}{2}$. We assumed that $\epsilon$ was non-negligible, so this shows that $B$ ``breaks" DDH.

\section{El Gamal}
\hspace*{0.5cm} El Gamal refers to a collection of 3 algorithms:

\begin{itemize}

\item $Setup(\lambda)$ which generates $(PK, SK)$, a public key, secret key pair,

\item $Encrypt(M, PK)$ which takes a message $M$ and a public key $PK$ and produces a cipher text $CT$, and

\item $Decrypt(CT, SK)$ which takes a cipher text and a secret key and produces a message $M$.

\end{itemize}

The $Setup$ algorithm choose a group $G$ of order $p$, and we assume that the message $M$ is an element of $G$. To generate $(PK, SK)$, an exponent $y\in \mathbb{Z}_p$ is randomly chosen. Then $PK$ is defined to be $(g, g^y = Y)$, and $SK$ is defined to be $y$. The $Encrypt(M, PK)$ algorithm chooses $r\in \mathbb{Z}_p$ randomly and produces cipher text $(C_1, C_2)$, where $C_1 = g^r$, and $C_2 = MY^r = Mg^{yr}$. The $Decrypt(CT, SK)$ algorithm computes $C_1^y = g^{ry} = g^{yr} = Y^r$, and thus can also compute that inverse of $Y^r$, denoted by $(C_1^y)^{-1}$. The output is $M = C_2(C_1^y)^{-1}$, which can also be written as $C_2/C_1^y$.

We might wonder why the $Encrypt$ algorithm should choose $r$ randomly. If the encryption algorithm were deterministic instead, then an attacker who guesses $M$ can simply encrypt $M$ and see if the output matches the observed encrypted message. One can imagine this would be an undesirable weakness in many situations, particularly if the encrypted message is likely to be one of a short list of possibilities. We also note that this encryption is not really practical for large messages (like big data files) because it is much slower than other encryptions such as AES. In practice, an encryption scheme like El Gamal might be used to encrypt a key $M$ for another encryption method that is used to encrypt the actual data. This is called hybrid encryption.

To analyze the security of El Gamal encryption, we must first develop a formal notion called ``Semantic Security" (this dates back to Goldwasser and Micali, 1984). We consider a game between a challenger and an attacker. The challenger starts by giving a public key $PK$ to the attacker. The attacker then freely chooses two messages $M_0$ and $M_1$ and sends them to the challenger(these choices do not need to be random, the attacker can choose them in any way it desires). The challenger sets a bit $\gamma = 0$ with probability $\frac{1}{2}$ and sets $\gamma = 1$ with probability $\frac{1}{2}$. The challenger then sends the attacker $T = Encrypt(M_{\gamma}, PK)$. The attacker tries to guess the value of $\gamma$, and outputs its guess, $\gamma^-$. (It is clear that the encryption function should be randomized here, otherwise the attacker can encrypt $M_0$ and $M_1$ on its own and check for agreement.) The attacker's advantage in the game is defined to be $Pr[\gamma = \gamma^-] - \frac{1}{2}$. We say that an encryption algorithm is semantically secure against a chosen plain text attack (CPA) if the attacker's advantage is negligible.

\begin{theorem} [Security of El Gamal]
\label{thm:one}
If DDH is hard, then El Gamal is semantically secure.
\end{theorem}

\bigskip

\begin{proof} We assume we have an algorithm $A$ which runs in polynomial time and has a non-negligible advantage $\epsilon$ as the attacker in the game described above where the encryption function is El Gamal. We will construct a DDH attacker $B$ which has access to $A$ and achieves a non-negligible advantage. $B$ is given $(g, g^a, g^b, T)$ as input. We let $t$ denote that bit that $B$ is trying to guess (i.e. $T = g^{ab}$ when $t = 0$ and is set randomly otherwise). $B$ gives $A$ $(g, Y = g^a)$ as input, which is a public key for El Gamal. (Note that $a$ now plays the role of $y$ in our previous description of El Gamal.) $A$ then chooses messages $M_0$ and $M_1$ which is sends to $B$. $B$ is playing the role of the El Gamal challenger here, so it sets a bit $\gamma$ randomly and generates cipher text $C_1 = g^b$, $C_2 = M_\gamma T$ to send to $A$. (Note that $b$ now plays the role of $r$.) $A$ sends $B$ a bit $\gamma'$, which is its guess for $\gamma$. $B$ guesses that $t=0$ iff $\gamma' = \gamma$.

If $t=0$ (so $T= g^{ab}$), then $C_2 = M_\gamma g^{ab}$ is a valid encryption for El Gamal. In this case, $A$ will guess $\gamma$ correctly with probability $\frac{1}{2} + \epsilon$. Thus, $Pr[B \textit{ succeeds}|t=0] = \frac{1}{2}+ \epsilon$. If $t=1$, we claim that $Pr[B \textit{ succeeds}|t=1] = \frac{1}{2}]$. To see why, we observe that when $T$ is randomly chosen, $M_\gamma T$ reveals no information about $\gamma$. More precisely, the El Gamal attacker $A$ receives the value $X = M_\gamma T$ where $T$ is random. We can write $X = T_0 M_0$ for exactly one value $T_0$ and also $X = T_1 M_1$ for exactly one value $T_1$: these values $T_0$ and $T_1$ are equally likely to occur as the randomly chosen $T$, so no information about $\gamma$ can be obtained from $X$. In this sense, the value of $\gamma$ is hidden to $A$, so the probability that $A$ will guess it is simply $\frac{1}{2}$. (We do not know what $A$ does when it is given invalid cipher text, but we can assume it always outputs either a 0 or 1 in a polynomial amount of time.) Hence,
\[Pr[B \textit{ succeeds}] = \frac{1}{2}\left(\frac{1}{2} + \epsilon\right) + \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{2} + \frac{\epsilon}{2}.\]
Since $\epsilon$ is non-negligible, this shows that $B$ violates the assumption that DDH is hard.
\end{proof}

\section{Identity-Based Encryption}
\hspace*{0.5cm} The concept of Identity-Based Encryption was introduced by Shamir in 1984. It deals with the following inconvenience of public key cryptography. If Bob wants to send an encrypted message to ``Alice", it is not enough for him to know her identity (e.g. name or email address). He must also lookup her public key (presumably in some large database). It might be preferable to have an encryption function which does not take a public key as input, but instead takes only some public parameters, the message, and the identity of Alice (represented somehow as a string). Of course, Alice must still have some secret allowing her alone to decrypt the message, and this secret obviously cannot be her identity which is known to Bob and others. Thus, we need some sort of trusted Authority who has a master secret key, publishes the public parameters, and gives Alice a secret key which allows her to decode messages encrypted with her identity.


%\subsection{Lists}
%
%\begin{itemize}
%\item hi
%\item there
%\end{itemize}
%
%\begin{enumerate}
%\item this
%\item is
%\item a
%\item list
%\end{enumerate}
%
%\subsection{Proofs}
%
%\begin{theorem}[Popularity of Cryptography]
%\label{thm:one}
%There exists a person who likes to study cryptography.
%\end{theorem}
%
%\bigskip
%\begin{proof}
%I do!
%\end{proof}
%
%\subsection{Figures}
%\label{sec:figs}
%
% \begin{figure}[h]
%   \centering
%   % uncomment out line below
%   % \includegraphics[width=6in]{figure.jpg}
%   \caption{Write caption here.}
%   \label{fig:sample}
% \end{figure}
%
%\subsection{References}
%
%This is how you reference Section~\ref{sec:figs}, Theorem~\ref{thm:one} or Figure~\ref{fig:sample}.   You can also make a citation~\cite{DH76}.
%
%\bibliography{mybib}
%\bibliographystyle{alpha}

\end{document}