\documentclass[11pt]{article}

\usepackage[margin=0.75in]{geometry}
\input{latexdefs}

\begin{document}

\newlength{\boxwidth}
\setlength{\boxwidth}{\textwidth}
\addtolength{\boxwidth}{-2cm}
\noindent\framebox[\textwidth]{
\begin{minipage}[t]{\boxwidth}
  {\bf CS 355: Topics in Cryptography \hfill Spring 2022}  \
  \begin{center} 
    {\Large Problem Set 1}
  \end{center}
\textbf{Due:}
Friday, 8 April 2022 (submit via Gradescope)
\end{minipage}}
\vspace{0.7cm}

\noindent \textbf{Instructions:} You {\bf must} typeset your
solution in LaTeX using the provided template:
\begin{center}
  \url{https://crypto.stanford.edu/cs355/22sp/homework.tex}
\end{center}

\noindent \textbf{Submission Instructions:} You must submit your problem set
via \href{https://gradescope.com/}{Gradescope}. Please use course code
\textbf{862WDX} to sign up. Note that Gradescope requires that the solution to
each problem starts on a \textbf{new page}.

\medskip

\noindent \textbf{Bugs:} We make mistakes! If it looks like there might be a mistake
in the statement of a problem, please ask a clarifying question on Ed.

\hrule
\problem{True/False [7 points]}
\begin{enumerate}[label=(\alph*), leftmargin=*]
    \item Which of the following are true in a world where $\mathsf{P}=\mathsf{NP}$.
    \begin{enumerate} 
      \item[i] Secure PRFs exist in the standard model.
      \item[ii] Secure PRFs exist in the random oracle model.
      \item[iii] The one-time-pad cipher is secure.
    \end{enumerate}
    \item If there exists a PRG with 1-bit stretch, there exists a PRG with $n^{800}$-bit stretch (where $n$ is the length of the PRG seed).
    \item Let $F\colon\calK\times\calX \to \calX$ be a pseudorandom permutation. Then:
    \begin{enumerate}
        \item[i] $f_{k=0}(x)\deq F(0,x)$ is (always) a one way function.
        \item[ii] $f_{k=0}(x)\deq F(0,x)$ is (always) a one way permutation.
		\item[iii] $f_{x=0}(k)\deq F(k,0)$ is (always) a one way permutation.
  \end{enumerate}
\end{enumerate}
\problem{Merkle Puzzles [15 points]}
In lecture, you saw Merkle's key-exchange protocol.
That protocol uses a hash function $H \colon \Z_{\lambda^2} \to \zo^{\log^2 \lambda}$,
where $\lambda \in \Z^+$ is the security parameter. 
We model $H$ as a random oracle.

Merkle's key-exchange protocol works as follows:
\begin{enumerate}[topsep=-1ex,itemsep=-1ex]
  \item Alice picks integers $a_1, \dots, a_\lambda\getsr \Z_{\lambda^2}$
and publishes $H(a_1), \dots, H(a_\lambda)$.
  \item Bob picks integers $b_1, \dots, b_\lambda \getsr \Z_{\lambda^2}$
and publishes $H(b_1), \dots, H(b_\lambda)$.
  \item \label{step:fail} Alice and Bob find the least $i,j \in \{1,\dots,\lambda\}$ 
    such that $H(a_i) = H(b_j)$. If no such pair exists, output ``fail.''
  \item Alice outputs $a_i$ as her shared secret with
        Bob. Bob outputs $b_j$ as his shared secret with Alice.
\end{enumerate}

\medskip
While Alice and Bob each make $\lambda$ queries to $H$, we argued in class that any
successful eavesdropping attacker must make $\Omega(\lambda^2)$ queries to $H$.

\begin{enumerate}[label=(\alph*), leftmargin=*]
  \item \label{part:fail} There is some chance that Alice and Bob agree on indices
        $i$ and $j$ in Step~\ref{step:fail}
        such that $H(a_i) = H(b_j)$ but $a_i \neq b_j$. 
        First, explain why this is problematic in the context
        of a key-agreement protocol.
        Next, show that the probability of this bad event is negligible.


  \item Prove that Alice and Bob successfully
        agree on a shared secret with probability at least $1/100$.
        Make sure that your argument accounts for the failure event
        from part \ref{part:fail}.\newline
        [\textbf{Hint:} You may use the ``Birthday Bound'' in Appendix B.1 
        of the Boneh-Shoup book.]
        

  \item Show that it is possible to reduce the failure probability 
        to some quantity \textit{negligible} in $\lambda$ while still
        keeping the total communication between Alice and Bob $\Otilde(\lambda)$.
        (Recall that $\Otilde(\lambda)$ is notation for $\lambda \cdot \polylog(\lambda)$.)
        

  \item As described, Merkle's scheme requires total communication
        $2 \lambda \log^2 \lambda$ bits. Describe how to reduce the 
        total communication to $\lambda \log^2 \lambda + o(\lambda)$ bits,
        without changing the protocol's failure probability 
        or security properties.

		
  \item \textbf{Research problem [+100 points].}
        If we take $\lambda \approx 2^{30}$ to get security against attackers running
        in time $\lambda^2 \approx 2^{60}$, then Merkle's protocol requires a huge amount
        of communication---around ten \textit{gigabytes}.
        Show that it is possible to reduce the communication of Merkle's scheme
        to $\Otilde(1)$ while: (a) Alice and Bob still run in time $\Otilde(\lambda)$
        and (b) the protocol maintains security against attackers running in time $o(\lambda^2)$.
        Even constructing a scheme with communication complexity
        $\Otilde(\lambda^\epsilon)$ for any $\epsilon < 1$ would be very interesting.
        Your solution must somehow skirt 
        the \href{https://eccc.weizmann.ac.il/report/2018/031/}{known impossibility results}.

  \item \textbf{Research problem [+1000 points].}
        Construct a key-agreement protocol from a one-way function (e.g., AES) in which
        Alice and Bob run in time~$\lambda$ and the best attack runs in 
        time \textit{super-polynomial} in~$\lambda$.
        We have no idea how to construct such a protocol, but we also have no
        way to rule out the existence of such a protocol either.
        A \href{https://cseweb.ucsd.edu/~russell/secret.ps}{famous result of
        Impagliazzo and Rudich} implies that any such protocol would likely not
        make ``black-box'' use of the one-way function.

\end{enumerate}
\problem{Key Leakage in PRFs [5 points]}
Let $F$ be a secure PRF defined over $\big( \calK, \calX, \calY \big)$, where
$\calK = \calX = \calY = \zo^n$. 
Let $\calK_1 = \zo^{n+1}$. Construct a new PRF $F_1$, defined over
$\big(\calK_1, \calX, \calY \big)$, with the following property: the PRF
$F_1$ is secure; however, if the adversary learns the last bit of the key
then the PRF is no longer secure. This shows that leaking even a
\emph{single} bit of the secret key can completely destroy the PRF security
property. \newline[\textbf{Hint:} Try changing the value of $F$ at a single point.]
\problem{P and NP [5 points]}
Show that
the existence of any one-way function implies
$\mathsf{P} \ne \mathsf{NP}$.

\noindent\textit{%
Recall:
if $\mathsf{P} = \mathsf{NP}$,
then for any an deterministic, efficient algorithm
$\mathcal{A}(x,w) \to \zo$
there
is a deterministic, efficient algorithm
$\mathcal{B}(x) \to \zo$
that computes whether $\exists w.\ \mathcal{A}(x,w)=1$
}
\problem{Vector Commitments [5 points]}
In this problem we consider \textit{vector commitments}:
commitments to vectors which can be opened to one index at a time.

The classic construction vector commitment scheme is the \textit{Merkle tree},
which is parameterized by a hash function $H:
\calX\times\calX\to\calX$.
The core of this construction is a hash tree, as shown in
Figure~\ref{fig:merkle}.
Each internal node in the tree represents an evaluation of the hash function
over the child nodes.
The $\Commit$ procedure evaluates the hash tree, returning the root at the
commitment.
The $\IdxOpen$ procedure produces the siblings along a path
(e.g., the blue nodes, for $x_4$),
and the $\IdxVerify$ checks the hash evaluations along the path.
\begin{figure}[t]
  \centering
  \begin{tikzpicture}[
      level 0/.style={sibling distance=80mm},
      level 1/.style={sibling distance=80mm},
      level 2/.style={sibling distance=40mm},
      level 3/.style={sibling distance=20mm},
      level 4/.style={sibling distance=10mm},
      level distance=0.7cm,
      edge from parent path={(\tikzparentnode\tikzparentanchor) edge[Stealth-]
      (\tikzchildnode.north)},
      h/.style={trapezium, draw, trapezium left angle=70, trapezium right angle = 70}
    ]
    \draw
      (0,0) node (R) {$c$}
      child {
        node[h] {$h_{3,0}$}
        child {
          node[h,blue] {$h_{2,0}$}
          child {
            node[h] {$h_{1,0}$}
            child { node[] {$x_0$} }
            child { node[] {$x_1$} }
          }
          child {
            node[h] {$h_{1,1}$}
            child { node[] {$x_1$} }
            child { node[] {$x_2$} }
          }
        }
        child {
          node[h] {$h_{2,1}$}
          child {
            node[h] {$h_{1,2}$}
            child { node[] {$x_4$} }
            child { node[blue] {$x_5$} }
          }
          child {
            node[h,blue] {$h_{1,3}$}
            child { node[] {$x_6$} }
            child { node[] {$x_7$} }
          }
        }
      }
    ;
  \end{tikzpicture}
  \caption{A Merkle tree}
  \label{fig:merkle}
\end{figure}

More precisely, the Merkle tree vector commitment scheme is defined by three
algorithms:
\begin{itemize}[leftmargin=*]
  \item $\Commit(d \in \N, x \in \calX^{2^d}) \to \calX:$

    \quad for $i \in \{0, 1, \ldots, 2^{d}-1\}$: $h_{0,i}\gets x_i$

    \quad for $\ell \in \{1, 2, \ldots, d\}$,
    for $i \in \{0, 1, \ldots, 2^{d-\ell}-1\}$:
    $h_{\ell,i}\gets H(h_{\ell-1,2i}, h_{\ell-1,2i+1})$

    \quad return $h_{d,0}$
  \item $\IdxOpen(d \in \N, i \in \N, x \in \calX^{2^d}) \to \calX^d:$

    \quad compute $h_{\ell,i}$ as in $\Commit$

    \quad for $\ell \in \{0, \ldots, d-1\}:$
    $p_i \gets h_{\ell,((i\gg \ell)\oplus 1)}$
    \unskip\footnote{
      Here, $\gg$ is logical right shift and $\oplus$ is bitwise XOR, as in C.
      That is, $x \gg y$ denotes $\lfloor x / 2^y\rfloor$ and
      $x \oplus y$ denotes the integer with binary representation equal to the
      bitwise XOR of the binary representations of $x$ and $y$.
    }

    \quad return $(p_0, \ldots, p_{d-1})$
  \item $\IdxVerify(d \in \N, i \in \N, x, \in \calX, c \in \calX, p \in \calX^d) \to \{0,1\}$:

    \quad $h_0\gets x$

    \quad for $\ell \in \{1, \ldots, d\}:$

    \quad\quad $j\gets i \gg (\ell-1)$

    \quad\quad if $j$ is odd:
    $h_\ell\gets H(p_{\ell-1}, h_{\ell-1})$

    \quad\quad else:
    $h_\ell\gets H(h_{\ell-1}, p_{\ell-1})$


    \quad return $h_d \eqq c$
\end{itemize}

A vector commitment scheme is \textit{index binding} if for all
$d \in \N$ and
for all efficient adversaries $\calA$,
\[
  \Pr
  \left\{
    \IdxVerify(d, i, x, c, p) = 1 \land
    \IdxVerify(d, i, x', c, p') = 1 \land
    x \ne x'
    :
    (c, i, x, p, x', p') \gets \calA(d, \lambda)
  \right\}
  =
  \negl(\lambda)
\]
where $\lambda$ is the security parameter of $H$.
A hash function $H$ is \textit{collision resistant} if for all
efficient adversaries $\calA$,
\[
  \Pr
  \left\{
    H(x, y) = H(x', y') \land
    (x, y) \ne (x', y')
    :
    (x, y, x', y') \gets \calA(\lambda)
  \right\}
  =
  \negl(\lambda)
\]

\begin{enumerate}[label=(\alph*), leftmargin=*]
  \item
Please prove that Merkle tree vector commitments are index binding if $H$
is collision-resistant.

\item
  \textbf{Extra Credit [2 points].}
  Is a Merkle tree commitment hiding
  in the random oracle model?
  If so, prove it.
  If not, briefly explain why,
  modify the scheme to make it hiding in the random oracle model,
  and prove that the modification is hiding in the random oracle model.
  \textit{Note: A few different ``hiding'' properties can be formalized for
  vector commitments. You should consider whether the commitment itself is
  hiding---you need not consider opening proofs.}
\end{enumerate}
\problem{Our Favorite PRF [10 points]}
In class we saw the PRF $F(k,x)=H(x)^k$ and were told that it has many useful properties. In this problem, we will explore two applications of this PRF. 

\begin{enumerate}[label=(\alph*), leftmargin=*]
  \item Let $F:\calK\times \calX\to\calY$ be a PRF defined over groups $(\calK, +)$ and $(\calY, \otimes)$, where $+$ and $\otimes$ are the respective group operations in those groups. We say $F$ is \emph{key-homomorphic} if it holds that 
  \[F(k_1+k_2, x) = F(k_1, x) \otimes F(k_2, x).\] 
  
  Is the PRF $F(k,x)=H(x)^k$ defined with a random oracle $H:\calX\to G$ (where $G$ is a group of prime order $p$) a key-homomorphic PRF? Please prove your answer one way or the other. 
  

  \item \emph{Key rotation} is a common problem encountered in cloud storage: how to change the key under which data is encrypted without sending the keys to the storage provider? A naive solution is to download the encrypted data, decrypt it, re-encrypt it under a new key, and re-upload the new ciphertext. We will now see how this process can be made more efficient with a key-homomorphic PRF. 
  
  Suppose you have a ciphertext $c$ made up of blocks $c_1,...,c_N$ that corresponds to a message $m=(m_1,...,m_N)$ encrypted under a key $k_1$ using a key-homomorphic PRF $F$ in counter mode, i.e., $c_i = m_i \otimes F(k_1, i)$. Now you want to rotate to a key $k_2$. It turns out you can send the storage provider a single element $k_\ms{update}\in\calK$ which it can then use to generate $c'$, an encryption of $m$ under $k_2$. Please tell us how you can compute $k_\ms{update}$ and how the storage provider can use $k_\ms{update}$ and $c$ to compute~$c'$. 
  
  
  \item An \emph{oblivious PRF} is an interactive protocol between a client who holds a message $x$ and a server who holds a key $k$. The protocol allows the client to learn the PRF evaluation $F(k,x)$ without the server learning anything about $x$. Oblivious PRFs are used in many advanced crypto protocols.
  
  It turns out that there is an oblivious PRF protocol for the PRF $F(k,x)=H(x)^k$. Please show us how a client holding $x$ and a server holding $k$ can interact so that the client learns $H(x)^k$ while the server learns nothing about $x$. You don't need to prove security, we would just like to see the protocol. 
    
\end{enumerate}
\end{document}
