\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 4}
  \end{center}
\textbf{Due:}
Friday, 22 May 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{Understanding Interactive Proofs [15 points]}
\textit{(Problems from ``The Foundations of Cryptography - Volume 1, Basic Techniques'' by Oded Goldreich)}

\begin{enumerate}[label=(\alph*), leftmargin=*]
  \item \textit{The role of verifier randomness:} Let $L$ be a language with a
  sound and complete
  interactive proof system where the verifier $V$ is deterministic. 
  Show that $L \in \classNP$.
  

  \item \textit{The role of prover randomness:} Let $L$ be a language with 
  a sound and complete
  interactive proof system. Show that there exists a
  sound and complete interactive proof 
  system for $L$ for which the prover $P$ is deterministic.\newline
  [\textbf{Hint:} Use the fact that $P$ is unbounded.]
  

  \item \textit{The role of errors:} Let $L$ be a language with a
   perfectly sound and complete interactive
  proof system, that is if $x \notin L$, the verifier 
  \emph{never} accepts (not even with negligible probability). 
  Show that $L \in \classNP$.


%\item \textbf{Research problem [+100 points].} 
%    Let $L$ be a language computable by a Turing Machine using time $T(n)$. 
%    Construct an interactive proof for $L$ in which the honest prover runs in 
%    time $\poly(T(n))$ and in which the verifier runs
%    in time $n \cdot \polylog(T(n))$. 

\end{enumerate}

\problem{Set Accumulators from Polynomial Commitments [8 pts]}

Cryptographic accumulators represent a data structure as a small digest in
such a way that operations over the data structure can be verified with
access to only the digest.
A \textit{set accumulator} over universe $\calU$ comprises five algorithms:
\begin{itemize}
  \item $\ms{Create}(S \subset \calU) \to d$:
    Creates a digest representing the set $S \subset \calU$.
  \item $\ms{ProveMem}(S \subset \calU, d, x \in S) \to \pi$:
    Creates a proof that $x \in S$.
  \item $\ms{VerifyMem}(d, x, \pi) \to \zo$:
    Verifies a proof that $x \in S$.
  \item $\ms{ProveNonMem}(S \subset \calU, d, x \notin S) \to \bar\pi$:
    Creates a proof that $x \notin S$.
  \item $\ms{VerifyNonMem}(d, x, \bar\pi) \to \zo$:
    Verifies a proof that $x \notin S$.
\end{itemize}

A set accumulator is
\textit{membership-secure}
if forging membership proofs for elements not in the set is hard.
Similarly, a set accumulator is
\textit{non-membership-secure}
if forging non-membership proofs for elements in the set is hard.
\unskip\footnote{
  In the literature, both properties are called ``collision resistance''.
  We avoid that name here to avoid a confusion with hash functions.
}
That is,
if for all efficient adversaries $\calA$,
the following probabilities are negligible in $\lambda$:
\[
  \Pr\left[
    \begin{array}[h]{l}
      (S, x, \pi) \gets \calA(\calU) \\
      d \gets \ms{Create}(S)
    \end{array}
    :
    \begin{array}[h]{c}
      x \notin S\ \land\\
      \ms{VerifyMem}(d, x, \pi) = 1
    \end{array}
  \right]
  \quad
  \Pr\left[
    \begin{array}[h]{l}
      (S, x, \bar\pi) \gets \calA(\calU) \\
      d \gets \ms{Create}(S)
    \end{array}
    :
    \begin{array}[h]{c}
      x \in S\ \land\\
      \ms{VerifyNonMem}(d, x, \bar\pi) = 1
    \end{array}
  \right]
\]

Using an evaluation-binding polynomial commitment scheme
(which may, or may not be the KZG scheme)
for polynomials over $\mathbb{F}$,
build a set accumulator for $\calU = \mathbb{F}$.
Assuming the underlying polynomial commitment scheme has constant-size
commitments and proofs,
your digest, membership and non-membership proofs should be constant-size too.
Prove that your accumulator is membership and non-membership secure,
assuming that the underlying polynomial commitment scheme is evaluation binding.

\textit{Hint: What set of values is naturally associated with a polynomial?}


\textbf{Extra Credit [2 points].}
 Now, assume that your accumulator construction is instantiated with the KZG
 polynomial commitment scheme.

 Show how one can compute the digest $d'$ of $S\cup\{y\}$ given the digest
 $d$ for $S$, and the secret exponent of the polynomial commitment scheme,
 $\alpha$. Your algorithm,
 \begin{itemize}
   \item $\ms{Update}(S, d, y) \to d'$:
     returns a digest $d'$ equal to $\ms{Create}(S\cup\{y\})$
 \end{itemize}
 should run in time independent of $|S|$,
 and you should show it is correct.

 Furthermore, show how one can compute a single update token, $u$,
 that allows any membership proof $\pi$ for some $x$
 which is valid with respect to $d$
 to be updated into a new membership proof $\pi'$ which is valid
 with respect to $d'$.
 That is, given two algorithms:
 \begin{itemize}
   \item $\ms{MakeToken}(S, d, y) \to u$:
     creates update token $u$ for membership proofs with respect to $d$
   \item $\ms{UpdateProof}(d, x, \pi, u) \to \pi'$:
     creates a new proof $\pi'$ which is valid with respect to $d'$
 \end{itemize}
 and show that these algorithms produce a valid $\pi'$.
 \unskip{\footnote{
     Note:
     Some accumulator constructions do not allow for the efficient update
     algorithms that this sub-problem requires.
     %
     You may need to modify your accumulator so that it does allow for efficient
     updates.
 }}

