%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}


\begin{document}
% Do not modify 


%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}

%Do not modify other than typing the homework number after #
\begin{center}
\textbf{\Large Homework 1} \\ 
\textbf{Due date: Thursday, September 13\nth 3:00 PM}
\end{center}


%Rest should contain your solution for the homework. Feel free to improvise in ways that you believe make grading easier.
\subsection*{Question 1 (20 points)} 
Consider each of the the following encryption schemes and state whether the scheme is perfectly secret or not. Justify your answer by giving a detailed proof if your answer is \emph{Yes}, a counterexample if your answer is \emph{No}.

\begin{itemize}
\item An encryption scheme whose plaintext space consists of the integers $\mathcal{M}=\{0,...,12\}$ and key generation algorithm chooses a uniform key from the key space $\mathcal{K}=\{0,....,13\}$. Suppose ${{\rm{Enc}}_{\rm{k}}}{\rm{(m) =  m + k \hspace{1mm}mod \hspace{1mm} 13}}$ and ${{\rm{Dec}}_{\rm{k}}}{\rm{(c) = c - k \hspace{1mm} mod \hspace{1mm} 13}}$. 


\item An encryption scheme whose plaintext space is ${\mathcal{M}\rm{ = \{ m }} \in {{\rm{\{ 0,1\} }}^\ell }{\rm{|the \hspace{1mm} last \hspace{1mm} bit \hspace{1mm}of \hspace{1mm} m \hspace{1mm}  is \hspace{1mm} 0\} }}$ and key generation algorithm chooses a uniform key from the key space ${\{ 0,1\} ^{\ell  - 1}}$. Suppose  $\rm{Enc_k}(m) = m \oplus (k\hspace{1mm} || \hspace{1mm} 0)$ and $\rm{Dec_k}(c) = c \oplus (k \hspace{1mm}|| \hspace{1mm} 0)$.

\item Consider a encryption scheme in which M=\{a,b\}, $K = \{ {K_1},{K_2},\ldots, {K_4} \}$, and $C=\{1,2,3,4,5,6\}$. Suppose that $\rm{Gen}$ selects the secret key $k$ according to the following probability distribution:
\[\Pr[k=K_1] = \Pr[k=K_4] = \frac{1}{6},\Pr[k=K_2] = \Pr[k=K_3] = \frac{1}{3} \ .\]
and the encryption matrix is as follows
\begin{center}
    \begin{tabular}{| l | l | l |}
    \hline
     & a & b  \\ \hline
    ${K_1}$ & 1  & 4 \\ \hline
    ${K_2}$ & 2  & 3 \\ \hline
    ${K_3}$ & 3 & 2 \\ \hline
    ${K_4}$ & 4 & 1  \\ \hline

    \end{tabular}
\end{center}



\item  Suppose that we have an encryption scheme whose plaintext space is ${\mathcal{M}\rm{ = \{ m }} \in {{\rm{\{ 0,1\} }}^{2n} }\}$ and whose key space is ${\mathcal{K}\rm{ = \{ k }} \in {{\rm{\{ 0,1\} }}^n }\}$. Suppose that ${{\rm{Enc}}_{\rm{k}}}(m)={m \oplus (k||F(k))}$ where  $F$ is a secure length-preserving pseudorandom generator.

\end{itemize}



\subsection*{Question 2 (10 points)}
Prove or refute: An encryption scheme with message space $\mathcal M$ is perfectly secret if and only if for every probability distribution over $\mathcal M$ and every $c_0, c_1 \in \mathcal C$ we have $\Pr[C=c_0] = Pr[C=c_1]$


\subsection*{Question 3 (20 points +  5 points bonus)}
Let $\epsilon > 0$ be a constant. Say an encryption scheme, $\Pi=(\mathsf{Gen, Enc, Dec})$, is $\epsilon$\textit{-perfectly secret} if for every adversary $\mathcal A$ it holds that:
\begin{equation*}
 	\Pr[\mathsf{PrivK}^{\mathsf{eav}}_{\mathcal A, \Pi} = 1] \leq \frac{1}{2} + \epsilon
 \end{equation*}

 (See definition 2.5 page 31)
 \begin{enumerate}
 	\item (20 points) Show that $\epsilon$-\textit{perfect secrecy} can be achieved with $|\mathcal K| < \mathcal |\mathcal M|$
 	\item (5  bonus points)  Prove a lower bound on the size of $\mathcal K$ in term of $\epsilon$ [Challenging]
 \end{enumerate}


