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

\pdfpagewidth 8.5in
\pdfpageheight 11in

\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{4}{29-Jan-2009}{Brent Waters} {Drake Dowsett} {Identity-Based Encryption}

\section{Identity-Based Encryption}

\subsection{Overview}

Identity-Based Encryption (IBE) centers around the ability to encrypt a message by simply known the name of the intended recipient. In an IBE protocol an \textit{Authority} publishes some \textit{Public Parameters} ($PP$) which enable an \textit{Encryptor} to produce some ciphertext that only the intended recipient as \textit{Decryptor} can decrypt. The \textit{Authority} generates and delivers upon request a \textit{Secret Key} ($SK_{ID}$) based on both the publicly available \textit{Public Parameters} and the privately known \textit{Master Secret Key} ($MSK$), which, upon delivery to the \textit{Decryptor}, is used to decrypt the ciphertext.\\

\begin{figure}[h]
\centering
% In case anyone is curious, to create the drawings, I created SVG images, 5in
% in width, in Inkscape and then exported them as PDF documents. -Drake
\includegraphics{drawing1.pdf}
\caption{Simple drawing of IBE Authority, Encryptor and Decryptor relationships}
\label{fig:1}
\end{figure}

\noindent
As can be seen in Figure~\ref{fig:1}, the \textit{Encryptor} is free to be offline while encrypting, since he or she is not required to communicate with the \textit{Authority} after the \textit{Public Parameters} are published. This is an advantage over Public-Key Encryption as it doesn't require a public-key lookup for each intended recipient. Instead, the \textit{Encryptor} uses the recipient's name---for example, ``alice@yahoo.com".\\

\noindent
By comparison though, this is not a benefit for all crypto-systems; protocols such as SSL carry on a dialog online and would gain nothing from the ability to encrypt offline. IBE is better suited to message drop-off or, even more creatively, to send messages to entities that don't exist yet, such as ``chairperson2010@yahoo.com".\\

\noindent
What happens in IBE when the \textit{Authority} is compromised? The \textit{Encryptor} will not be aware that the system is insecure and will continue unhesitatingly. Compare this to Certificate Authorities (CAs): if one CA is compromised other CAs will still be there to cross-reference against, so an attacker would need to infiltrate more than one CA to convincingly deceive someone.\\

\noindent
\textit{Side note: How do CAs such as Verisign work? Verisign has some verification key $VK_{sig}$ and signs a statement such as ``$PK_{Brent}$ is Brent's public key" and calls it a certificate. Then Brent can publish $PK_{Brent}$ along with the certificate. Someone wishing to communicate with Brent:
\begin{enumerate}
\item retrieves $PK_{Brent}$ and the certificate
\item verifies the certificate using $VK_{sig}$
\item encrypts a message to Brent using $PK_{Brent}$
\end{enumerate}
But how does your web browser know whom to trust to begin with? It is boot-strapped, delivered with 40+ pre-trusted CAs.}

\subsection{Algorithms}

