%Do not change 
\documentclass[12pt, oneside]{article}
\usepackage{amssymb,amsmath}
\usepackage[margin=1in]{geometry}
\usepackage{textpos}
\usepackage{mathtools}
\usepackage{xspace}
\usepackage{mdframed}
\usepackage{xcolor}
\newcommand\myeq{\stackrel{\mathclap{\normalfont\mbox{?}}}{=}}
\newcommand\eq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}
\newcommand\rd{\textsuperscript{rd}\xspace}
\newcommand\nth{\textsuperscript{th}\xspace}
\newcommand\nd{\textsuperscript{nd}\xspace}
\newcommand{\eps}{\epsilon}


\newenvironment{answer}{\begin{mdframed}\textit{Answer:}}{ \end{mdframed}}
\newenvironment{colabs}{\begin{mdframed}\textit{Resource and Collaborator Statement: }}{ \end{mdframed}}
\newenvironment{proofSK}{\begin{mdframed}\textit{Sketch:}}{ \end{mdframed}}
\newcommand\bset{\{0,1\}}

\newcommand{\M}{\mathcal{M}}
\newcommand{\K}{\mathcal{K}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\Ad}{\mathcal{A}}
\newcommand{\Enc}{\mathtt{Enc}}
\newcommand{\Dec}{\mathtt{Dec}}
\newcommand{\PvK}{\mathsf{PrivK}}
\newcommand{\Mc}{\mathsf{Mac}_k}
\newcommand{\Vrf}{\mathsf{Vrfy}_k}

\begin{document}
%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}(-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 2} \\ 
\textbf{Due date: Thursday , February  18\nd}
\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)}
Define $  (t(n),q(n), \eps (n)) $-CPA security of $ \Pi $ as the statement that any attacker running in time $ t(n) $ and making at most $ q(n) $ queries to the Left-Right encryption oracle wins the CPA security game with probability at most $ \eps(n) $. Similarly, for the function $ F_K:\{0,1\}^{n'}\times \{0,1\}^n\to \{0,1\}^n $ (mapping $ n' $ bits of input to $ n $ bits using the key $ K $ of size $ n $) we can define $ (t_{PRF}(n),q_{PRF}(n),\eps_{PRF}(n)) $-PRF security, implying that for any distinguisher running in time $ t_{PRF}(n) $ and making at most $ q_{PRF}(n) $ queries to the PRF oracle distinguishes the $ F_{K}(\cdot) $ from a truly random function with advantage at most $ \eps_{PRF}(n)$. 

\begin{itemize}
	\item \textbf{Part 1}: Assume that $ F_K $ is a $ (t_{PRF}(n),q_{PRF}(n),\eps_{PRF}(n)) $-secure PRF mapping $ n' $ bit strings to $ n $ bit strings. What is the concrete security bound of the encryption scheme $ \Enc_K(m) = (r,F_K(r) \oplus m)$? Justify your answer.

	\item \textbf{Part 2}: In practice one often assumes that $q_{ENC}(n) \ll t_{ENC}(n)$ e.g., oftentimes one requires that secret keys are rotated after $2^{n/4}$ encryptions. In this case we can sometimes save bandwidth by reducing the length of the nonce $r$.  Suppose that $ q_{ENC}(n)  = 2^{n/4}$ and for any $t \leq 2^n$ that $ F_K$  is a $ (t, t, t/2^{n}) $-secure PRF mapping $n'$ bit nonces to $n$ bit outputs. If we want to ensure that our encryption scheme is $ (t, 2^{n/4}, 2^{-n/4} + t2^{-n+1}) $-CPA secure. How big does $ n' $ need to be? (Justify your answer)


			
\end{itemize}

			\begin{answer}
		\dots 
	\end{answer}
		\begin{colabs}
		\dots 
	\end{colabs}
\subsection*{Question 2  (20 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))$ (On any other input $x \neq 1^n$ the oracle ${g^\$ }(x)$ will simply return $\bot$). 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}\label{Q2P1}
	{{\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.

	
\end{enumerate}

		\begin{answer}
		\dots 
	\end{answer}
		\begin{colabs}
		\dots 
	\end{colabs}


\subsection*{Question 3 (20 points)} 
\begin{enumerate}

	\item Show that the CBC, OFB, and CTR modes of operation do not yield CCA-secure encryption schemes (regardless of $F$). Briefly describe how an attacker could win the CCA-Security game with non-negligible advantage. (Hint: Suppose that we encrypt a message $m=(m_1,m_2,m_3)$ and get back a ciphertext $c = (c_0,c_1,c_2,c_3)$. What happens if we flip a bit in $c_2$?)


	\item Let F be a pseudorandom permutation. Consider the mode of operation in which a uniform value $\mathsf{ctr} \in \{0,1\}^n$ is chosen, and the $i^{th}$ ciphertext block $c_i$ is computed as $c_i:= F_{k}(\mathsf{ctr} + i + m_i)$. Show that this scheme does not have indistinguishable encryptions in the presence of an eavesdropper.
	
\end{enumerate}

		\begin{answer}
		\dots 
	\end{answer}

		\begin{colabs}
		\dots 
	\end{colabs}



\subsection*{Question 4 (20 points)}
In this question, we explore what happens when the basic CBC-MAC construction is used with messages of different lengths.
\begin{itemize}
	\item Say the sender and receiver do not agree on the message length in advance (and so $\Vrf(m, t) = 1 \text{ iff } t \myeq \Mc(m)$, regardless of the length of m), but the sender is careful to only authenticate messages of length 2n. Show that an adversary can forge a valid tag on a message of length 4n. 	
	
	\item Say the receiver only accepts 3-block messages (so $  \Vrf(m, t) = 1  $) only if m has length 3n and  $ t = \Mc(m)$, but the sender authenticates messages of any length a multiple of $ n $. Show that an adversary can forge a valid tag on a new message. 

\end{itemize}
			\begin{answer}
		\dots 
	\end{answer}

		\begin{colabs}
		\dots 
	\end{colabs}

\subsection*{Question  5 (20 points)}
Let $(\mathsf{Gen}_1,H_1)$ and $(\mathsf{Gen}_2, H_2)$ be two hash functions. We define $(\mathsf{Gen}, H)$ as follow:
\begin{itemize}
 	\item $\mathsf{Gen}:$ runs $\mathsf{Gen_1}$ and $\mathsf{Gen_2}$ to obtain $s_1,s_2$
 	\item $H^{s_1,s_2}(x)=H_1^{s_1}(x)||H_2^{s_2}(x)$
 \end{itemize} 
 Prove that if at least one of $(\mathsf{Gen}_1,H_1)$ and $(\mathsf{Gen}_2,H_2)$ is collision resistant, then $(\mathsf{Gen},H)$ is collision resistant. 

			\begin{answer}
		\dots 
	\end{answer}
		\begin{colabs}
		\dots 
	\end{colabs}


\end{document}