%Do not change 
\documentclass[12pt, oneside]{article}
\usepackage{amssymb,amsmath}
\usepackage[margin=1in]{geometry}
\usepackage{textpos}
\usepackage{mathtools}
\usepackage{xspace}
\newcommand\myeq{\stackrel{\mathclap{\normalfont\mbox{?}}}{=}}
\newcommand\eq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}
% You may add the packages you need here
\newcommand\rd{\textsuperscript{rd}\xspace}
\newcommand\nth{\textsuperscript{th}\xspace}
\newcommand\nd{\textsuperscript{nd}\xspace}
\newcommand\bset{\{0,1\}}
\begin{document}
%Do not modify
\begin{textblock*}{4cm}(-1.7cm,-2.3cm)
\noindent {\large CS 555-Fall 2018} 
\end{textblock*}
%Do not modify other than putting your name where stated
\begin{textblock*}{8cm}(-1.5cm,-1cm)
\noindent {Name: } 
\end{textblock*}
%Do not modify other than typing your acknowledgement where stated
\begin{textblock*}{13.5cm}(-1.5cm,0cm)
\noindent {Purdue E-mail: } 
\end{textblock*}
\begin{textblock*}{18.5cm}(-1.5cm,0.5cm)
\noindent \textit{\footnotesize  I collaborated with (...). I affirm that I wrote the solutions in my own words and that I understand the solutions I am submitting.} 
\end{textblock*}
\vspace{1cm}
\begin{center}
\textbf{\Large Homework 4} \\ 
\textbf{Due date: Thursday, November 15th\nd 3:00 PM}
\end{center}
\subsection*{Question 1 (20 points)} 
Given a prime $p > 2$ we say that $x \in \mathbb{Z}_{p}^*$ is a quadratic residue  if $x = y^2 \mod{p}$ for some $y \in \mathbb{Z}_{p}^*$. Assume that $g \in \mathbb{Z}_{p}^*$ is a generator such that $\langle g \rangle = \mathbb{Z}_{p}^*$. Let $QR_p = \{x \in \mathbb{Z}_{p}^*~:~\exists y~\mbox{s.t.}~y^2=x \mod{p} \}$.
\begin{enumerate}
\item[a.] Show that $QR_p$ is a subgroup of $\mathbb{Z}_{p}^*$.
\item[b.] Show that $g \notin QR_p$, but that $g^{2i} \in QR_p$ for every $i \geq 0$.
\item[c.] Show that $\left| QR_p \right| = \frac{p-1}{2}$ (Hint: Look at Lemma 8.37). 
\item[d.] Show that $y\in QR_p$ if and only if $y^{\frac{p-1}{2}} = 1$. In particular, this means that there is a polynomial time algorithm to test if $y \in QR_p$. 
\end{enumerate}
\subsection*{Question 2 (20 points)} 
Here we show how to solve the discrete-logarithm problem in a cyclic group of order $q=p^e$ in time $\mathcal O(\mathsf{polylog}(q)\cdot \sqrt{p})$. Given as input a generator $g$ of order $q=p^e$ and value $h$, we want to compute $x=\log_g h$. You may assume that $p>2$ is a prime number. 
\begin{itemize}
	\item[(a)] Show how to compute $[x \mod{p}]$ in time $\mathcal O(\mathsf{polylog}(q)\cdot \sqrt{p})$. {\bf Hint:} Consider the equation $\left(g^{p^{e-1}}\right)^{x_0} = h^{p^{e-1}}$ as well as the ideas from the Pohlig-Hellman algorithm.
	\item[(b)] Say $x = x_0 + x_1\cdot p + \dots + x_{e-1}\cdot p^{e-1}$ with $0\leq x_i < p$. In the previous step we determined $x_0$. Show how to compute in $\mathsf{polylog}(q)$ times a value $h_1$ such that $(g^p)^{x_1+ \dots + x_{e-1}\cdot p^{e-2}} = h_1$ 
	\item[(c)] Use recursion to obtain the claimed running time for the original problem. (Note that $e= \mathcal O(\log q)$)
\end{itemize}


