\documentclass[11pt]{article}
\usepackage{amssymb,amsmath,amsthm,url}
%uncomment to get hyperlinks
%\usepackage{hyperref}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Some macros (you can ignore everything until "end of macros")
\topmargin 0pt \advance \topmargin by -\headheight \advance
\topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt \evensidemargin \oddsidemargin \marginparwidth
0.5in
\textwidth 6.5in
%%%%%%
\newcommand{\getsr}{\gets_{\mbox{\tiny R}}}
\newcommand{\bits}{\{0,1\}}
\newcommand{\Ex}{\mathbb{E}}
\newcommand{\eqdef}{\stackrel{def}{=}}
\newcommand{\To}{\rightarrow}
\newcommand{\e}{\epsilon}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\indist}{\approx}
\newcommand{\dist}{\Delta}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\theoremstyle{definition}
\newtheorem{exercise}{Exercise}
\newtheorem{definition}{Definition}
\newcommand{\Adv}{\ensuremath{\mathsf{Adv}}}
\newcommand{\CSAT}{\ensuremath{\mathsf{CSAT}}}
\newcommand{\SAT}{\ensuremath{\mathsf{SAT}}}
\newcommand{\COL}{\ensuremath{\mathsf{3COL}}}
\newcommand{\cclass}[1]{\mathbf{#1}}
\renewcommand{\P}{\cclass{P}}
\newcommand{\NP}{\cclass{NP}}
\newcommand{\Time}{\cclass{Time}}
\newcommand{\BPP}{\cclass{BPP}}
\newcommand{\Enc}{\mathsf{E}}
\newcommand{\Dec}{\mathsf{D}}
\newcommand{\Gen}{\mathsf{G}}
\newcommand{\Sign}{\mathsf{Sign}}
\newcommand{\Ver}{\mathsf{Ver}}
\newcommand{\angles}[1]{\langle #1 \rangle}
\newcommand{\view}{\mathsf{view}}
\newcommand{\trans}{\mathsf{trans}}
% end of macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{Handout 9: Chosen Ciphertext Security}
\author{Boaz Barak}
\date{Total of 100 points. \\ Exercises due November 29th, 2005 1:30pm.}
\begin{document}
\maketitle
\begin{exercise}[Login protocol needs CCA - 50 points] Consider the following login protocol
mentioned in class:
\begin{itemize}
\item Client and server share secret $PIN$ chosen at random from $\bits^{\ell}$.
\item Client and server has public encryption key $e$ of server.
\item To login, client sends encryption of $PIN$ with key $e$ to server.
\item If $PIN$ is valid then server sends ``START'' message to client.
Otherwise it aborts.
\end{itemize}
\begin{enumerate}
\item Give an example for a CPA-secure public key encryption such that
if it is used in this protocol then the protocol is \emph{not}
secure: an active person-in-the-middle adversary can recover the
$PIN$ by intercepting $O(\ell)$ sessions.
\item Show that if the encryption scheme used is CCA secure
and an adversary can interact
with the client and server at most $m$ times, then its probability
of guessing the PIN is at most $O(\tfrac{m}{2^{\ell}})$.
\end{enumerate}
\end{exercise}
\begin{exercise}[Non malleability of CCA secure schemes - 50 points] An attractive
way to perform a bidding is the following: the seller publishes a
public key $e$. Each buyer sends through the net the encryption
$\Enc_e(x)$ of its bid, and then the seller will decrypt all of
these and award the product to the highest bidder.
One aspect of security we need from $\Enc(\cdot)$ is that given an
encryption $\Enc_e(x)$, it will be hard for someone not knowing $x$
to come up with $\Enc_e(x+1)$ (otherwise bidder B could always take
the bid of bidder A and make into a bid that is one dollar higher).
You'll show that this property is also related to CCA security:
\begin{enumerate}
\item Show a CPA-secure public key encryption such that there is an algorithm
that given $e$ and a ciphertext $y=\Enc_e(x)$, converts $y$ into a
ciphertext $y'$ that decrypts to $x+1$. (If it makes your life
easier, you can make the algorithm work only if $x$ is, say, a
multiple of $100$.)
\item Show that if $\Enc$ is CCA secure then there is no such algorithm. In particular
show that if $M$ is any polynomial time algorithm, and $X$ is a set
of possible numbers $x$, then
\[
\Pr_{(e,d) \gets \Gen(1^n)}[ \Dec_d(M(e,\Enc_e(x)))=x+1 ] <
\tfrac{1}{|X|} + n^{-\omega(1)}
\]
\end{enumerate}
\end{exercise}
\begin{exercise}[0 points] The proof for the CCA secure scheme given in class
was a bit handwavy. Go over the notes and make sure you understand
it. For double the points, go over the proof the OAEP+ scheme in
Shoup's paper (see link on website) and make sure you understand it.
For triple the points, do this for Boneh's scheme (see link on web
site).
\end{exercise}
\end{document}