\problem{Garbled Circuits are not maliciously secure [10 points]}

Suppose that
Alice has bit $x$,
Bob has bit $y$, and they use Yao's GC protocol to compute $z = \text{AND}(x, y)$.

\begin{enumerate}[label=(\alph*), leftmargin=*]
\item
  (True/False, no explanation):
  If Alice's bit is 1,
  and all parties follow the protocol,
  then afterwards Alice can tell whether Bob's bit is 0 or 1.
\item
  (True/False, no explanation):
  If Alice's bit is 0,
  and all parties follow the protocol,
  then afterwards Alice can tell whether Bob's bit is 0 or 1.
\item
  Suppose that Alice has bit 0
  and plays the role of the garbler.
  %
  Show that by incorrectly garbling the circuit,
  and by observing the response of Bob (who is following the protocol),
  Alice can learn Bob's bit.
  %
  Explicitly describe how Alice's attack works,
  and
  informally explain why Bob cannot detect that Alice
  has deviated from the protocol.
  %
  In your attack, Alice \textit{must} participate honestly
  in the OT protocol.
\end{enumerate}


\problem{Extending Oblivious Transfers [15 points]} 
Oblivious transfer (OT) is an important building block of many secure MPC
protocols. Because OT requires public-key cryptography, implementing a large
number of OTs can be very expensive in practice. In this problem, we will show
how we can realize $n = \poly(\lambda)$ instances of 1-out-of-2 OTs on
$\ell$-bit strings (where $\ell = \poly(\lambda)$) using just $\lambda$
instances of 1-out-of-2 OTs on $\lambda$-bit strings. Here, $\lambda \in \N$ is
a security parameter. This means that we can essentially obtain an {\em
arbitrary} polynomial number of OTs using a fixed number of {\em base OTs}.
\begin{enumerate}[label=(\alph*), leftmargin=*]
  \item First, we show how to realize $n$ instances of 1-out-of-2 OTs on $\ell$-bit
  strings using $\lambda$ instances of 1-out-of-2 OTs on $n$-bit strings (we refer to
  these as the {\em base OTs}). Consider the following protocol:
  \begin{itemize}[leftmargin=*]
    \item Let $r \in \zo^n$ be the receiver's choice bits for the $n$
    OT instances, let $\big( m^{(1)}_0, m^{(1)}_1 \big), \ldots, \big( m^{(n)}_0, m^{(n)}_1 \big)$
    be the sender's messages for the $n$ OT instances.

    \item The receiver begins by choosing a matrix $\boldM \getsr \zo^{n \times \lambda}$.
    The sender chooses a random string $s \getsr \zo^\lambda$.

    \item The sender and the receiver now perform $\lambda$ instances of
    an 1-out-of-2 OT on $n$-bit strings, but with their roles swapped
    (namely, the sender plays the role of the receiver in the base OTs, and
    vice versa). In the $\ord{i}$ base OT (where $i \in [\lambda]$), the
    sender provides $s_i$ as its choice bit and the receiver provides
    $(\boldM_i, \boldM_i \oplus r)$ as its two messages, where
    $\boldM_i \in \zo^n$ denotes the $\ord{i}$ column of $\boldM$.

    \item Let $\boldT \in \zo^{n \times \lambda}$ be the matrix the sender receives
    from these base OTs (where the $\ord{i}$ column of $\boldT$ is the column
    it received from the $\ord{i}$ base OT). By construction, either $\boldT_i = \boldM_i$ or
    $\boldT_i = \boldM_i \oplus r$.
  \end{itemize}
  For $j \in [n]$, let $\boldM^{(j)}$ denote the $\ord{j}$ row of $\boldM$ and let
  $\boldT^{(j)}$ denote the $\ord{j}$ row of $\boldT$. Write down an expression
  for $\boldM^{(j)}$ in terms of $\boldT^{(j)}$ and $s$ when $r_j = 0$ and when $r_j = 1$.

  \item Let $H \colon [n] \times \zo^\lambda \to \zo^\ell$ be a hash function (modeled
  as a random oracle). Suppose the sender encrypts each pair of messages
  $\big( m^{(j)}_0, m^{(j)}_1 \big)$ by computing
  \[ \ct^{(j)}_0 \gets m^{(j)}_0 \oplus H\big( j, k^{(j)}_0 \big) \quad \text{and} \quad
     \ct^{(j)}_1 \gets m^{(j)}_1 \oplus H\big( j, k^{(j)}_1 \big), \]
  where $k^{(j)}_0, k^{(j)}_1 \in \zo^\lambda$. The sender sends each pair of
  encrypted messages to the receiver. Write down expressions for
  $k^{(j)}_0, k^{(j)}_1$ that would enable the receiver to learn $m^{(j)}_{r_j}$. 
  [\textbf{Hint:} Recall that the receiver chooses the matrix $\boldM$ and 
  then use the result from Part~(a).]

  \item Give a brief explanation of why the receiver learns nothing about
  the other message $m^{(j)}_{1 - r_j}$.
  [\textbf{Hint:} Use the fact that $H$ is modeled as a random oracle.]

  \item Give a brief explanation of what goes wrong if we implement the hash function
  $H(j, k)$ as $F(k, j)$, where $F \colon \zo^\lambda \times [n] \to \zo^\ell$ is a secure PRF.

  \item Describe how you would modify the above protocol so that the base OTs are
  performed over $\lambda$-bit strings rather than $n = \poly(\lambda)$-bit strings.
  [\textbf{Hint:} You will need to introduce a computational assumption.]
