\documentclass[11pt]{article}

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

\usepackage{chngcntr}
%\counterwithin*{equation}{section}
\newtheorem*{defn*}{Definition}

\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 2}
  \end{center}
  {\bf Due:} April 26, 2021 at 11:59pm
\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}. 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.

\medskip

\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}

\hrule

\begin{problem}{Conceptual Questions [10 points]}



For each of the following statements, say whether it is 
TRUE or FALSE. Write \textit{at most one sentence} to justify
your answer.

\begin{enumerate}[label=(\alph*), leftmargin=*]
    \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}[label=\roman*]
      \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}
    
    \ignore{\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}[i]
      \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 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})$).

  \item Let $e: \G\times\G \to \G_T$ be a pairing for an elliptic curve group $\G$. If the discrete log problem in $\G$ is easy, then the BDDH problem for $e$ is easy as well.


\end{enumerate}
\end{problem}

\begin{problem}{Coppersmith Attacks on RSA [15 points]}

In this problem, we will explore what are known as ``Coppersmith''
attacks on RSA-style cryptosystems.
As you will see, these attacks are very powerful and very general.
We will use the following theorem: 

\begin{framed}
\noindent
\begin{minipage}{\textwidth}
    \begin{theorems}[Coppersmith, Howgrave-Graham, May]
      Let $N$ be an integer of unknown factorization.
      Let $p$ be a divisor of $N$ such that 
      $p \geq N^\beta$ for some constant $0 < \beta \leq 1$.
      Let $f \in \Z_N[x]$ be a monic polynomial of degree $\delta$.
      Then there is an efficient algorithm that outputs all integers $x$
      such that 
      \[f(x) = 0 \bmod p \qquad \text{and}\qquad |x| \leq N^{\beta^2 / \delta}.\]
      Here $|x| \leq B$ indicates that
      $x \in \{-B, \dots, -1, 0, 1, \dots, B\}$.
    \end{theorems}
\end{minipage}
\end{framed}
\noindent In the statement of the theorem,
when we write $f \in \Z_N[x]$, 
we mean that $f$ is a polynomial 
in an indeterminate $x$ with coefficients
in $\Z_N$.
A \textit{monic} polynomial is one whose leading coefficient
is $1$.

\medskip

\noindent When $N=pq$ is an RSA modulus
(where $p$ and $q$ are random primes of equal bit-length
with $p > q$), the interesting
instantiations of the theorem have either $\beta = 1/2$
(i.e., we are looking for solutions modulo a prime factor of $N$)
or $\beta = 1$ (i.e., we are looking for small solutions modulo $N$).

\medskip

