\documentclass[11pt]{article}

\usepackage{
  latexsym,
  amsfonts,
  amssymb,
  amsthm,
  stmaryrd,
  pdfsync,
  graphicx,
  framed,
  empheq,
  physics,
}
\usepackage[hidelinks]{hyperref}
\usepackage{cleveref}
\usepackage[
  margin=1in,
]{geometry}

\theoremstyle{definition}

\newcommand{\hint}[1]{Hint: \emph{#1}}
\newcommand{\bit}{\{0,1\}}
\newcommand{\indist}{\overset{c}{\approx}}
\newcommand{\linked}{\diamond}
\newcommand{\lib}{\mathcal{L}}
\newcommand{\adv}{\mathcal{A}}

\newcommand{\word}[1]{\mathsf{#1}}
\newcommand{\many}[1]{\mathit{#1}}
\newcommand{\defn}{\ensuremath{\triangleq}}

\newcommand{\ensem}[2]{\left\{~#1~\left\lvert\begin{array}{l}#2\end{array}\right.\right\}}
\newcommand{\ensemline}[2]{\left\{~#1~\left\lvert~~#2~\right.\right\}}
\newcommand{\prob}[2]{\mathrm{Pr}\left[~#1~\left\lvert\begin{array}{l}#2\end{array}\right.\right]}
\newcommand{\probline}[2]{\mathrm{Pr}\left[~#1~\left\lvert~~#2~\right.\right]}

\newtheorem{problem}{Problem}
\newtheorem{definition}{Definition}
\newtheorem{solution}{Solution}

\title{CS/ECE407 Cryptography -- Homework 5\\
  Public Key Cryptography}
\author{}
\date{Due: Wednesday, May 6, 11:59PM CT}

\begin{document}

\maketitle

Remember, you are free to collaborate with up to one classmate.
See the course webpage for more details.
You are expected to write out and submit your own solutions!
Your collaboration is for discussing problems at a high level, not plagiarizing answers.

Your homework should be typed or carefully handwritten.
We provide a \LaTeX\ template for this document, if you would like to use it as a starting point.
\textbf{If we cannot read your handwritten answers, they will not receive credit.}

Your typed solutions should be submitted through gradescope (see course webpage).
Your hand-written solutions should be scanned and turned in through gradescope.

\pagebreak

\noindent
\begin{problem}[Certificates]
      Recall that a certificate is a document signed by some `certificate
      authority' (CA) that associates an identity with a public key.
      For instance, let $\many{sk}_C$ be the secret key of the CA.
      The following is a certificate associating Bob with some key $\many{pk}_B$:
      \[
        \many{Cert}_{C \rightarrow B} = \many{Sign}(\many{sk}_C, \text{``Bob's key is $\many{pk}_B$''})
      \]
      This problem involves \emph{certificate revocation}, where, for example,
      a CA might maintain a list of certificates that should no longer be trusted.
      In the following, you may assume that the CA wishes to revoke any
      certificate for which the secret key has been compromised.
  \begin{enumerate}
    \item
      \textbf{(2 points)}
      Suppose Bob's secret key is leaked in a data breach, and so now he would like the CA to revoke this certificate, so that others cannot forge messages on his behalf.
      Bob sends the following message to the CA:
      \[
        m = \text{``please revoke $\many{Cert}_{C \rightarrow B}$''}
      \]
      The CA calls Bob on the phone to verify Bob's identity using non-cryptographic mechanisms.
      Why does the CA need to verify Bob's identity before revoking his certificate?
    \item
      \textbf{(2 points)}
      Now, in addition to sending $m$, suppose that Bob also signs $m$ and sends the following signature to the CA:
      \[
        \sigma = \many{Sign}(\many{sk}_B, m)
      \]
      Does the CA still need to call and verify Bob's identity before revoking his certificate? Why/why not?
  \end{enumerate}
\end{problem}

\begin{problem}[RSA]
    Suppose $\many{Enc}', \many{Dec}'$ is a symmetric-key encryption scheme with CPA security where keys are uniformly sampled from $\bit^\lambda$.
    Recall that the RSA key generation algorithm outputs a triple $(N, e, d)$ such that:
    \[
      e \cdot d \equiv 1 \mod \phi(N)
    \]
    Let $H : \mathbb{Z}_N^* \rightarrow \{0,1\}^\lambda$ be a random oracle, and consider the following public-key encryption algorithm that uses RSA keys:
\begin{align*}
\boxed{
\begin{aligned}
  &\many{Enc}((N, e), m):\\
  &~~r \gets \mathbb{Z}_N^*\\
  &~~k = H(r)\\
  &~~\word{return}~(r^e \bmod N, \many{Enc}'(k, m))
\end{aligned}
}
\end{align*}
  \begin{enumerate}
    \item 
      \textbf{(2 points)}
      Specify a corresponding decryption algorithm:
\begin{align*}
\boxed{
\begin{aligned}
  &\many{Dec}((N, d), c):\\
  &~~...
\end{aligned}
}
\end{align*}
    \item
      \textbf{(2 points)}
      Prove that your decryption algorithm is correct.
    \item
      \textbf{(2 points)}
      Argue that your public key scheme is CPA secure, under the RSA assumption.
      Namely, argue why it is that an adversary that can win the CPA game must be able to break either the CPA security of the symmetric-key scheme, or the RSA assumption.
  \end{enumerate}
\end{problem}

\begin{problem}[CCA Security for Public-Key Schemes]
  In class we studied public-key schemes with CPA security.
  It is useful to also define \emph{CCA security} for public-key encryption schemes.
  Recall that in the symmetric-key setting, CCA security is related to
  \emph{malleability} -- namely the ability for the adversary to induce a
  change in a message by changing the encryption of that message.
  The same is true for public-key schemes, and the definition of CCA security is similar:
  \begin{definition}[Public Key Encryption Security against Chosen Ciphertext Attacks]
    Let $\Pi = (\many{KeyGen}, \many{Enc}, \many{Dec})$ denote a public-key encryption scheme.
    We define two helper procedures:
    \begin{align*}
      \many{Enc}_0(\many{pk}, m_0, m_1) &= \ensemline{c_0}{c_0 \gets \many{Enc}(\many{pk}, m_0)}\\
      \many{Enc}_1(\many{pk}, m_0, m_1) &= \ensemline{c_1}{c_1 \gets \many{Enc}(\many{pk}, m_1)}
    \end{align*}
    
    We say $\Pi$ achieves CCA security if the
    following ensembles are indistinguishable to any polytime adversary issuing \emph{legal queries} (discussed next):
    \begin{align*}
      &\ensem{
        (\many{pk}, \many{Dec}(\many{sk}, \cdot), \many{Enc}_0(\many{pk}, \cdot, \cdot))
      }{
        (\many{sk}, \many{pk}) \gets \many{KeyGen}(1^\lambda)
      }
      \approx
      \\
      &\ensem{
        (\many{pk}, \many{Dec}(\many{sk}, \cdot), \many{Enc}_1(\many{pk}, \cdot, \cdot))
      }{
        (\many{sk}, \many{pk}) \gets \many{KeyGen}(1^\lambda)
      }
    \end{align*}
    That is, the adversary is given the public key $\many{pk}$, as well as oracle access to decryption, and oracle access either to $\many{Enc}_0$ or $\many{Enc}_1$.
    The \emph{legal query} restriction states that the adversary may not pass any output obtained from its encryption oracle as input to its decryption oracle.
    \begin{enumerate}
      \item \textbf{(3 points)} Recall the ElGamal encryption scheme, which we discussed was CPA
        secure under the DDH assumption.
        Show that ElGamal is \emph{not} CCA secure.
      % \item CCA secure KEM?
      % \item No Authenticated notion?
    \end{enumerate}
  \end{definition}
\end{problem}

\end{document}
