\documentclass[10pt]{article}
\usepackage{amsfonts,amsthm,amsmath,amssymb}
\usepackage{array}
\usepackage{epsfig}
\usepackage{fullpage}
\usepackage[table]{xcolor}
\usepackage{adjustbox}
\usepackage{dashbox}
\usepackage{cjhebrew}
\usepackage{xspace}

\begin{document}
\input{preamble.tex}

\lecture{3}{November 28, 2019}{Nir Bitansky}{December 12}

\paragraph{Instructions:}
\begin{itemize}

  \item
  Type your solution and email it to "focf19hw@gmail.com", with subject "HW\#, ID\#, Name".
  \item
  You're encouraged to use latex. You can find on the webpage the assignment's tex file to help you.
  \item
  You can cooperate. However, you should write the solution by yourself, and list all collaborators for each question. Same goes for any external sources that you may use.
  \item
  Do not discuss solutions over the course's forum. You are more than welcome though to ask for clarifications regarding the questions themselves.
\end{itemize}

\bigskip
\begin{enumerate}
\item
In class, we've seen the GGM PRF) where both the keys $s$ and the inputs $x$ were of length $n$. We would like to extend this construction so that for keys $s\in\zo^n$, we can apply the function for inputs of arbitrary length $x\in\zo^*$.
\begin{enumerate}
  \item (10 pts) Consider applying the GGM function applied as is for inputs of arbitrary length. That is, for any $x\in\zo^*$, and letting $\ell$ be the length of $x$, and $G$ a length doubling PRG, define
  $$
  F_s(x) := G_{x_\ell}(G_{x_{\ell-1}}(\cdots G_{x_2}(G_{x_1}(s))\cdots))\enspace.
  $$
  Show that $F$ is not a PRF. (Recall that $G_0(s)$ and $G_1(s)$ denote the first and second $n$-bit blocks of the output, respectively.)
  \item (25 pts)
  Consider the following variant of GGM. Let $G:\zo^n\rightarrow \zo^{3n}$ be a length-tripling PRG, and denote by $G_0(s),G_1(s),G_2(s)$ the first, second, and third blocks of $n$ output bits, respectively. For any $x\in\zo^*$, and letting $\ell$ be the length of $x$, define
  $$
  F_s(x) := G_{2}(G_{x_\ell}(G_{x_{\ell-1}}(\cdots G_{x_2}(G_{x_1}(s))\cdots))\enspace.
  $$
  Show that $F$ is a PRF.
\end{enumerate}
\item
Let $(Auth,Ver)$ be a MAC, and assume $Auth$ is deterministic (i.e., it does not toss any coins on its own) and that for secret key of size $n$ it produces tags of size $n$.
\begin{enumerate}
  \item (30 pts) Consider the function $G:\zo^n\times\zo^n\rightarrow\zo^{3n}$ defined as:
  $$G(sk,r) = r, \langle Auth_{sk}(1),r\rangle,\langle Auth_{sk}(11),r\rangle,\dots,\langle Auth_{sk}(1^{2n}),r\rangle\enspace,$$
  where $\langle\cdot,\cdot\rangle$ denotes inner product modulo $2$. Show that $G$ is a PRG.\footnote{You're allowed to use (without proof) the fact that for any distribution $X$ and jointly distributed bit $B$, if $A$ distinguishes $X,B$ from $X,U_1$ with advantage $\varepsilon$, there exists a predictor $P$ that given $X$ predicts $B$ with probability $1/2+\varepsilon/2$ (where $P$ runs in time polynomially related to that of $A$).}
  \item
  ({\bf Bonus}: 10 pts) Consider the function $G:\zo^n\times\zo^n\rightarrow\zo^{3n+1}$ defined as:
  $$G(sk,r) = r, \langle Auth_{sk}(r),r\rangle,\langle Auth_{sk}(1),r\rangle,\langle Auth_{sk}(11),r\rangle,\dots,\langle Auth_{sk}(1^{2n}),r\rangle\enspace.$$
  Prove that this function is also a PRG, or give a counter example.
\end{enumerate}
\item
Let $H$ be a collision-resistant hash function that for a key $hk\in \zo^n$ maps $\zo^{2n}$ to $\zo^n$. We would like to use $H$ to construct  a new collision-resistant $H^*$ for inputs of arbitrary length. We first focus on inputs whose length is a power of two, $2^\ell$ for some $\ell$. We consider the following construction (known as {\em Merkle's tree hash}).

\smallskip\noindent Given a key $hk$ for $H$, and an input $x$ of length $2^\ell$, consider the following labeling $\set{L_v}_v$ of the binary tree of depth $\ell$ whose nodes are represented by $\set{v\in\zo^i,i\in\set{0,\dots,\ell}}$:
\begin{itemize}
\item
For every leaf $v\in \zo^\ell$, $L_v := x_v 0^{n-1}$ (the $v$th bit of $x$ padded).
\item
For every intermediate node, $L_v = H_{hk}(L_{v0}L_{v_1})$ (the hash of its sons).
\end{itemize}
The hash $H^*_{hk}(x)$ is then set to be the root label $L_\varepsilon$.
\begin{enumerate}
  \item (25 pts) Show that $H^*$ is also collision resistant in the sense that it is hard to find to inputs $x\neq x'$ of {\em the  same} length $2^\ell$, which collide under $H^*_{hk}$.
  \item (10 pts) Briefly explain how to extend $H^*$ to inputs of any size (not necessarily a power of two), and so that it is hard to find collisions $x\neq x'$ also for inputs that are not of the same length. No need to prove.
\end{enumerate}
\end{enumerate}


\end{document}