\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{amsmath}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{fact}[theorem]{Fact}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{assumption}[theorem]{Assumption}

\newcommand{\qed}{\hfill \ensuremath{\Box}}

\newenvironment{proof}{
\vspace*{-\parskip}\noindent\textit{Proof.}}{$\qed$

\medskip
}

\newcommand{\alg}[1]{\mathsf{#1}}
\newcommand{\Prover}{\alg{P}}
\newcommand{\Verifier}{\alg{V}}
\newcommand{\Simulator}{\alg{S}}
\newcommand{\PPT}{\alg{PPT}}
\newcommand{\isom}{\cong}
\newcommand{\from}{\stackrel{\scriptstyle R}{\leftarrow}}
\newcommand{\handout}[5]{
   \renewcommand{\thepage}{#1-\arabic{page}}
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { {\bf CS395T Advanced Cryptography} \hfill #2 }
       \vspace{4mm}
       \hbox to 5.78in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\ho}[5]{\handout{#1}{#2}{Instructor:
#3}{Scribe: #4}{Lecture #1: #5}}
\newcommand{\al}{\alpha}
\newcommand{\Z}{\mathbb Z}

\begin{document}
\ho{9}{2/17/2009}{Brent Waters} {Vishvas Vasuki} {CCA security}

\section{Semantic security against CCA}
\subsection{Motivation}
Chosen cyphertext attacks (CCA) are a realistic possibility. Consider the following scenarios.

Suppose that A and B are exchanging embarassing Valentines day messages using a public key cryptosystem. C can intercept a cyphertext c from A to B, mangle it to get cyphertext $c' = Enc(m', r)$ and send it to B. B, mystified by the message $m'$ he got from C, contacts him with $m'$ and asks him what is going on. In such ways, C can concievably choose cyphertexts and get them decrypted.

If the cryptosystem being used by A and B is vulnerable to such attacks, it is possible that, C will be able to deduce the content of the messages being sent by A to B.

\subsection{The formal notion of security from CCA}
The notion of semantic security of a public key cryptosystem against CCA can be specified by a game similar to the CPA security definition. The new security game is identical to the CPA game (described in previous scribe notes), except that the attacker can now make a polynomial number of decryption requests in two phases. The first phase occurs before the challenger challenges the attacker by supplying a cyphertext c; and the second phase occurs after this event. In the first phase, the attacker may request the decryption of any abritrary cyphertext; but in the second phase, he may not ask for the decryption of the challenge cyphertext c.

It is possible that the cyphertext the attacker asks to decrypt is not in the space of valid cyphertexts, in which case, the challenger responds with the message 'invalid', denoted by $\perp$.

\section{Vulnerability of ElGamal cryptosystem under CCA}
Consider the ElGamal cryptosystem, which was discussed in previous scribe notes. Note that the challenge cyphertext is of the form $Enc(m, r) = (c_{1}, c_{2})$, where $c_{1} = g^{r},\ c_{2} = g^{ry}m$, where r and y are unknown to the attacker. Given this, an attacker can pick a random number r' and generate the cyphertext $c_{1}' = g^{r + r'},\ c_{2}' = g^{(r+r')y}m$, as the values g and $g^{y}$ are known. The attacker can then query for the decryption of this modified cyphertext and receive the message m as answer. Thus, the ElGamal cryptosystem is vulnerable to CCA.

A stronger attack may be mounted by picking a random value h and querying for the decryption of cyphertext $c_{1}' = g^{r + r'},\ c_{2}' = g^{(r+r')y}mh$. Upon receiving a reply mh, the attacker can then distinguish $m_{0}h$ from $m_{1}h$. This attacker is stronger as it works even against challengers who might refuse to send the challenge plaintext m to the attacker.

\section{Making a CCA secure scheme from a secure IBE scheme}
We now show a generic way to build a CCA secure public key cryptography scheme from a secure IBE scheme.

Consider an IBE system with public parameters PP and a master secret key MSK.

\subsection{A first attempt}
Consider the scheme defined by the algorithms below:

\begin{itemize}
 \item Setup(l): PK = PP. SK = MSK.
 \item Enc(m): Choose a random id, find $C_{1} = Enc_{IBE}(PP,ID,m)$, then compose the cyphertext $CT = C_{1}, ID$.
 \item Dec(CT): Decompose CT into $C_{1}$ and ID, then get $Keygen(MSK, ID) = SK_{id}$; then do $Dec_{IBE}(C_{1}, SK_{id}) = m$ to get the plaintext.
\end{itemize}

Now we attempt to show that this algorithm is CCA secure by showing that a successful CCA attacker can be used to construct an attacker for the supposedly secure IBE scheme. Let A be the IBE challenger, B the IBE attacker/ CCA challenger, and C the CCA attacker.

Initially, the IBE system in A is setup. A announces PP to B. B communicates the public key PK = PP to C. C can make decryption requests in two phases. Whenever C makes a decryption request, the Dec algorithm described above is used to answer it. At some point B chooses $ID^{*}$ from the ID's which were not involved in a decryption request in the previous step. B tells A that it intends to attack $ID^{*}$.

When C chooses the plaintexts to be encrypted, B passes them on to A. Then, A replies by sending the cyphertext $C_{1}$ of a randomly chosen message using the $SK_{ID^{*}}$. B passes it on to C after appending ID to $C_{1}$.

Now consider the second phase of C's decryption requests. What will B do if C asks for the decryption of some message of the form $C_{1}'.ID^{*}$? B cannot call $keygen(ID^{*})$ and respond to C's request.

Thus, our attempt to show that this scheme is CCA secure has ended in failure.

\subsection{The correct reduction}
We solve the problem mentioned in the previous section by signing encrypted messages. This idea is due to Canetti, Halevi and Katz. First, we introduce some notation:

Let SigPK and SigSK denote the public and private keys used by a secure signature algorithm. Let Sign(x) denote a signature for the message x created using SigPK. Let Verify(x, y) denote the result of the verification of a signature y for the message x using SigSK.

The algorithms used in the truly CCA secure scheme are as follows:

\begin{itemize}
 \item Setup(l): PK = PP. SK = MSK, SigSK, SigPK.
 \item Enc(m): Choose a random id, find $C_{1} = Enc_{IBE}(PP,ID,m)$, then compose the cyphertext $CT = C_{1}, ID, Sign(C_{1})$.
 \item Dec(CT): Decompose CT into $C_{1}$, ID and s, and check if s is the correct signature for $C_{1}$ by calling $Verify(C_{1}, s)$. If this fails, reply with $\perp$ and abort. Otherwise, get $Keygen(MSK, ID) = SK_{id}$; then use $Dec_{IBE}(C_{1}, SK_{id}) = m$ to retrieve the plaintext.
\end{itemize}

In this way, the problem encountered with the previous attempt at a provably secure scheme is averted. This can be seen by considering the scenario in which C requests the decryption of a message of the form C $CT = C_{1}, ID^{*}, s$ in phase 2, where $ID^{*}$ is the IBE ID being attacked by B. Now, as the signature scheme is assumed to be secure, the probability of C guessing a valid signature is negligibly small. So, when encountered with this request, B can call $Verify(C_{1}, s)$, and respond with $\perp$ if the result is negative and abort otherwise. So, the proof goes through and we have a CCA secure cryptosystem.

\end{document}