\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 2026}  \
  \begin{center} 
    {\Large Problem Set 1}
  \end{center}
\textbf{Due:}
Friday, 10 April 2026 (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://cs355.stanford.edu/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{X85KN6} 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{A Special PRF [10 points]}
One can show that $F(k,x)=H(x)^k$
is a PRF,
if $H$ is modeled as a random oracle to a group where the discrete logarithm problem is hard (We will discuss the random oracle model in Lecture 4, but you do not need to know what they are for this problem).
%
This PRF has many special 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).\] 
 
  Let us consider a PRF defined over $(\calK = \Z_p,+)$ with group operation addition and $(\calY = G , \otimes)$ where $G$ is a group of prime order $p$. 
  Is the PRF $F(k,x)=H(x)^k$ defined with a random oracle $H:\calX\to G$ a key-homomorphic PRF? Please prove your answer one way or the other (you only need to prove key-homomorphism, and do not need to prove whether it is a secure PRF).
  

  \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'$.
  Prove that your protocol is correct (you need not prove security).
  
  
  \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$.
  Prove that your protocol is correct (you need not prove security).
    
\end{enumerate}
\problem{True/False [7 points]}
Note: Please give a short explanation with your answers.
\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 function.
        % Alex and Wilson could not get a working proof.
		\item[iii] $f_{x=0}(k)\deq F(k,0)$ is (always) a one way permutation.
  \end{enumerate}
\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. Prove that $F_1$ indeed has both of these properties.
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{Composition [10 points]}
Determine whether each of the following statements is TRUE or FALSE.
%
For the first two statements, prove that your answer is correct.
%
That is, give a security proof or describe an adversary and prove it
has high advantage.

Let $F(k,x) \to y$ be a PRF,
and $f(x) \to y$ be a OWF,
and let $G(s) \to r$ be a PRG.
%
Assume that the PRF outputs fixed-length bit-strings.

\begin{enumerate}
\item
  The function $F_1(k, (x_1, x_2)) = F(k, x_1) \oplus F(k, x_2)$ is a PRF
\item
  The function $F_2((k_1, k_2), x) = F(k_1, x) \oplus F(k_2, x)$ is a PRF
\item
  The function $G_3(s) = (G(s), G(s))$ is a PRG
\item
  The function $G_4((s_1, s_2)) = (s_1, G(s_2))$ is a PRG (where $s_1, s_2 \in \mathcal{S}$: the seed space for $G$)
\item
  The function $f_5((x_1, x_2)) = (f(x_1), f(x_2))$ is a OWF
\end{enumerate}
\begin{problem}{Time Spent [1 point for answering]}
   How long did you spend on this problem set? This is for calibration purposes, and the response you provide will not affect your score.
\end{problem}
\paragraph{Optional Feedback [0 points].} Please answer the following questions to
help us design future problem sets. You do not need to answer these questions,
and if you would prefer to answer anonymously, please use this
\href{https://forms.gle/M1dQ6EoiuyawCbvr5}{form}.
However, we do encourage you to provide us feedback on how to improve the course experience.
\begin{enumerate}[label=(\alph*), leftmargin=*]

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

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

  \item Do you have any other feedback for this problem set?

  \item Do you have any other feedback on the course so far?

\end{enumerate}
\end{document}
