\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 2}
  \end{center}
\textbf{Due:}
Friday, 24 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
\vspace{0.7cm}
\noindent \textbf{Note:} The following two documents may help with number theory background on this assignment.
\begin{enumerate}
\item \url{https://crypto.stanford.edu/~dabo/cs255/handouts/numth1.pdf}
\item \url{https://crypto.stanford.edu/~dabo/cs255/handouts/numth2.pdf}
\end{enumerate}
\problem{Random Oracle Commitments [5 points]}

Let $H: \mathcal{M} \times \mathcal \mathcal{R} \to \mathcal{C}$
be a function
where $\mathcal{R}=\mathcal{C}=\zo^\lambda$.
%
Define $\Commit(m,r) = H(m,r)$.
%
Show that $\Commit$ is binding and hiding if $H$ is modeled as a random oracle.
\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}[b]
  \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_2$} }
            child { node[] {$x_3$} }
          }
        }
        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, 1^\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(1^\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{For each of the following statements, say whether it is TRUE or FALSE. Write \textit{at most one sentence} to justify your answer [7 points]}
\begin{enumerate}
  \item Let $p$, $q$, $r$, and $r'$ be distinct large primes.
Let $N = pqr$ and $N' = pqr'$.
Assume that there does \textit{not} exist an 
efficient (probabilistic polynomial time)
factoring algorithm. Say whether each of the following statements
are TRUE or FALSE.

\begin{enumerate}
  \item  There is an efficient algorithm that takes $N$ as input
    and outputs $r$.


  \item  There is an efficient algorithm that takes $N$ and $N'$ as input
    and outputs $r$.


  \item  There is an efficient algorithm that takes $N$ and $N'$ as input
    and outputs $q$.

\end{enumerate}

\item Let $\G$ be a group of prime order $q$. Consider the following special
cases of the discrete-log problem. For each of them, say TRUE if an efficient
(polynomial in $\log q$) algorithm for the special case can be used to construct
an efficient algorithm for the general case of the discrete-log problem, and
FALSE otherwise.
\begin{enumerate}
  \item An algorithm that correctly outputs the discrete log only when it is smaller than $q/\log q$.
  \item An algorithm that correctly outputs the discrete log only when it is smaller than $\log q$.
\end{enumerate}

\item Given $g\in\G$ and a positive integer $n$, a generic group algorithm
requires $\Omega(n)$ time to compute $g^{n}$.


\item Let $\G$ be a cyclic group of prime order $q$ with a generator $g\in\G$
and $H\colon\G\to\{1,2,3\}$ be a random function. A walk on $\G$
defined as $x_0\getsr \G$ and $x_{i+1}\gets x_i\cdot g^{H(x_{i})}$ collides in $O(\sqrt{q})$ steps in expectation (i.e., if
$i_{\textrm{col}}=\min\{i\in\N\colon \exists j<i\text{ s.t. } x_i=x_j\}$, then
$\Exp_{x_0,H}\left[i_{\textrm{col}}\right]\leq O(\sqrt{q})$).

\end{enumerate}

\problem{Generic Discrete Log [12 points]} 

You will need the ``Birthday Bound'' for these problems
(see Boneh-Shoup, Appendix B.1).
Let $\G = \langle g \rangle$ be a group of prime order $q$.
%Let $N=pq$ be an RSA modulus.

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

  \item Many times this quarter, we have mentioned that there
        is a algorithm for discrete log that runs in time
        $\tilde O(\sqrt q)$.\footnote{
        The big-$\tilde O$ and big-$\tilde \Omega$ notations are
         just like the normal big-$O$ and big-$\Omega$, except that
         they also suppress log factors. 
         So, a running time of $\sqrt{q} \cdot \log^4 q$ is $\tilde O(\sqrt q)$.
          }
        This algorithm, which is shockingly simple, is the
        best known algorithm for discrete-log in standard
        elliptic curve groups.

        You are given a discrete-log challenge $h = g^x \in \G$.
        Show that by computing two tables of values:
        one of the form $g^{r_i}$ for $r_i \getsr \Z_q$
        and one of the form $h^{s_j}$ for $s_j \getsr \Z_q$,
        you can recover the discrete log $x \in \Z_q$ in time
        $\tilde O(\sqrt q)$.

        This algorithm uses space $\tilde \Omega(\sqrt q)$.
        A clever trick, due to Pollard, gets the space
        usage down to $O(\poly \log q)$.

    \item The $B$-bounded discrete-log problem is
        the problem of recovering $x \in \{0, \dots, B\}$, given $g^x \in \G$. 
        That is, the group $\G$ is of order $q$, but we sample the exponent
        $x$ from a range of size $B \ll q$.
        Modify your algorithm of part (a) to solve
        the $B$-bounded discrete-log problem in time $\tilde O(\sqrt B)$.
\end{enumerate}

\problem{Factoring [10 points]} 
For this problem, let $p$ and $q$ be distinct large primes.
Remember that finding roots of polynomials over the reals is easy.
\begin{enumerate}[label=(\alph*), leftmargin=*]

  \item The best algorithm for factoring an 
    RSA modulus $N=pq$ is the general number field sieve (GNFS).
        This algorithm runs in time 
        \[ e^{\Omega( (\log N)^{1/3} \cdot (\log \log N)^{2/3})}.\]
        Compute the smallest integral constant $c \in \Z^+$ such that 
        an RSA modulus of $\lambda^c$ bits takes time 
        $\Omega(2^\lambda)$ to factor.
        
        \textit{Note:} The keys
        for standard elliptic-curve cryptosystems only need to 
        be $2\lambda$ bits long to guarantee $\Omega(2^\lambda)$
        security against the best known attacks. The answer to this question
        explains why elliptic-curve cryptosystems are much more
        popular than RSA today.

  \item Say that you are given an algorithm $\calA$ that takes as input
        $N=pq$ and outputs $p+q$. Show that you can use $\calA$ to factor $N$. 

  \item Let $f$ and $g$ be fixed/public 
        polynomials of constant degree with integral coefficients.
        In an attempt to shorten the size of your RSA secret key, 
        you compute an RSA modulus using the following algorithm:
        \begin{itemize}
          \item Choose a random $\poly(\lambda)$-bit integer $x$.
          \item If $f(x)$ and $g(x)$ are both primes, return
            $N = f(x) \cdot g(x)$.
          \item Else, restart.
        \end{itemize}
        Give an efficient algorithm that factors such a modulus $N$
        in polynomial time.
  
\end{enumerate}
\end{document}