\begin{description}
\item[$Setup(\lambda)\rightarrow (PP,MSK):$] The \textit{Authority}, based on some security parameter $\lambda$, generates a \textit{Master Secret Key} and derives and publishes some \textit{Public Parameters} from the $MSK$ specific to the system (e.g. ``Dean of Natural Sciences").
\item[$KeyGen(MSK,ID)\rightarrow SK_{ID}:$] The \textit{Authority} derives \textit{Secret Keys} for each identity in the system based on the $MSK$ and the $ID$.
\item[$Enc(PP,ID,M)\rightarrow CT:$] The \textit{Encryptor} generates a ciphertext $CT$ by blinding the message $M$ based on the \textit{Public Parameters} and the $ID$ of the intended recipient.
\item[$Dec(CT,SK_{ID})\rightarrow M or ``fail":$] The \textit{Decryptor} recreates the original message $M$, or fails, by requesting its $SK_{ID}$ from the \textit{Authority} and unblinding the ciphertext $CT$.
\end{description}

\subsection{Security Model}

Going back to Goldwasser and Micali's definition of ``semantic security" (discussed in the last class), we will design a challenger/attacker pair that can be reduced to some other hard problem. The IBE challenger and attacker play their game in 5 phases (as shown in Figure~\ref{fig:2}):

\begin{figure}[h]
\centering
\includegraphics{drawing2.pdf}
\caption{Visualization of IBE challenger \& attacker to show semantic security under CPA}
\label{fig:2}
\end{figure}

\begin{enumerate}
\item The challenger sets up by presenting the attacker with the \textit{Public Parameters}
\item The attacker presents a series of $ID$s ($ID_{1}, ..., ID_{n}$) to the challenger and the challenger returns the corresponding $SK_{ID_{i}}$. This is \textit{Key Phase I}.
\item The attacker presents a 3-tuple to the challenger of some $ID*$, not requested in \textit{Key Phase I}, along with two messages $M_{0}$ and $M_{1}$. The challenger flips a coin $\gamma$ and returns the encrypted ciphertext of the corresponding message.
\item The attacker is now permitted a second \textit{Key Phase II}, in which he or she may query the challenger for any number of \textit{Secret Keys} to $ID_{n+1}$ through $ID_{n+m}$, excepting that to $ID*$, which is the $ID$ whose $SK_{ID}$ the attacker is meant to break.
\item The attacker presents a bit $\gamma'$, indicating which of the two messages $M_{0}$ and $M_{1}$ he or she believes the challenger to have encrypted.
\end{enumerate}

\noindent
As you may recall, the system is thought to be semantically secure if the attacker has no better than a probability of $\frac{1}{2}$ (random guess) at providing a correct $\gamma'$ (such that $\gamma=\gamma'$).\\

\noindent
This model is intended to be weak, allowing the attacker to know the $SK_{ID}$s for up to all $ID$s except for $ID*$. Then it can be argued that since even this week model reduces to a hard problem, any more restrictive model will not prove anything more. What hard problem can an IBE system be reduced to, though? To answer this, we must first introduce some bilinear group theory.

\section{Bilinear Groups}

\subsection{Introduction}

If $G$ is bilinear group of order $p$ with a generator $g$, then there exist:

\begin{itemize}
\item Some parity operator $\cdot$
\item Some bilinear map $e: G \times G \rightarrow G_{T}$ such that $\forall a,b\in Zp~e(g^{a},g^{b}) = e(g,g)^{ab}$ where $G_{T}$ is the ``target group'' and $g^{a} \in G, g^{b} \in G, e(g,g)^{ab} \in G_{T}$
\end{itemize}

\noindent
The bilinear map $e$ is reflexive, so $e(h_{1},h_{2})=e(h_{2},h_{1})$. $e$ is also a ``one shot" function and can't be chained together transitively as its domain and range are of different groups. For any $g_{1}, g_{2} \in G$, $e(g_{1}, g_{2})$ is a generator of $G_{T}$. The target group is also of order $p$.

\subsection{Hard Problems}

We have already looked at:

\begin{itemize}
\item $CDH$: given $g$, $g^{a}$, $g^{b}$ output $g^{ab}$
\item $DDH$: given $g$, $g^{a}$, $g^{b}$, $T$ decide whether $T = g^{ab}$ or $T = $~random\\

In the case where $T = g^{ab}$:
\begin{eqnarray}
e(g,T) & =? & e(g^{a},g^{b}) \nonumber\\
e(g^{1}, g^{ab}) & =? & e(g^{a},g^{b}) \nonumber\\
e(g,g)^{ab} & = & e(g,g)^{ab} \nonumber
\end{eqnarray}

In the case where $T = $~random:
\begin{eqnarray}
e(g,R) & =? & e(g^{a},g^{b}) \nonumber\\
e(g^{1}, R) & \neq & e(g,g)^{ab} \nonumber
\end{eqnarray}
\end{itemize}

\noindent
With bilinear groups, it's no longer hard to discern between $T = g^{ab}$ or $T = $~random! That's bad news for El Gamal... or is it good news for IBE?\\

\noindent
For IBE systems we'll reduce to the hard Decisional Bilinear Diffie-Hellman (decisional-BDH) problem instead:

\begin{itemize}
\item $dBDH$: given $g$, $g^{a}$, $g^{b}$, $g^{c}$, $T$ decide whether $T = e(g,g)^{abc}$ or $T =$~random
\end{itemize}

\end{document}