\documentclass[11pt]{article}

\usepackage[margin=0.75in]{geometry}
\usepackage{tikz}
\usetikzlibrary{shapes.geometric}
\usetikzlibrary{arrows.meta}
\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 2021}  \\ [-0.3cm]
  \begin{center} 
    {\Large Problem Set 1}
  \end{center}
  {\bf Due:} April 12, 2021 at 11:59pm PT (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/21sp/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{V8WVZK} 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 Piazza.

\hrule

\paragraph{Problem 1: Conceptual Questions [8 points].}
For each of the following statements, say whether it is TRUE or FALSE. Write \emph{at most one sentence} to justify your answer. 

\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 $P\colon\calK\times\calX \to \calX$ be a pseudorandom permutation. Then:
  \begin{enumerate}
	  \item[i] $f_{k=0}(x)\deq P(0,x)$ is (always) a one way function.
	  \item[ii] $f_{k=0}(x)\deq P(0,x)$ is (always) a one way permutation.
	  \item[iii] $f_{x=0}(k)\deq P(k,0)$ is (always) a one way function.
	  \item[iv] $f_{x=0}(k)\deq P(k,0)$ is (always) a one way permutation.
  \end{enumerate}

\end{enumerate}


\paragraph{Problem 2: 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.]


\paragraph{Problem 3: Multi-Commitments [10 points].}

Let $\G$ be a group of prime order $q$ in which the discrete logarithm problem is hard.
Let $g$ and $h$ be generators of $\G$. 
As we saw in class, 
the Pedersen commitment scheme commits to a message $m \in \Z_q$
using randomness $r \in \Z_q$ as $\Comm(m; r) \deq g^m h^r \in \G$. Moreover, we saw that Pedersen commitments are \emph{additively homomorphic}, meaning that given commitments to $m_1$ and $m_2$, one can compute a commitment to $m_1+m_2$. 
The ``public parameters'' associated with the Pedersen commitment scheme
are the description of the prime-order group
$\G$ and the group elements $g$ and $h$.

\begin{enumerate}[label=(\alph*), leftmargin=*]
\item Use $\G$ to construct an additively homomorphic commitment scheme $\Comm_n(m_1, \dots, m_n; r)$
      that commits to a length-$n$ vector of messages $(m_1, \dots, m_n) \in \Z_q^n$
		using randomness $r \in \Z_q$. The output of the commitment should be short -- only a single group element.
		%with only a \emph{single} group element (i.e., the type signature is
		%$\Comm_n \colon \Z_q^n \times \Z_q \to \G$).
    You should specify both the public parameters of your scheme (which may be different from
      that of the basic Pedersen commitment scheme) as well as the description of the
      $\Comm_n$ function.
      
\item Prove that your commitment scheme is perfectly hiding and
      computationally binding (assuming hardness of discrete log in $\G$).

\item Show that if you are given a hash function $H \colon \Z_q \to \G$
      (modeled as a random oracle), the public parameters for your 
      construction from Part~(a) only needs to consist of the description
      of the group $\G$ and the description of $H$.
      Argue {\em informally} why your construction is secure. You do {\em not}
      need to provide a formal proof. This problem shows that
      getting rid of public parameters is
      another reason why random oracles are useful in practice!

\item \textbf{Extra Credit [3 points].} Prove formally
  that your construction from Part~(c) is secure in the random oracle model.

\end{enumerate}

\paragraph{Problem 4: Vector Commitments [5 points].}
The previous problem considered multi-commitments:
commitments to vectors which can be opened all at once.
In this problem we consider \textit{vector commitments}:
commitments to vectors which can be opened to one index at a time.

The classic construction of a 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$.


\begin{enumerate}[label=(\alph*), leftmargin=*]
  \item
Please prove that Merkle tree vector commitments are index binding if $H$
is collision-resistant. Recall that 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\}
  \leq
  \negl(\lambda)
\]

\item
  \textbf{Extra Credit [3 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}



\paragraph{Problem 5: 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}


\paragraph{Problem 6: Feedback [0 points].} Please answer the following questions to
help us design future problem sets. You are not required to answer these questions,
and if you would prefer to answer anonymously, please use this
\href{https://stanforduniversity.qualtrics.com/jfe/form/SV_6XTKIK2cWZyqpRr}{form}.
However, we do encourage you to provide us feedback on how to improve the course experience.
\begin{enumerate}[label=(\alph*), leftmargin=*]
  \item Roughly how long did you spend on this problem set?

  \item What was your favorite problem on this problem set?

  \item What was your least favorite problem on this problem set?

  \item Any other feedback for this problem set?
\end{enumerate}

\end{document}