\subsection*{Question 3 (20 points)}
Show that the Decisional Diffie-Hellman Problem does not hold over the cyclic group  $\mathbb{Z}_{p}^*$ (although the computational Diffie-Hellman Assumption is believed to hold). {\b Hint:} Use the properties you proved in question 1 about quadratic residues.  You may assume  $g \in \mathbb{Z}_{p}^*$ is a generator such that $\langle g \rangle = \mathbb{Z}_{p}^*$ and that $p >3$ is a prime number. 
\subsection*{Question 4 (20 points)} 
In class we proved that the Diffie-Hellman Key Exchange Protocol was secure if the DDH assumption holds. In this problem we will develop a secure key exchange protocol based on the weaker CDH assumption. Let $\mathcal{G}\left( 1^n\right)$ be a PPT algorithm which outputs a cyclic group $\langle g\rangle$ along with the generator $g$ and the size $m = \left| \langle g \rangle\right|$ of the cyclic group. Consider the following variant of the Diffie-Hellman Key Exchange Protocol: (1) Alice selects $r_A \in \mathbb{Z}_m$ at random and sends $g^{r_A}$ to Bob. (2) Bob selects $r_B \in \mathbb{Z}_m$ at random and sends $g^{r_B}$ to Alice. (3) Alice and Bob both compute $g^{r_A r_B}$ and set $K_{A,B} = H\left(g^{r_A r_B} \right)$ where $H:\{0,1\}^* \rightarrow \{0,1\}^n$ is a random oracle. Assuming that the Computational Diffie Hellman Assumption holds with respect to the group generator $\mathcal{G}$ show that the modified Diffie-Hellman Key Exchange Protocol (above) is secure in the random oracle model.  
\subsection*{Question 5 (20 points)} 
Consider the following protocol for two parties $A$ and $B$ to flip a fair coin. 

\begin{enumerate}
\item  A trusted party $T$ publishes her public key $pk$; 
\item  Then $A$ chooses a uniform bit $b_A$, encrypts it using $pk$, an announces the ciphertext $c_A$ to $B$ and $T$; 
\item  Next, $B$ acts symmetrically and announces a ciphertext  ${c_B} \ne {c_A}$; 
\item  $T$ decrypts both $c_A$ and $c_B$ to obtain $b_A$ and $b_B$ and sends bits to A and B.  Both parties XOR the results to obtain the value of the coin $b_A \oplus b_B$.
\end{enumerate}
\begin{itemize}
\item[a)] Argue that even if $A$ is dishonest (but B is honest), the final value of the coin is uniformly distributed. 
\item[b)] Assume the parties use EI Gamal encryption (where the bit $b$ is encoded as the group element ${g^b}$ before being encrypted --- note that efficient decryption is still possible ). Show how a dishonest $B$ can bias the coin to any values he likes. 
\item[c)] Suggest what type of encryption scheme would be appropriate to use here. Can you define an appropriate notion of security for a fair coin flipping and prove that the above coin flipping protocol achieves this definition when using an appropriate encryption scheme?
\end{itemize}

\subsection*{Bonus Question 1 (5 Points)}
Let $q$ have prime factorization $q = \prod_{i=1}^{k} p_i^{e_i}$. Using the result from problem 2, show a modification of the Pohlig-Hellman algorithm that solves the discrete-logarithm problem in a group of order $q$ in time $\mathcal O\big(\mathsf{polylog}(q)\cdot \sum_{i=1}^{k}e_i\sqrt{p_i} \big) = \mathcal O(\mathsf{polylog}(q)\cdot \max_i\{\sqrt{p_i}\})$
% \subsection*{Bonus Question 2 (5 Points)}
\subsection*{Bonus Question 2 (5 Points)}
In the attached Mathematica Notebook file we have generated RSA keys $$(N_i=p_iq_i, e_i, d_i)~~\mbox{for $i =1,\ldots, 11$} \ $$
for eleven different kings. Each king used the same public parameter $e_i=11$ for each $i =1,\ldots, 11$ though the secret prime factors $p_i,q_i$ are all distinct. Archimedes had an important message $$m \leq \min_i N_i$$ that he wanted to share will all eleven kings so he sent the ciphertext $$c_i = m^{e_i} \mod{N_i}$$ to each king $i$. An eavesdropping attacker intercepted all of the ciphertexts and placed them in the Mathematica Notebook file. He needs your help to recover the secret message $m$ that Archimedes sent to the eleven kings. 

\end{document}