\newcommand{\Frsa}{F_\text{RSA}}
\newcommand{\SHA}{\textsc{sha}}
\noindent For this problem, let $N$ be an RSA modulus 
with $\gcd(\phi(N), 3) = 1$ and
let $\Frsa(m) \deq m^3 \pmod N$ be the RSA one-way function.

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

  \item Let $n = \lceil \log_2 N \rceil$. Show that you can factor an RSA modulus $N = pq$ if you are
        given:
        \begin{itemize}
          \item the low-order $n/3$ bits of $p$, 
          \item the high-order $n/3$ bits of $p$, or
          \item the high-end $n/6$ bits of $p$ \textit{and}
                the low-end $n/6$ bits of $p$.
        \end{itemize}

        %\textbf{Extra credit [5 points].} Show that if you are given
        %    the middle $n/3$ bits of $p$ you can also factor $N$.

  \item In the dark ages of cryptography, 
    people would encrypt messages directly using
    $\Frsa$. 
    That is, they would encrypt an arbitrary bitstring $m \in \zo^{\lfloor\log_2 N\rfloor/5}$ by 
    \begin{itemize}
      \item setting $M \gets 2^\ell +  m$ for some integer $\ell$ 
        to make $N/2 \leq M < N$, and
      \item computing the ciphertext as $c \gets \Frsa(M)$.
    \end{itemize}
    (Note that the first step corresponds to padding the message $M$
    by prepending it with a binary string 
    ``$10000\cdots000$.'')

    Show that this public-key encryption scheme is very broken.
    In particular, 
    give an efficient algorithm that takes as input
    $(N, c)$ and outputs $m$.

  \item To avoid the problem with the padding scheme above, your
      friend proposes instead encrypting the short message
      $m \in \zo^{\lfloor\log_2 N\rfloor/5}$ by setting
      $M \gets (m \| m \|m \|m \|m) \in \zo^{\lfloor\log_2 N\rfloor}$
      and outputting $c \gets \Frsa(M)$.
      Show that this ``fix'' is still broken.

  \item The RSA-FDH signature scheme uses a hash function $H: \zo^* \to \Z_N$.
      The signature on a message $m\in \zo^*$ is the value
      $\sigma \gets \Frsa^{-1}(H(m)) \in \Z_N$.
      The signature $\sigma$ is 
      $n = \lceil \log_2 N \rceil$ bits long.
      Show that the signer need only output signatures of $2n/3$ bits
      while still 
      \begin{itemize}
        \item retaining exactly the same level of security (i.e., using
          the same size modulus), and
        \item having the verifier run in polynomial time.\footnote{
      We don't use this optimization in practice since 
      (1) Schnorr signatures are so much shorter and
      (2) the verification time here is polynomial, but still
          much larger than the normal RSA-FDH verification time.
          Still, it's a cool trick to know.}
      \end{itemize}

\end{enumerate}

\end{problem}


\problem{On The Importance of Elliptic-Curve Point Validation [10 points]}
In this problem, we will see that all parties in a cryptographic protocol must verify that adversarially chosen points are on the right curve, and failing to do so may break security. We exemplify this by considering a
variant of elliptic-curve Diffie-Hellman key exchange in which the server uses
the same key pair across multiple sessions. More specifically, 
let $E\colon y^2=x^3+Ax+B$ be an elliptic curve over $\F_p$, where $q\coloneqq
|E(\F_p)|$ is a prime number and $P\in E(\F_p)$ is a generator. 
The server holds
a \emph{fixed} secret key $\alpha\getsr\Z_q$ and advertises (e.g., in its TLS
certificate) the corresponding fixed public key $\alpha P\in E(\F_p)$. A client
connects to the server by choosing $\beta\getsr\Z_q$, computing $V=\beta P$, and
sending $V$ to the server. Both sides then compute the shared secret $W=\alpha\beta P$. For simplicity, we assume that the server then sends the
message $E_s(W,\text{``Hello!''})$ to the client, where $(E_s,D_s)$ is some
symmetric cipher.

\ignore{One pitfall in this setting (and in elliptic-curve cryptography in general) is
that the server must check that the point $V=(x_0,y_0)$ it receives from the
client is in fact on the curve $E(\F_p)$ (i.e., that $y_0^2=x_0^3+Ax_0+B \pmod p$).
Skipping this check can be devastating because the elliptic-curve group addition law is independent of the parameter $B$ of the curve equation.\footnote{We have seen this in class for $P\boxplus Q$ when $Q\neq P,-P$, and it holds in general as well.}
More specifically, a malicious client can send any point $V_1=(x_1,y_1)\in\F_p^2$, and for every such point, there exists $\hat B\in \F_p$ such that $V_1$ is a point on the curve $E_1\colon y^2=x^3+Ax+B_1$. If the server computes $\alpha V_1$ using the group law for $E(\F_p)$ without first checking that $V_1\in E(\F_p)$, the resulting point $\alpha V_1$ will be on the attacker's curve $E_1$ rather than on $E$.
}

\begin{enumerate}[label=(\alph*), leftmargin=*]
  \ignore{
    \item Warmup: the finite-field case. Here $\G\subseteq \F_p^*$ is a group of prime order $q$, $g$ is a generator of $\G$, and all group elements $g,u,v,w\in\G$  are represented as integers $\bmod p$. When the server receives from the client the integer $v\in[0,p-1]$, it computes the shared secret $w$ as $w\gets v^\alpha\bmod p$. Show that a malicious client that sends to the server the integer $\hat v = p-1$, can learn one bit of the server's fixed secret key $\alpha$. 
   }
  \item Explain how the server can check that the point $V$ it receives from the client is indeed in $E(\F_p)$.
  
\end{enumerate}

\noindent
  %Observe that 
  The
  elliptic-curve group addition formulae are \emph{independent of the parameter $B$} of
  the curve equation. In particular, for every curve $\hat E \colon y^2=x^3+Ax+\hat B$ for some
  $\hat B\in \F_p$, applying the formulae for addition in $E(\F_p)$ to any two
  points $\hat V,\hat W\in \hat E(\F_p)$ gives the point $\hat V\boxplus \hat W
  \in \hat E(\F_p)$.
  

\begin{enumerate}[label=(\alph*), leftmargin=*]
  \setcounter{enumi}{1}
  \item\label{ecpart1} Suppose there exists a curve $\hat E \colon
  y^2=x^3+Ax+\hat B$ such that $|\hat E(\F_p)|$ is divisible by a small prime
  $t$ (i.e., $t=O(\polylog(q))$). Show that if the server \emph{does not check}
  that $V\in E(\F_p)$, a malicious client can efficiently learn $\alpha
  \bmod{t}$. You may assume one can efficiently find a point of order $t$ in
  $\hat E(\F_p)$.
  \item Use Part~\ref{ecpart1} to show how a malicious client can efficiently learn the secret key $\alpha$, if the server \emph{does not check} that $V\in E(\F_p)$. You may assume that if $\hat B\getsr \F_p$, then $|\hat E(\F_p)|$ is uniform in $\left[p+1-2\sqrt p, p+1+2\sqrt p\right]$ and is efficiently computable. (As in Part~\ref{ecpart1}, you may assume that whenever the order of a curve has a small prime factor $t$, one can efficiently find a point of order $t$ on that curve.)
\end{enumerate}


\problem{Somewhat-homomorphic encryption from pairings~[10 points]} 
In this problem, you will construct a ``somewhat homomorphic'' public-key
encryption scheme: it allows computing any number of additions and a single
multiplication. 
Let $\G_1$ be a cyclic group of prime order $p$ and $g\in\G_1$ be a generator of
the group. 
Consider the following two algorithms:

\setlist[description]{font=\normalfont}
\begin{description}
  \item[$\ms{Gen}(g)\to (\pk, \sk)$]: Choose random $a,b,c\getsr \Z_p$ such that $c\neq ab\Mod{p}$. Set $g_a=g^a$, $g_b=g^b$, and $g_c=g^c$. Output the public key $\pk = (g, g_a, g_b, g_c)$ and the secret key $\sk=(a,b,c)$.
  \item[$\ms{Enc}(\pk=(g,g_a,g_b,g_c), m)\to \ct$]: Given a message $m\in\Z_p$, choose $r\getsr \Z_p$ and output $\ct=(g^mg_a^r, g_b^mg_c^r)$.
\end{description}

\begin{enumerate}[label=(\alph*), leftmargin=*]
\item\label{part:decrypt} Give a $\textsf{Dec}$ algorithm that takes a secret key $\sk$ and a  ciphertext $\ct=(u,v)$ and outputs $m$. Your algorithm needs to be efficient only if the message $m$ lies in some known small space (say $0\leq m< B$ as an integer, for some bound $B=O(\polylog(p))$).
\item Give an algorithm $\ms{Add}(\pk, \ct,\ct')\to \ct_{\textrm{sum}}$ that takes as input two ciphertexts $\ct$ and $\ct'$, that are encryptions of $m,m'\in\Z_p$ respectively, and outputs an encryption of $m+m' \bmod{p}$.
\end{enumerate}

Now let $\G_2, \G_T$ be two other cyclic groups of order $p$ (i.e.,
$|\G_1|=|\G_2|=|\G_T|$), $e\colon \G_1\times\G_2\to \G_T$ be a pairing, and
$h\in\G_2$ and $e(g,h)\in\G_T$ be generators of $\G_2$ and $\G_T$ respectively.
Furthermore, let $(\pk',\sk')\leftarrow \ms{Gen}(h)$ be the public and secret
keys obtained by running $\ms{Gen}$ using the group $\G_2$. Consider now the
following algorithm:

\begin{description}
  \item[$\ms{Mult}(\ct,\ct')$]: On input two ciphertexts $\ct=(u,v)\leftarrow \ms{Enc}(\pk, m)$ and $\ct'=(u',v')\leftarrow \ms{Enc}(\pk', m')$, output the tuple $(w_1,w_2,w_3,w_4)\in\G_T^4$ where
\begin{equation*} \label{q4:cond}
w_1=e(u,u'),\quad w_2=e(u,v'),\quad w_3=e(v,u'),\quad w_4=e(v,v') \,.
\end{equation*}
\end{description}

\begin{enumerate}[label=(\alph*), leftmargin=*,resume]
\item Let $\alpha_1,\dotsc,\alpha_4\in\Z_q$ such that $w_i=e(g,h)^{\alpha_i}$ (i.e., $\alpha_i$ is the discrete log of $w_i$ in $\G_T$).
Show that ${m\cdot m'\bmod{p}}$ can be expressed as a \emph{linear function} $\sum_{i=1}^4C_i\alpha_i$, where the coefficients $C_i$ depend only on the secret keys. (You \emph{need not} give an explicit formula for the coefficients $C_i$.)
\item Show how to efficiently recover $m\cdot m'\bmod{p}$ from $w_1,\dotsc,w_4$ and the two secret keys $\sk$ and $\sk'$.  As in Part~\ref{part:decrypt}, you can assume that the messages $m,m'$ lie in some known small space.
\item \textbf{Extra credit [3 points].} Show that if the DDH assumption holds in $\G_1$ then $\calE=(\textsf{Gen}, \textsf{Enc}, \textsf{Dec})$ is a semantically secure public-key encryption scheme. 

\end{enumerate}


  
\begin{problem}{Time Spent [3 points 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://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 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}
