\documentclass[a4paper]{article}

\usepackage[english]{babel}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath}
\usepackage{enumerate}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{hyperref}
\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{\sign}{\ensuremath{\class{Sig}}\xspace}
\newcommand{\gen}{\ensuremath{\class{Gen}}\xspace}

\hypersetup{colorlinks,urlcolor=blue}
\usepackage{graphicx}
\usepackage[colorinlistoftodos]{todonotes}

\title{CSE 5852: Problem Set 9}
\date{Due: December 5, 2016}
%\author{You}

\begin{document}
\maketitle

In this assignment you'll be  working with hash functions.  Recall the different security properties of a hash function:

\begin{description}
\item[Collision resistance]  For all PPT $\mathcal{A}$, there exists a negligible function $\epsilon(n)$ such that for $k\leftarrow \gen(1^n)$, 
\[
\Pr[(m_1, m_2)\leftarrow \mathcal{A}(1^n, k) \wedge m_1\neq m_2 \wedge H_k(m_1) = H_k(m_2) ] \le \epsilon(n).
\]
this probability is over the choice of $k$ and any randomness used by $\mathcal{A}$.

\item[Second-preimage resistance] A hash function is second preimage resistant if given $k$ and a uniform $m$ it is infeasible for a PPT adversary to find some $m'\neq m$ such that $H_k(m') = H_k(m)$.  \text{Note:} Look at the distinction between this and collision resistance.  Here $\mathcal{A}$ doesn't get to choose the point $m$ they are forced to find a preimage on a random point.
\item[Preimage resistance] A hash function is preimage resistant if given $k$ and uniform $y$ it is infeasible for a PPT $\mathcal{A}'$ to find a value $m$ such that $H(x) = y$.
\end{description}

\section{Collision-resistant hashing}
\paragraph{20 pts} 
\begin{theorem} Let $H: \zo^\ell \times \zo^{n+k} \rightarrow \zo^n$ be a family of collision resistant hashes.  Show that $H': \zo^\ell \times \zo^{n+2k} \rightarrow \zo^n$ defined as follows is a family of collision resistant hashes:

\begin{enumerate}
\item $H_k'(m)$.  Interpret $m = m_{1...k}, m_{k+1...n+2k}$.  Set $y = H_k(m_{k+1....n+2k})$. 
\item Compute $z' = H_k(m || y)$.
\end{enumerate}
\end{theorem}

Show that this $H_k'$ is collision resistant.  Let $m, m'$ be a collision output by $\mathcal{A}$.  Separately consider the following cases (what is the collision output by $\mathcal{A}'$?):

\begin{enumerate}
\item \textbf{5 pts} $m_{k+1...n+2k} \neq m_{k+1...n+2k}$ and $y = y'$.
\item \textbf{5 pts} $m_{1...k} = m_{1...k}'$ and $m_{k+1...n+2k} \neq m_{k+1...n+2k}$ and $y \neq y'$.
\item \textbf{5 pts} $m_{1...k} \neq m_{1...k}'$ and $m_{k+1...n+2k} \neq m_{k+1...n+2k}$ and $y \neq y'$.
\item \textbf{5 pts} $m_{1...k} \neq m_{1...k}'$ and $m_{k+1...n+2k} = m_{k+1...n+2k}$.
\end{enumerate}

\paragraph{20 pts}  Consider a hash function $H:\zo^\ell \times \zo^{2n} \rightarrow \zo^n$.  Consider the following adversary $\mathcal{A}$:

\begin{enumerate}
\item While all $y_i$ are distinct:
\subitem Choose random (but distinct) $x_i$.
\subitem Compute $y_i = H_k(x_i)$. 
\item Output $x_i, x_j$ such that $H_k(x_i) = H_k(x_j)$.
\end{enumerate}

\textbf{10 pts} Assume an output space of $2^n$. What needs to happen for each value $x_i$ to be unique?  What is that probability?  Your answer can be an algebraic expression, you don't need to try and simplify?  Does this quantity get bigger or smaller with the number of guesses?

\textbf{10 pts}  Assume we want to build an adversary that succeeds with probability $.5$ how many $x_i$ need be generated by $\mathcal{A}$?  You can consult \url{https://en.wikipedia.org/wiki/Birthday_problem} for some approximations on this value.


\section{Repeated Hashing}

\paragraph{20 pts} 
Let $\gen, H$ be a family of collision resistant hash functions.  Define $\gen', H'$ as the following:

\begin{itemize}
\item $\gen'$: Set $k = k_1, k_2$ where $k_1\leftarrow \gen(1^n)$ and $k_2 \leftarrow \gen(1^n)$.
\item $H'_{k_1, k_2}(m) = H_{k_1}(m) || H_{k_2}(m)$.
\end{itemize}

Show that $(\gen', H')$ is collision resistant.  Provide a reduction to the collision resistance of $(\gen, H)$.

\paragraph{20 pts} 
Let $\gen_1, H_1$ and $\gen_2, H_2$ be two families of second-preimage resistant hash functions.  Define $\gen, H$ as the following:

\begin{itemize}
\item $k = k_1, k_2$ where $k_1 \leftarrow \gen_1(1^n)$ and $k_2 \leftarrow \gen_2(1^n)$. 
\item $H_{k_1, k_2}(m) = H_{1, {k_1}}(m) || H_{2, k_2} (m)$.
\end{itemize}

Show that $(\gen, H)$ is second-preimage resistant if both $(\gen_1, H_1)$ and $(\gen_2, H_2)$ are second preimage resistant.  

\paragraph{20 pts} 
Let $\gen_1, H_1$ and $\gen_2, H_2$ be two families of preimage resistant hash functions.  Define $\gen, H$ as the following:

\begin{itemize}
\item $k = k_1, k_2$ where $k_1 \leftarrow \gen_1(1^n)$ and $k_2 \leftarrow \gen_2(1^n)$. 
\item $H_{k_1, k_2}(m) = H_{1, {k_1}}(m) || H_{2, k_2} (m)$.
\end{itemize}

Provide an example of $\gen_1, H_1$ and $\gen_2, H_2$ such that $\gen, H$ is not preimage resistant.



\paragraph{20 pts} 
Let $\gen_1, H_1$ and $\gen_2, H_2$ be two families of preimage resistant hash functions.  Define $\gen, H$ as the following:

\begin{itemize}
\item $k = k_1, k_2$ where $k_1 \leftarrow \gen_1(1^n)$ and $k_2 \leftarrow \gen_2(1^n)$. 
\item $H_{k_1, k_2}(m) = H_{1, {k_1}}(m) || H_{2, k_2} (m)$.
\end{itemize}

Provide an example of $\gen_1, H_1$ and $\gen_2, H_2$ such that $\gen, H$ is not preimage resistant.



\end{document}