\documentclass[a4paper]{article}

\usepackage[english]{babel}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath}
\usepackage{enumerate}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{xspace}

        \newtheorem{theorem}{Theorem}
        \newtheorem{lemma}{Lemma}
        \newtheorem{proposition}{Proposition}
        \newtheorem{corollary}{Corollary}
        \newtheorem{definition}{Definition}
        \newtheorem{assumption}{Assumption}
        \newtheorem{claim}{Claim}
        \newtheorem{problem}{Problem}
        \newtheorem{construction}{Construction}
\DeclareMathOperator*{\expe}{\mathbb{E}}

\newcommand{\class}[1]{{\ensuremath{\mathsf{#1}}}}
\newcommand{\enc}{\ensuremath{\class{Enc}}\xspace}
\newcommand{\dec}{\ensuremath{\class{Dec}}\xspace}
\newcommand{\zo}{\ensuremath{\{0,1\}}\xspace}
\newcommand{\poly}{\ensuremath{\class{poly}}\xspace}
\newcommand{\negl}{\ensuremath{\class{ngl}}\xspace}
\newcommand{\mac}{\ensuremath{\class{Mac}}\xspace}
\newcommand{\ver}{\ensuremath{\class{Vfy}}\xspace}
\newcommand{\gen}{\ensuremath{\class{Gen}}\xspace}


\usepackage{graphicx}
\usepackage[colorinlistoftodos]{todonotes}

\title{CSE 5852: Problem Set 6}
\date{Due: November 7, 2016}
%\author{You}

\begin{document}
\maketitle

This homework looks at some of the power of the discrete log and Diffie-Hellman.  Please be clear what definitions are used in your proofs.  Also since there are many definitions feel free to copy and paste from the problem set latex source.  Recall we have three different assumptions related to the group $\mathbb{Z}_p^*$:

\begin{assumption}
For any PPT $\mathcal{A}$, there exists a negligible $\epsilon$ such that for a random $n$-bit $p$ and its generator and select a random $x\in\mathbb{Z}_p^*$,
\[
\Pr[\mathcal{A}(1^n, p, g, g^x\mod p) = x]\le \epsilon(n).
\]
\end{assumption}

\begin{assumption}[Computational Diffie-Hellman Assumption]
For any PPT $\mathcal{A}$, there exists a negligible $\epsilon$ such that for a random $n$-bit $p$ and its generator and select a random $x, y\in\mathbb{Z}_p^*$,
\[
\Pr[\mathcal{A}(1^n, p, g, g^x\mod p, g^y \mod p) = g^{xy}]\le \epsilon(n).
\]
\end{assumption}

\begin{assumption}[Decisional Diffie-Hellman Assumption]
For any PPT $\mathcal{A}$, there exists a negligible $\epsilon$ such that for a random $n$-bit $p$ and its generator and select a random $x, y, z\in\mathbb{Z}_p^*$,
\[
\Pr[\mathcal{A}(1^n, p, g, g^x, g^y, g^{xy})=1] - \Pr[\mathcal{A}(1^n, p, g, g^x, g^y, g^{z})=1] \le \epsilon(n).
\]
\end{assumption}



\section{Diffie-Hellman Assumptions (30 pts)}

Show the following theorems:
\begin{theorem}\textbf{10 pts}
If there exists PPT $\mathcal{A}$ that breaks the discrete logarithm assumption with an inverse polynomial probability then there exists PPT $\mathcal{A}'$ that breaks the computational DH assumption with an inverse polynomial probability.  (That is, computational DH implies discrete log.)
\end{theorem}

\begin{theorem}\textbf{20 pts}
If there exists PPT $\mathcal{A}$ that breaks the computational DH assumption with an inverse polynomial probability then there exists PPT $\mathcal{A}'$ that breaks the decisional DH assumption with an inverse polynomial probability.  (That is, decisional DH implies computational DH.)
\end{theorem}

\textbf{Hint:} The adversary that breaks the computational DH problem only takes $p, g, g^x, g^y$ as input.  How can you use their response to check the last value received by $\mathcal{A}'$?

\section{Variants of Diffie-Hellman (35 pts)}
In class we showed that Diffie-Hellman could be used once.  In this problem we will show that it is okay to reuse a Diffie-Hellman element.  Consider the following extension to the problem:

\begin{assumption}[2-time Decisional Diffie-Hellman Assumption]
For any PPT $\mathcal{A}$, there exists a negligible $\epsilon$ such that for a random $n$-bit $p$ and its generator and select a random $x, y, z, r_1, r_2\in\mathbb{Z}_p^*$,
\[
\Pr[\mathcal{A}(1^n, p, g, g^x, g^y, g^z, g^{xy}, g^{xz})=1] - \Pr[\mathcal{A}(1^n, p, g, g^x, g^y, g^{z}, g^{r_1}, g^{r_2})=1] \le \epsilon(n).
\]
\end{assumption}

Show the following theorems:
\begin{theorem}\textbf{10 pts} 
If there exists PPT $\mathcal{A}$ that breaks the breaks the DDH assumption with an inverse polynomial probability then there exists PPT $\mathcal{A}'$ that breaks the 2-time DDH assumption with an inverse polynomial probability.  (That is, 2-time DDH implies DDH.)
\end{theorem}

\begin{theorem}\textbf{25 pts} 
If there exists PPT $\mathcal{A}$ that breaks the breaks the 2-time DDH assumption with an inverse polynomial probability then there exists PPT $\mathcal{A}'$ that breaks the DDH assumption with an inverse polynomial probability.  (That is, DDH implies 2-time DDH.)
\end{theorem}

\textbf{Hint:} 
Call the setting where $\mathcal{A}$ is presented with $(g^x, g^y, g^z, g^{xy}, g^{yz})$, $\mathtt{exp-0}$ and the setting where $\mathcal{A}$ is presented with $(g^x, g^y, g^z, g^{r_1}, g^{r_2}$, $\mathtt{exp-2}$.
Your argument should consider an intermediate experiment $\mathtt{exp-1}$ (hybrid) where the adversary is presented with the values $(g^x, g^y, g^z, g^{xy}, g^{r_2})$.  Your algorithm needs to function differently in the two cases of the hybrid argument.  

\section{El Gamal (35 pts)}
Recall our definition of indistinguishable encryptions and El Gamal.

\begin{definition}
The El-Gamal public-key encryption scheme is as follows:

\begin{itemize}
\item $\gen(p, g)$: 
\subitem Select $x$ from $\mathbb{Z}_p^*$.
\subitem Compute $g^x$.
\subitem Output $pk = g^x, sk =x$.
\item $\enc(g^x, m \in \{0, 1\})$:
\subitem Select $y \in\mathbb{Z}_p^*$ compute $g^y$
\subitem If $m =0 $ send $c = (g^y, (g^{x})^y)$ if $m=1 $ send $c = (g^y , g(g^{x})^y = g^{xy+1})$.
\item $\dec(x, c)$:
\subitem Parse $c$ as $g^y = g^z$.
\subitem Compute $(g^y)^x$ and then compute $h = (g^{xy})^{-1}$.  
\subitem If $hg^z = 1$ output $0$, if $hg^z = g$ output $1$.
\end{itemize}
\end{definition}

\begin{definition}
A public-key cryptosystem for $1$-bit messages is polynomially-secure if for all polynomial time $\mathcal{A}$ there exists a negligible function $\epsilon(n)$ such that
\[
|\Pr_{pk, sk, \enc}[\mathcal{A}(pk, \enc(pk, 0)) = 1] - \Pr_{pk, sk, \enc}[\mathcal{A}(pk, \enc(pk, 1)) = 1] | <\epsilon(n).
\]
\end{definition} 

Show that the ElGamal encryption scheme is polynomially-secure under the DDH assumption.  That is, show that if there exists a PPT $\mathcal{A}$ that distinguishes between encryptions of $0$ and encryptions of $1$ then there is an algorithm that breaks the DDH problem. 

Your proof should be by the hybrid argument.  Denote by $\mathtt{exp-0}$ the setting where $\mathcal{A}$ receive $g^x, g^y, g^{xy}$ and $\mathtt{exp-3}$ the setting where $\mathcal{A}$ receives $g^{x}, g^{y}, g\cdot g^{xy}$.  Consider two hybrids $\mathtt{exp-1}$ where $\mathcal{A}$ receives $g^x, g^y, g^{r_1}$ and $\mathtt{exp-2}$ where $\mathcal{A}$ receives $g^x, g^g, g\cdot g^{r_1}$.

\begin{itemize}
\item \textbf{15 pts} Show a $\mathcal{A}'$ that breaks DDH when $\mathcal{A}$ is able to distinguish between $\mathtt{exp-0}$ and $\mathtt{exp-1}$ with nonnegligible probability.
\item \textbf{5 pts} What is the distance between $\mathtt{exp-1}$ and $\mathtt{exp-2}$?  Why?
\item \textbf{15 pts} Show a $\mathcal{A}'$ that breaks DDH when $\mathcal{A}$ is able to distinguish between $\mathtt{exp-2}$ and $\mathtt{exp-3}$ with nonnegligible probability.
\end{itemize}

\end{document}