\end{enumerate}

\problem{Secret Sharing and Polynomials [10 points.]}
Let $\F$ be a finite field.  (If it's helpful, you can think of $\F$ as the set
of integers modulo a prime $p$.)

\medskip

\noindent While working late into the night on your CS355 problem set, you miraculously 
discover a polynomial-time factoring algorithm! 
To safeguard your algorithm, you express it as a message $m \in \F$,
and split it into $n$ shares using
the \textit{additive} secret-sharing scheme we saw in lecture.
You give one share $s_i$ to each of your $n$ friends 
(for $n \ll |\F|$)
and then you spend many hours watching mind-numbing Netflix shows to erase the algorithm
from your memory.

\medskip

\noindent Later on, when you want to recover your secret message/algorithm $m$, you call your
friends over to your dorm room. You ask each friend $i \in [n]$ to
announce their share $s_i \in \F$ one at a time.
Given these shares, you and your friends
can all use the reconstruction algorithm to recover $m \in \F$.

\begin{enumerate}[label=(\alph*), leftmargin=*]

  \item In the setting described above, each friend $i \in [n]$ announces 
      their share $s_i$ one at a time.
      Unfortunately, you are unlucky and the last friend to announce their share is
      not your friend, but is actually a frenemy. 
      Show that by deviating from the specified protocol, the frenemy
      can broadcast a malformed share $s'_n \neq s_n$ that will
      cause you to recover a message $m' \neq m \in \F$, for any
      message $m'$ of the frenemy's choosing.
      

  \item One (ineffective) way to prevent the attack would be to require all of your friends
      to announce their shares simultaneously.
      Show that the frenemy can still cause you to recover the incorrect
      message $m' = m + \Delta \in \F$, for any $\Delta \in \F$ of the frenemy's
      choosing.


  \ignore{
    \item To protect yourself against frenemies, you instead take multiple
    precautions:
      \begin{itemize}
        \item You require all of your friends to announce their shares at once.
        \item You use $n$-out-of-$n$ Shamir secret sharing.
        \item You encode your algorithm as a message $m \in S \subset \F$.
      \end{itemize}
        Show that in this case, if frenemy $i$ announces an invalid share $s_i
        \neq s'_i$, you will detect this with probability at least $1 -
        |S|/|\F|$.
  }

 \item You come up with an improved factoring algorithm that is too complicated
       to describe in a single element $m \in \F$. Show how you can extend
       Shamir secret sharing to share an element $\vec m = (m_1, \dots, m_\ell) \in \F^{\ell}$
       such that:
       \begin{itemize}
       \item Each friend gets a share consisting of a \textit{single} element of $\F$.
       \item Seeing any $n - \ell$ shares leaks nothing about $\vec m$ (so you are protected
             against coalitions of $n-\ell$ frenemies who want to steal your algorithm).
       \item All $n$ friends can recover the entire secret message $\vec m$.
       \end{itemize}
       You may assume that $n + 2\ell < \abs{\F}$.


 \item \textbf{Extra Credit [5 points].} So far we have assumed
    that the number of friends $n$ is much smaller than the size of the
    field $\F$ (i.e., we have been working modulo a prime $p \gg n$).
    Construct a $t$-out-of-$n$ secret-sharing scheme that works when $|\F| < n$
    such that the shares have size $\poly(|\F|, \log n)$.
    If it's helpful, you may assume that $n \ll |\F|^2$
    and have a scheme that works only for some subset of the values
    $t \in [n]$.
    There are many possible solutions to this problem, so feel free to
    be creative.

\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 the anonymous feedback form available on the course website.
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}