\subsection*{Question 4 (20 points)}
We say that a PRG $G:\{0,1\}^n \rightarrow \{0,1\}^{2n}$ is $(t,\epsilon)$-secure if for all distinguishers $\mathcal{D}$ running in time at most $t$ we have 
\[ \mathbf{Adv}_{\mathcal{D},G} = \left|Pr_{s \leftarrow \{0,1\}^n}\left[ \mathcal{D}(G(s)) = 1 \right]-Pr_{r \leftarrow \{0,1\}^{2n}}\left[ \mathcal{D}(r) = 1 \right] \right| \leq \epsilon \ . \]
Suppose that $G$ is $\left(t,\epsilon_t = \frac{1.5t}{2^n}\right)$-secure  PRG for all $t \leq 2^n$. Show that for all $t \leq 2^n$ the encryption scheme $\Pi =(\mathtt{Gen},\mathtt{Enc},\mathtt{Dec})$ (defined below) is $\left(t'=t-O(n),\epsilon_t = \frac{1.5t}{2^n}\right)$-EAV Secure.   
\begin{itemize}
\item $\mathtt{Gen}$: on input ${1^n}$, choose uniform $k \in {\{ 0,1\} ^n}$ and output it. 
\item $\mathtt{Enc}$: on input a key $k \in {\{ 0,1\} ^n}$ and a message $m \in {\{ 0,1\} ^{2n}}$ output the ciphertext:
\begin{equation}
c: = \left\langle {G(k) \oplus \left. m \right\rangle } \right.
\end{equation}
\item $\mathtt{Dec}$: on input a $k \in {\{ 0,1\} ^n}$ and a ciphertext 
$c \in \{0,1\}^{2n}$, output the plaintext message

\begin{equation}
m: = G(k) \oplus c
\end{equation}

\end{itemize}








\subsection*{Question 5 (30 points)}
For any function	$g:{\{ 0,1\} ^n} \to {\{ 0,1\} ^n}$, define	${g^\$ }(.)$ to be a probabilistic oracle that, on input	${1^n}$, choose uniform	$r \in {\{ 0,1\}^n}$ and return $(r, g(r))$. A keyed function F is a \emph{weak pseudorandom function} if for all PPT algorithm D, there exists a negligible function \textbf{negl} such that: 

\begin{equation}
\left| {\Pr [{D^{F_k^\$ (.)}}({1^n}) = 1] - \Pr [{D^{{f^\$ }(.)}}({1^n}) = 1]} \right| \le \mathsf{negl}(n)
\end{equation}

where 	$k\in {\{ 0,1\} ^n}$ and $f \in Fun{c_n}$ and chosen uniformly. 
\begin{enumerate}
\item Let ${F'}$ be a pseudorandom function, and define 
\begin{equation}
{{\rm{F}}_{\rm{k}}}{\rm{(x) \hspace{1mm} \eq }} \hspace{2mm} \left\{ \begin{array}{l}
{{{\rm{F'}}}_{\rm{k}}}{\rm{(x)  \hspace{3mm} if \hspace{1mm} x \hspace{1mm} is  \hspace{1mm} even}}\\
{{{\rm{F'}}}_{\rm{k}}}{\rm{(x + 1) \hspace{3mm} if \hspace{1mm} x \hspace{1mm} is \hspace{1mm} odd}}
\end{array} \right.
\end{equation}
Prove that F is weakly pseudorandom.

\item Is CTR-mode encryption using a weak pseudorandom function necessary CPA-secure? Does it necessarily have indistinguishable encryptions in the presence of an eavesdropper? Prove your answers.

\item Prove that the following construction is CPA-secure if $F$ is a weak pseudorandom function. 

\textbf{Construction:}
Let $F$ be a pseudorandom function. Define a private-key encryption scheme for messages of length n as follows:
\begin{itemize}
\item Gen: on input ${1^n}$, choose uniform $k \in {\{ 0,1\} ^n}$ and output it. 
\item Enc: on input a key $k \in {\{ 0,1\} ^n}$ and a message $m \in {\{ 0,1\} ^n}$, choose uniform $r \in {\{ 0,1\} ^n}$ and output the ciphertext:
\begin{equation}
c: = \left\langle {r,{F_k}(r) \oplus \left. m \right\rangle } \right.
\end{equation}
\item Dec: on input a $k \in {\{ 0,1\} ^n}$ and a ciphertext 
$c = \left\langle {r,s} \right\rangle $, output the plaintext message

\begin{equation}
m: = {F_k}(r) \oplus s
\end{equation}

\end{itemize}


\end{enumerate}

\end{document}
