%Do not change 
\documentclass[12pt, oneside]{article}
\usepackage{amssymb,amsmath}
\usepackage{mdframed}
\usepackage[margin=1in]{geometry}
\usepackage{textpos}
\usepackage{mathtools}
\usepackage{xspace}
\usepackage{hyperref}
\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\bset{\{0,1\}}
\newenvironment{proof}{\begin{mdframed}\textit{Ans:}}{ \end{mdframed}}
\newenvironment{proofSK}{\begin{mdframed}\textit{Sketch:}}{ \end{mdframed}}

\newcommand{\eqdef}{\overset{\mathtt{def}}{=}}
\newcommand{\Ad}{\mathcal{A}}

\newcommand{\first}{\textsl{first}}
\newcommand{\second}{\textsl{second}}

\newcommand{\M}{\mathcal{M}}
\newcommand{\K}{\mathcal{K}}
\newcommand{\C}{\mathcal{C}}

\begin{document}
% Do not modify 


%Do not modify
\begin{textblock*}{4cm}(-1.7cm,-2.3cm)
\noindent {\large CS 555-Spring 2021} 
\end{textblock*}

%Do not modify other than putting your name where stated
\begin{textblock*}{8cm}(12.5cm,-1cm)
%\noindent {Name: } 
\end{textblock*}
%Do not modify other than typing your acknowledgement where stated
\begin{textblock*}{13.5cm}(-1.7cm,-1.8cm)
\noindent \textit{\footnotesize  } 
\end{textblock*}

\vspace{1cm}

%Do not modify other than typing the homework number after #
\begin{center}
\textbf{\Large Homework 1} \\ 
\textbf{Due date: Thursday, February 4\nth 11:59 PM (Gradescope)}
\end{center}


\subsection*{Question 1 (24 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{enumerate}
\item An encryption scheme whose plaintext space consists of the integers $\mathcal{M}=\{0, \ldots ,10\}$ and key generation algorithm chooses a uniform key from the key space $\mathcal{K}=\{0,\ldots ,11\}$. Suppose ${{\rm{Enc}}_{\rm{k}}}{\rm{(m) =  m + k \hspace{1mm}mod \hspace{1mm} 11}}$ and ${{\rm{Dec}}_{\rm{k}}}{\rm{(c) = c - k \hspace{1mm} mod \hspace{1mm} 11}}$. 


\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} 1)$ and $\rm{Dec_k}(c) = c \oplus (k \hspace{1mm}|| \hspace{1mm} 1)$.

\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} = \{0, 1\}^{2n}$ and whose key space is $\mathcal{K}= \{0,1\}^n$. Suppose that ${{\rm{Enc}}_{\rm{k}}}(m)={m \oplus G(k)}$ where  $G:\{0,1\}^n \rightarrow \{0,1\}^{2n}$ is a secure PRG. 

\end{enumerate}


\newpage
\subsection*{Question 2 (16 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|$ {\bf Hint:} Start with a well known perfectly secret encryption scheme and consider reducing the keyspace.
    
 	\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)}

\noindent\textbf{(a)}.  Let $ G $ and $ H $ be a pseudorandom generator with expansion factor $ \ell(n) $.  In each of the for each of the following cases, say whether $ G' $ is necessarily a pseudorandom generator. If yes, give a proof; if not, find a counter example. 


\begin{enumerate}
	\item Suppose that $\ell(n) > 2n$ and define $ G'(s_1, \cdots, s_{2n}) \eqdef G(s_1\cdots s_{n }) $ where $ \ell(n) >2n $. Note: Each $s_i \in \{0,1\}$ is just a single bit of input.
	
	\item  Suppose that $\ell(n) > 2n$  and $ G'(s_1,\ldots, s_{\lceil n/2 \rceil}) \eqdef G(0^{n-\lceil n/2 \rceil}||s) $. 
	
	\item Suppose that $\ell(n) = n+2$ and define $ G'(0s) \eqdef G(s) $ and $ G'(1s)  = H(s)$. 
\end{enumerate}

\noindent\textbf{(b)}. We say that a PRG $G:\{0,1\}^n \rightarrow \{0,1\}^{\ell(n)}$ 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\}^{\ell(n)}}\left[ \mathcal{D}(r) = 1 \right] \right| \leq \epsilon \ . \]
Suppose that $G$ and $H$ are both $\left(t,\epsilon_t = \frac{1.5t}{2^n}\right)$-secure  PRG for all $t \leq 2^t$. 


For those schemes of part \textbf{(a)} which are secure PRG, determine $ (t', \epsilon') $ for the resulting $ G' $. Your bounds should be as tight as possible e.g., a bound of the form $(t,1.5/2^n)$-secure would be better than the bound $(t-100n, 1.5t/2^n)$-secure. Similarly, the bound$(t-100n, 1.5t/2^n)$-secure  would better than a bound of the form $(t-100n,3t/2^n)$-secure which in turn would be better than a bound of the form $(\sqrt{t}, 3t/2^n)$-secure. 


\subsection*{Question 5 (20 points)}
Let $ F: \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n $ be a length-preserving pseudorandom function. For the following construction of keyed function $ F':\{0, 1\}^n\times \{0, 1\}^{n-2} \to \{0 , 1\}^{2n}$,  state whether F' is a pseudorandom function. If yes, prove it; if not, show an attack. 

\begin{enumerate}
	\item $ F'_k\eqdef F_k(00|| x) || F_k (01||x)  $.
	
	
	
	\item $ F'_k \eqdef F_k(00|| x_1 \cdots x_{n-3}  || \bar{x}_{n-2}) || F_k(00|| x)  $, where $ x = x_1 \cdots x_{n-2}\in \{0, 1\}^{n-2} $ and $ \bar{x_i}  = x_i + 1 \mod 2$. 
\end{enumerate}

\end{document}\grid
