\documentclass[11pt]{article}
\usepackage{amssymb,amsmath,amsthm,url}
\usepackage{graphicx}
\newif\ifpdf
\ifx\pdfoutput\undefined \else
\ifx\pdfoutput\relax
\else
\ifcase\pdfoutput
\else
\pdftrue
\fi
\fi
\fi
%uncomment to get hyperlinks
%\usepackage{hyperref}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Some macros (you can ignore everything until "end of macros")
\def\class{0}
\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{\To}{\rightarrow}
\newcommand{\e}{\epsilon}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\GF}{\mathsf{GF}}
\newcommand{\maxpr}{\text{\rm max-pr}}
\newcommand{\cclass}[1]{\mathbf{#1}}
\renewcommand{\P}{\cclass{P}}
\newcommand{\NP}{\cclass{NP}}
\newcommand{\PH}{\cclass{PH}}
\newcommand{\coNP}{\cclass{coNP}}
\newcommand{\AvgP}{\cclass{AvgP}}
\newcommand{\DTIME}{\cclass{DTIME}}
\newcommand{\BPP}{\cclass{BPP}}
\newcommand{\BQP}{\cclass{BQP}}
\newcommand{\NTIME}{\cclass{NTIME}}
\newcommand{\SIZE}{\cclass{SIZE}}
\newcommand{\Ppoly}{\cclass{P_{/poly}}}
\newcommand{\SPACE}{\cclass{SPACE}}
\newcommand{\PSPACE}{\cclass{PSPACE}}
\newcommand{\BPL}{\cclass{BPL}}
\newenvironment{summary}{\begin{quote}\textbf{Summary.}}{\end{quote}}
\newtheorem{theorem}{Theorem}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}{Claim}[theorem]
\theoremstyle{definition}
\newtheorem{exercise}{Exercise}
\newtheorem{definition}{Definition}
\newcommand{\sstart}{\triangleright}
\newcommand{\send}{\triangleleft}
\newcommand{\CSAT}{\ensuremath{\mathsf{CSAT}}}
\newcommand{\SAT}{\ensuremath{\mathsf{3SAT}}}
\newcommand{\IS}{\mathsf{INDSET}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\inp}{\mathsf{in}}
\newcommand{\outp}{\mathsf{out}}
\newcommand{\Adv}{\mathsf{Adv}}
\newcommand{\Supp}{\mathsf{Supp}}
\newcommand{\dist}{\Delta}
\newcommand{\indist}{\approx}
\newcommand{\PRG}{\mathsf{G}}
\newcommand{\Enc}{\mathsf{E}}
\newcommand{\Dec}{\mathsf{D}}
\newcommand{\Fcal}{\mathcal{F}}
\newcommand{\Gen}{\mathsf{Gen}}
\newcommand{\Sign}{\mathsf{Sign}}
\newcommand{\Ver}{\mathsf{Ver}}
\newcommand{\Com}{\mathsf{Com}}
\newcommand{\angles}[1]{\langle #1 \rangle}
\newcommand{\eqdef}{\stackrel{\text{\tiny def}}{=}}
\newcommand{\view}{\mathsf{view}}
\newcommand{\trans}{\mathsf{trans}}
\newcommand{\qstart}{q_{\text{\tiny start}}}
\newcommand{\qacc}{q_{\text{\tiny acc}}}
\newcommand{\qrej}{q_{\text{\tiny rej}}}
\newcommand{\csp}{\mathsf{CSP}}
\newcommand{\ared}{\text{\tt alph-red}}
\newcommand{\qred}{\text{\tt q-red}}
\newcommand{\dred}{\text{\tt deg-red}}
\newcommand{\amp}{\text{\tt gap-amp}}
\newcommand{\LC}{\mathcal{LC}}
\renewcommand{\H}{\mathcal{H}}
\newcommand{\iprod}[1]{\langle #1 \rangle}
\newcommand{\pmo}{\{\pm 1\}}
\newcommand{\set}[1]{\{ #1 \}}
% end of macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{COS 433 --- Cryptography --- Homework 8.}
\author{Boaz Barak}
\date{Total of 120 points. Due April 9, 2010.}
\begin{document}
\maketitle
\iffalse
\begin{exercise}[30 points]
Consider the following identification problem: there's a ``box''
that controls access to some resource (e.g., a door) and
authorized people are given some secret information that enables
them to use the resource, but unauthorized people cannot do so,
even if the know the contents of the box.
\begin{enumerate}
\item Consider the weakest security definition of this
problem where the only attack we're considering is an
adversary that ``listens in'' on conversations between
honest users and the box). Construct a non-interactive
(i.e., a protocol consisting of a single message from
the user to the box) protocol solving the identification
problem and prove its security.
\item Construct a non-interactive identification protocol
that remains secure under the stronger attack where an
adversary may open up the box and see the data it
contains, listen in on other conversations and also
construct ``fake boxes'' and have the authorized people
talk to these fake bozes. Prove the security for your
protocol. You may assume that all parties have access to
a perfectly synchronized global clock.
\end{enumerate}
\end{exercise}
\fi
\begin{exercise}[Random oracle security of hash and sign trapdoor - 30 points] Recall that in class
we considered the signature scheme that given a trapdoor function $f:\bits^n\To\bits^n$ and a hash function
$H:\bits^m\To\bits^n$, signs $x\in\bits^m$ with key $f^{-1}$ as $f^{-1}(H(x))$. We verify the signature $t$ on $x$ by
checking that $f(t) = H(x)$. Prove that for every polynomial-time $A$, if $H$ is chosen as a random function, and $A$
is given the key $f$, black-box access to $H$, and the signing function $x \mapsto f^{-1}(H(x))$ then $A$ wins the CMA
game with at most negligible probability. (Where $A$ wins the CMA game if it outputs $(x^*,t^*)$ such that
$t^*=f(H(x^*))$ but $x^*$ is not one of the queries made by $A$ to the signing function.)
\end{exercise}
\begin{exercise}[Non malleability of CCA secure schemes - 30 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 the following sense: that if $M$ is any
polynomial time algorithm, then
\[
\Pr_{\substack{(e,d) \gets \Gen(1^n)\\ X \getsr \{1,10^6\} }}[ \Dec_d(M(e,\Enc_e(x)))=x+1 ] <
10^{-6} + n^{-\omega(1)}
\]
\end{enumerate}
\end{exercise}
\newcommand{\Epubcca}{\Enc^{\text{\sf\tiny pub,cca}}}
\newcommand{\Epubcpa}{\Enc^{\text{\sf\tiny pub,cpa}}}
\newcommand{\Epriv}{\Enc^{\text{\sf\tiny priv,cca}}}
\begin{exercise}[Authenticated key exchange - 60 points]
Consider a key exchange protocol where the client has the public keys of a server, chooses a key $k \getsr\bits^n$ for
a private key scheme, interacts with the server, and at the end decides whether or not to accept the key as valid. For
simplicity we restrict ourselves to two-message protocols (one message from client to server and one message from
server to client). Consider the following attack on such protocols: (In this attack the adversary completely controls
the network between the client and server, so that all messages transmitted between them go through the adversary.)
\begin{enumerate}
\item Client sends the first message to the adversary.
\item Adversary gets a polynomial number of interactions with the server, in each such interaction the adversary
sends a message to the server. The server interprets the message as a first-message from some client, and it
either accepts a key $k$ as a result of this message and outputs the second message of the protocol or it
outputs ``invalid''. If the server accepted the key $k$, it also outputs $\Epriv_k(0^n)$. The adversary gets
the outputs of the server.
\item Adversary sends a message to the client.
\item If the client accepts the message and obtained a key $k$, then it chooses $b \getsr \{0,1\}$, and does the
following. If it accepted the key $k$ then the client outputs an encryption $\Epriv_k(0^n)$ if $b=0$, and
$\Epriv_k(1^n)$ if $b=1$. Otherwise it outputs ``invalid''.
\item The adversary outputs $b' \in \{0,1\}$. We say the adversary is \emph{successful} if both (i) the client
accepted the key and (ii) $b'=b$.
\end{enumerate}
We say the protocol is \emph{secure} if the probability the
adversary succeeds in this attack is at most $\tfrac{1}{2} +
n^{-\omega(1)}$.
\textbf{Notation:} We denote by $(\Sign,\Ver)$ a secure signature scheme. We denote by $\Epubcca$ a CCA secure public
key encryption scheme, by $\Epubcpa$ a CPA secure public key encryption scheme, and by $\Epriv$ a CCA secure private
key encryption scheme. The protocol is secure if it is secure for \emph{every} suitable choice of the underlying
schemes. In all cases we denote by $e$ and by $v$ the public encryption key and verification key of the server, and
assume that the client knows them.
For each of the following protocols, either prove that it is secure (for \emph{every} suitable choice of the schemes)
or give an example showing it is insecure (for \emph{some} choice of the schemes).
\noindent\textbf{Protocol 1:}
\begin{itemize}
\item Client chooses $k \getsr \bits^n$ and $m \getsr \bits^n$ and sends to server $\Epubcpa_e(k \circ m)$.
($\circ$ denotes string concatenation.)
\item Server decrypts ciphertext to get $k,m$, accepts the key $k$, and sends to client $m,\Sign_s(m)$ (if
ciphertext is invalid then server sends ``invalid'').
\item Clients verifies $m$ is the same string it sent before, verifies signature and if it passes verification, it
considers the key $k$ as valid.
\end{itemize}
\noindent\textbf{Protocol 2:} Same as Protocol~1 but with
$\Epubcca$ instead of $\Epubcpa$.
\iffalse \noindent\textbf{Protocol 3:}
\begin{itemize}
\item Client chooses $k \getsr \bits^n$, $k' \getsr \bits^n$
and $m \getsr \bits^n$ and sends to server $\Epubcpa_e(k
\circ k' \circ m)$.
\item Server decrypts ciphertext to get $k,k',m$ and sends
to client $y=\Epriv_{k'}(m)$ and $\Sign_s(y)$ (if
ciphertext is invalid then server sends ``invalid''.
\item Clients verifies signature and if it passes
verification and $y$ decrypts with $k'$ to the value
$m$, it considers the key $k$ as valid.
\end{itemize}
\fi
\noindent\textbf{Protocol 3:}
\begin{itemize}
\item Client chooses $k \getsr \bits^n$ and sends to server
$y=\Epubcpa_e(k)$.
\item Server decrypts ciphertext to get $k$, chooses $m\getsr \bits^n$ at random and sends to client $y$,$m$ and
$\Sign_s(y\circ m)$ (if ciphertext is invalid then server sends ``invalid'').
\item Client checks $y$ is the same message it sent before, verifies signature and if it passes verification, it
considers the key $k$ as valid.
\end{itemize}
\end{exercise}
\end{document}