\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{7}{2/10/2009}{Brent Waters} {Ioannis Rouselakis} {Boneh-Boyen Proof \& Waters IBE System}
\section{Review}
Last lecture we discussed about the Boneh-Boyen IBE system, which is an IBE system without
random oracle. We started proving that this system is secure under the Selective-ID Model.
In that model the attacker states from the beginning the identity she is going to attack, $ID^*$,
before seeing the public parameters and has the ability to request as many secret keys
she likes for any other $ID$.
Remember that Setup phase worked as follows:
\begin{itemize}
\item The trusted authority picks three random group elements of a group $G$ of prime order $p$: $g,h,u \in G$.
\item Then she picks random $a,b\in \Z_p$.
\item The Master Secret Key is $MSK=g^{ab}$.
\item The Public Parameters are $PP=(g,h,u,e(g,g)^{ab})$ and the hash function $f(ID)=u^{ID}h$ where $ID \in \Z_p$.
\end{itemize}
For the proof we have to show that an attacker on BB system can be used to solve the Decisional Bidirectional Diffie-Hellman
problem. That is, the simulator (or BB Challenger) will get the following parameters: $g,A=g^a, B=g^b, C=g^c$ and $T\in G_T$
where $T=e(g,g)^{abc}$ or $T$ is a random element from $G_T$. To solve DBDH he has to answer with $1/2$ plus more than
negligible probability correctly whether $T=e(g,g)^{abc}$ or random.
The initial Setup we proposed for the simulator was the following:
\begin{enumerate}
\item Choose a random $y\in \Z_p$.
\item The public parameters are: $PP=(g,e(g,g)^{ab}=e(A,B),u=A,h=A^{-ID^*}g^y)$. Notice that we know beforehand the
identity $ID^*$ the attacker will attack.
\item $f(ID) = u^{ID}h = A^{ID-ID^*}g^y$.
\end{enumerate}
\subsection{Simulator's View}
However the above schema looks special to the simulator. Firstly, we have that
$f(ID^*) = g^y$ which is a ``special value''. We inserted the random parameter $g^y$
so that the attacker doesn't get $f(ID^*) = 1$ and quit.
In addition the cipher text from the simulator's point of view is the following:
\begin{equation*}
CT=(C_0,C_1,C_2) = (Me(g,g)^{abs},g^s,g^{a \cdot \Delta ID \cdot s}g^{ys})
\end{equation*}
where $\Delta ID = ID - ID^*$.
Notice now that if $\Delta ID = 0$ as a simulator we cannot decrypt $CT$. That is because we try to find
the blinding factor $e(g,g)^{abs}$. If $\Delta ID \neq 0$ we can do the following:
\begin{equation*}
\left(\frac{C_2}{C_1^y}\right)^{\frac{1}{\Delta ID}} = \left( g^{a\cdot \Delta ID \cdot s}\right)^{\frac{1}{\Delta ID}} = g^{as}
\end{equation*}
By taking $e(g^b,g^{as})$ we calculate the blinding factor $e(g,g)^{abs}$. If $\Delta ID $ were 0, we wouldn't be able to do that.
That way the simulation seems a little less ``magical'' to the simulator.\\
As we mentioned in the previous lecture we need to add randomness in the key generation phase, so that the attacker
thinks that keys are distributed randomly. We can do that by re-randomizing the keys. If we give a key for a certain
$ID$, the next key can be random, based on the previous key and the public parameters. Suppose we gave the following key
with random parameter $r$: $ K_1=g^{ab}f(ID)^r, \quad K_2=g^r$. Then we can choose a random $t\in \Z_p$ and create a key
with randomness $r'=t+r$. This can be done since:
\begin{align*}
K'_1&=g^{ab}f(ID)^{r+t}=g^{ab}f(ID)^rf(ID)^t=K_1f(ID)^t\\
K'_2&=g^{r+t}=g^rg^t=K_2g^t
\end{align*}
\section{Proof of Security (continued)}
\begin{theorem}[Boneh-Boyen IBE]
Decisional-BDH is hard $\Rightarrow$ Boneh-Boyen IBE is CPA selective-ID secure.
\end{theorem}
\begin{proof}
The simulator (the DBDH attacker) is given the following parameters: $A=g^a, B=g^b, C=g^c, T$ where
$T=e(g,g)^{abc}$ or random. We suppose that she has gone through the Setup and Key Phase 1, the way we
discussed in the first part of the proof. Now we are going to examine the Challenge Phase.
That is, the attacker sends to the simulator two messages $M_0$ and $M_1$ to encrypt. The simulator chooses
a random $\gamma \in \{0,1\}$. Then she should present the attacker with the (valid) encryption of $M_\gamma$. In
order to do that she calculates the following:
\begin{align*}
C_0&=M_\gamma T\\
C_1&=g^c=C \quad \text{That is $c$ plays the role of $s$}\\
C_2&=f(ID^*)^c=g^{yc}=C^y \quad \text{$y$ is known because we chose it}
\end{align*}
The simulator sends $CT=(C_0,C_1,C_2)$ to the attacker and the attacker responds with $\gamma'$; his guess of $\gamma$.
Actually, before she does that he might request another set of secret keys for various identities (except $ID^*$)
and the simulator can respond as before with random secret keys.
If $(A,B,C,T)$ was a correct DBDH combination, the attacker will respond with $\gamma'= \gamma$ and the simulator will
respond with ``yes'' correctly, thus solving DBDH. If $T$ was random, then the attacker will give a random answer with
probability 0.5 and the simulator will answer correctly in half of the cases. Notice that in contrast to BF proof the
probability we need to abort is 0, because we know beforehand the identity $ID^*$ the attacker wants to attack. That is the
``strangeness'' of the selective ID model. In the next section we will see a cryptosystem that uses a less restrictive
assumption.\\
To complete the proof say that the probability of success of the BB attacker is $\frac{1}{2}+\epsilon$, where
$\epsilon$ is not negligible. Then the probability of solving DBDH is:
\begin{align*}
Pr(success)&=Pr(success|T=e(g,g)^{ab})Pr(T=e(g,g)^{ab})+Pr(success|T=R)Pr(T=R)=\\
&=(\frac{1}{2}+\epsilon)\frac{1}{2}+\frac{1}{2}\cdot \frac{1}{2} = \frac{1}{2}+\frac{\epsilon}{2}
\end{align*}
\end{proof}
\section{Waters '05 System}
As we mentioned in the above proof the selective-ID model imposes a very strong assumption on the proof of security. That is, the
attacker picks at the very beginning only one identity to attack and notifies everyone about it. In order to make
a weaker assumption we partition the identities space in two sets: challenge space and the rest. The special identities the attacker
is allowed to attack lie in the challenge space. If she asks for a private key for one of them, we abort. For all the
others we provide her with the secret keys. Hopefully in the end she will attack one special ID. Supposing that the attacker
makes $Q$ private key queries, the challenge space's size is $1/Q$ of the whole identity space. The cryptosystem is the following:
\subsection{System}
We assume that each identity is an element of $\{0,1\}^n$, i.e. $n$-bits integers. Then the following is the $\alg{Setup}$ phase
for Waters IBE system. The algorithms for $\alg{Encrypt}$, $\alg{Decrypt}$ and $\alg{KeyGen}$ are exactly the same as in the Boneh-Boyen
system.\\
$\alg{Setup}$
\begin{enumerate}
\item Pick two random $(a,b) \in \Z_p$.
\item Pick $n+2$ random elements from group $G$ of prime order $p$: $g,h,u_1,u_2,\ldots,u_n$.
\item The public parameters are $PP=(g,e(g,g)^{ab},h,u_1,u_2,\ldots,u_n)$, where $e(g,g)^{ab} \in G_T$.
\item Suppose each $ID$ consists of the following bits $\vec{ID}=(ID_1,ID_2,\ldots,ID_n)$. Then we define
$f(ID)=h\cdot \prod_{i=1}^n u_i^{ID_i}$.
\item The master secret key is $MSK=g^{ab}$ as in BB system.
\end{enumerate}
\subsection{Proof of Security (Sketch)}
\begin{theorem}[Waters IBE]
Decisional-BDH is hard $\Rightarrow$ Waters IBE is CPA Q-selective-ID secure (where by Q-selective-ID we mean that
the attacker can attack only ID's in the challenge space of size $1/Q$).
\end{theorem}
\vspace*{-\parskip}\noindent\textit{Sketch of Proof.}
As before the security of the system is based on DBDH assumption. That is, we are given a tuple $g,A=g^a,B=g^b,C=g^c,T$ and
we try to find if $T=e(g,g)^{abc}$ using an attacker on the cryptosystem. This adversary is allowed now to make $Q$ private
key queries of identities and attack some other identity. $Q$ is known to us from the beginning. The setup phase we do is the
following.
For every $i$ from 1 to $n$ ($n$ is the number of bits of every ID) we choose a random $x_i \in \{0,1,\ldots,c'Q\}$ where
$c'$ is a constant ($c' \approx 8$). Also we choose a random $y_i\in \Z_p$. From these we calculate each $u_i$ for the
cryptosystem as $u_i=A^{x_i}g^{y_i}$. Remember $A=g^a$.
We choose a random $z\in \{0,1,\ldots,n\}$ and a random $y\in \Z_p$. We define $h=A^{-Qz}g^y$. According to the cryptosystem
the function $f(ID)$ is the following:
\begin{equation*}
f(ID)=h\cdot \prod_{i=1}^n u_i^{ID_i}=A^{t(ID)}g^{w(ID)}
\end{equation*}
where
\begin{align*}
t(ID)&=-Qz+\sum_i ID_ix_i\\
w(ID)&=y+\sum_i ID_iy_i
\end{align*}
The assertion we do now is that when $t(ID)=0$, the identity $ID$ is in challenge space and when $t(ID)\neq 0$, it is inside
the private space. The ``high level'' argument for that assertion is that $-Qz$ comes in multiples of $Q$. Therefore when
we pick $n$ random elements $ID_i$ from the identity space, the probability that $\sum_i ID_ix_i$ is also a multiple of $Q$
is less than $1/Q$. That is the relative size of the challenge space. The probability that for a random identity $t(ID)\neq 0$ is
$1-\frac{1}{Q}$.
Using these ideas it is provable that the cryptosystem is secure.
\section{Crypto Attack Exercise}
\textit{Try to break a Boneh-Franklin encryption where the public key is $PK=(g,g^y)$ and the secret key for identity
$ID$ is $SK_{ID}=H(ID)^y$, where the Boneh-Boyen function $H(ID)=f(ID)=u^{ID}h$ is used; or prove that this system is secure.}\\
\emph{Solution}\\
The proposed system is not secure because we can do the following to acquire the secret key of any identity $ID^*$ we want
(provided we can acquire at least two secret keys for other identities):
\begin{enumerate}
\item We request the secret keys for two identities $ID_1, ID_2$ different than $ID^*$. These are:
$X_1=f(ID_1)^y=(u^{ID_1}h)^y$ and $X_2=(u^{ID_2}h)^y$.
\item We calculate the following quantity:
\begin{equation*}
Q_1 = (\frac{X_1}{X_2})^{\frac{1}{ID_1-ID2}} = (\frac{u^{ID_1y}}{u^{ID_2y}}\cdot \frac{h^y}{h^y})^
{\frac{1}{ID_1-ID2}}= u^{\frac{(ID_1-ID2)y}{ID_1-ID2}} = u^y
\end{equation*}
\item We calculate
\begin{equation*}
Q_2 = \frac{X_1^{\frac{1}{ID_1}}}{Q_1}=\frac{u^y h^{\frac{y}{ID_1}}}{u^y}= h^{\frac{y}{ID_1}}
\end{equation*}
\item Finally we get $Q_3 = Q_2^{ID_1} = h^y$.
\end{enumerate}
With the above we can find the secret key of $ID^*$ and decrypt his messages by $Q_1^{ID^*}Q_3=(u^y)^{ID^*}h^y=H(ID^*)^y=SK_{ID^*}$.
\begin{thebibliography}{1}
\bibitem{BW05} Brent Waters. \emph{Efficient Identity-Based Encryption Without Random Oracles.}
Proceedings of Eurocrypt 2005.
\end{thebibliography}
\end{document}