\documentclass{article}
\usepackage{amsmath}				% want AMS fonts
\usepackage{amssymb}                            % use AMS symbols
%\usepackage[ruled]{algorithm2e}
\input{p}

%=================================================================
% My macros
%=================================================================
\newcommand{\Zstar}[1]{\ensuremath{\mathbb{Z}_{#1}^*}}

\newcommand{\pk}{\mathit{PK}}
\renewcommand{\sk}{\mathit{SK}}

\newcommand{\pr}{\mbox{Pr}}

\newcommand{\gen}{\mathit{Gen}}
\newcommand{\dom}{\mathit{Dom}}
\newcommand{\fakecom}{\mathit{FakeCom}}

\newcommand{\lsb}{\mathit{LSB}}
\newcommand{\RSA}{\mathit{RSA}}

\renewcommand{\mod}{\mbox{mod}}
\newcommand{\commit}{\mathit{Commit}}

\begin{document}
\homework{9}{April 11, 2007}{April 18, 2007}{Anna Lysyanskaya}


\problem{Collision Resistant Hash Functions}


Let $\{G,h_{K}\}$ be a family of collision-resistant hash
functions, where $G$ is the key generation algorithm that
generates a key $K$, and $h_K~:~D_K \mapsto \{0,1\}^*$ 
is the function indexed
by key $K$, with domain $D_K$.  
Recall that 
a function is collision-resistant if
the following 
are satisfied:

\begin{description}
\item[Non-triviality]:  for all keys $K \in G$, 
for any input $x$, $|x|>k$, 
$h_K(x)$ is always shorter than $x$.
\item[Collision-resistance]: for all 
PPT adversaries $\{A_k\}$, there exists a 
negligible function $\nu(k)$ such that
$$\Pr[K\leftarrow G(1^k); (x_1,x_2) \leftarrow A_k(K) : h_K(x_1) = h_K(x_2)
\wedge x_1,x_2\in D_K] = \nu(k)$$
(recall that $D_K$ is the domain of the function $h_K$.)
\end{description}

\begin{alphabetize}
\item
Let $\{G,h_{K}\}$ be a family of
collision-resistant hash functions, where 
$D_K$,
the domain
of the function, consists of all strings of length up to 
$L(k)$, and $L(k)>k$ is a polynomial.
Let $h'_K(x) = h_K(h_K(x))$.  Is $\{G,h'_K\}$ a 
family of collision-resistant hash functions?


\item
Suppose you have a collision-resistant 
hash function
that reduces its input by a little bit, for example from
$k+1$ bits to $k$ bits.  
Your task is to design a hash function that reduces an $L>k$ bit
string into a $k$ bit string, in such a way that it is
hard to find collisions.
More precisely, let $\{G,h_{K}\}$ be a family of
collision-resistant hash functions, 
$h_K~:~\{0,1\}^{k+1}\mapsto \{0,1\}^{k}$.
Let $L(k)>k$ be any given polynomial.
Design a collision-resistant hash function family
$\{G,h^L_K\}$ such that
$h^L_K~:~\{0,1\}^{L(k)}\mapsto \{0,1\}^k$.

\end{alphabetize}

\problem{Zero Knowledge Proofs}
Recall that in homework 2, we examined a zero knowledge proof protocol for the language of vertex cover.  
\begin{alphabetize}
\item On homework 2, we discussed a physical protocol using physical drawings and paper cups.  Explain how we could implement the same protocol cryptographically using commitments.

\item Recall our definition of zero knowledge.
We said that a proof scheme with prover algorithm $P$, and verifier algorithm $V$ is zero knowledge iff:

$\forall$ ppt $V'$, $\exists$ ppt $S$ such that $\forall x\in L$, $\forall$ witnesses $w$ the following two distributions are indistinguishable:
$$D_0 = \{P(1^k,x,w) \leftrightarrow V'(1^k,x) \rightarrow view:view\}$$
$$D_1 = \{S(1^k,x) \leftrightarrow^* V'(1^k,x) \rightarrow view:view\}$$
Note that in the second experiment, $S$ is allowed to rewind $V'$ and run him on different inputs polynomially many times.

Describe a simulator for the vertex cover proof protocol you gave in part (a).

\item Argue that the protocol given in part (a) is zero knowledge.
\end{alphabetize}

\problem{Commitments}
\begin{alphabetize}
\item Recall the definition of commitments that we discussed in class:

Let $\commit$ be algorithm which takes input of the form $1^k,x,r$, where $k$ is a security parameter, $x\in \dom$ is the value we will commit to, and $r\in\{0,1\}^{l(k)}$ is the randomness used.
$\commit$ is a perfectly binding commitment scheme if the following two properties hold:
\begin{description}
\item [Hiding] $\exists$ a randomized algorithm $\fakecom$ such that
$\forall x\in \dom$, the distribution $$D_0= \{r\leftarrow
\{0,1\}^{l(k)};C\leftarrow \commit(1^k,x,r):C\}$$ is indistinguishable from the distribution $$D_1 =  \{C\leftarrow \fakecom(1^k):C\}.$$
\item [Perfect Binding] $\forall$ $\A$,  
$$\pr[C,x_1, x_2, r_1, r_2 \leftarrow \A(1^k): C= \commit(1^k, x_1, r_1) = \commit(1^k, x_2, r_2)\wedge x_1\neq x_2]=0$$
\end{description}

Now consider the function $f(y)$, which first parses $y$ as $x\circ r$, and then computes $\commit(1^k, x,r)$.

Prove that if $\commit$ is a commitment scheme as defined above, then $f$ is a one way function. (Give a reduction).


\item We can consider a slightly weaker definition which we call Computationally Binding Commitments.  
Intuitively, here we want a slightly weaker binding property, so that
there is a negligible probability that the adversary will be able to
produce two openings ($x_1,r_1$ and $x_2,r_2$) for the same
commitment.  However, note that when we make this change, we also need
to change our definition to consider families of commitment schemes
keyed by some public key.  Explain why.


\item
It turns out that adding a public key also allows us to get commitments which satisfy a stronger hiding property.

The resulting definition goes as follows:
An pair of algorithms $\gen,\commit$ is a computationally binding perfectly hiding commmitment scheme if the following two properties hold:


\begin{description}
\item [Hiding] $\exists$ a randomized algorithm $\fakecom$ such that
$\forall x\in \dom$, $\forall \pk$ in the output range of $\gen$, the distribution $$D_0= \{r\leftarrow
\{0,1\}^{l(k)};C\leftarrow \commit_\pk(1^k,x,r):(C,\pk)\}$$ is identical to the distribution $$D_1 =  \{C\leftarrow \fakecom(1^k, \pk):(C,\pk)\}.$$
\item [Computational Binding]  $\forall$ ppt. $\A$, $\exists $ negligible function $\nu(k)$ such that 
\begin{eqnarray*}
&\pr[&\pk \leftarrow \gen, C,x_1, x_2, r_1, r_2 \leftarrow \A(1^k,\pk):\\&& C= \commit_\pk(1^k, x_1, r_1) = \commit_\pk(1^k, x_2, r_2)\wedge x_1\neq x_2]=\nu(k)
\end{eqnarray*}
\end{description}

Now consider a family of functions $G, f$.  $G$ will run $\gen$ to obtain a public key $\pk$. $f_\pk(y)$ will first parse $y$ as $x\circ r$, and then compute $\commit_\pk(1^k,x,r)$.

Let's prove that if $\gen,\commit$ is a computationally binding commitment scheme, then $G,f$ as defined above, is a family of one way functions.

Suppose we are given an adversary $\A$ who with high probability can, given $f_\pk(y)$, find $y'$ such that $f_\pk(y)=f_\pk(y')$.  Consider the following two cases:  
\begin{itemize}
\item 
Suppose that when we give the adversary $f_\pk(y=x\circ r)$, with nonnegligible probability, he outputs $y'=x\circ r'$ (where it is possible that $r'=r$).  Then show that we can build an algorithm $\B$ which breaks the Hiding property.  

\item Now suppose that when we give the adversary $f_\pk(y=x\circ r)$, with
nonnegligible probability, he outputs $y'=x'\circ r'$, where $x'\neq x$ (and
again it is possible that $r'=r$).  Then show that we can build an
algorithm $\B$, which breaks the Binding property of the commitment.

\item Conclude the proof 
\end{itemize}
\end{alphabetize}



\end{document}