diff.tex

\chapter{Advanced Encryption Schemes}
\section{Identity-Based Encryption}

We introduce Bilinear Maps and two of its applications: NIKE, Non-Interactive Key Exchange; and IBE, Identity Based Encryption.


\section{Diffie-Hellman Key Exchange}

\begin{figure}
\label{fig:dh}
\centering
  \includegraphics[width=0.7\textwidth]{Old Scribe Notes/fig1.pdf}
\caption{Diffie-Hellman Key Exchange}
\end{figure}


Fig \ref{fig:dh} illustrates Diffie-Hellman key exchange. Alice and Bob each has a private key ($a$ and $b$ respectively), and they want to build a shared key for symmetric encryption communication. They can only communicate over a insecure link, which is eavesdropped by Eve.
So Alice generates a public key $A$ and Bob generates a public key $B$, and they send their public key to each other at the same time. Then Alice generates the shared key $K$ from $a$ and $B$, and likewise, Bob generates the shared key $K$ from $b$ and $A$.
And we have $\forall$ PPT Eve, $Pr[k=Eve(A,B)]=neg(k)$, where $k$ is the length of $a$.


\subsection{Discussion 1}

Assume that $\forall (g, p)$, and $a_1,b_1 \stackrel{\$}{\gets} Z^*_p$, and $a_2,b_2,r \stackrel{\$}{\gets}Z^*_p$, we have $(g^{a_1}, g^{b_1}, g^{a_1b_1}) \stackrel{c}{\simeq} (g^{a_2}, g^{b_2}, g^r)$. How to apply this to Diffie-Hellman Key Exchange?


Make $A=g^a$, $B=g^b$, $K=A^b=g^{ab}$, and $K=B^a=g^{ab}$.


\subsection{Discussion 2}


How does Diffie-Hellman Key Exchange imply Public Key Encryption?


Alice
$pk = A$, $sk = a$, $Enc(pk, m \in \{0, 1\})$.

Bob
$b,r \gets Z^*_p$
$(g^b, mA^b+(1-m)g^r)$

Alice $Dec(sk, (c_1, c_2))$

$c_1^a \stackrel{?}{=} c_2$




\section{Bilinear Maps}

\begin{definition}{Bilinear Maps}

Bilinear Maps is $(G,P,G_T,g,e)$, where $e$ is an efficient function $G \times G \to G_T$ such that

\begin{itemize}
\item if $g$ is generator of $G$, then $e(g, g)$ is the generator of $G_T$.
\item $\forall a,b \in Z_p$, we have $e(g^a, g^b) = e(g, g)^{ab} = e(g^b, g^a)$.
\end{itemize}

\end{definition}

\subsection{Discussion 1}


How does Bilinear Maps apply to Diffie-Hellman?

Make $A=g^a$, $B=g^b$, and $T=g^{ab}$, then Diffie-Hellman has $e(A, B)=e(g, T)$.


\section{Tripartite Diffie-Hellman}

\begin{figure}
\label{fig:3dh}
\centering
  \includegraphics[width=0.7\textwidth]{Old Scribe Notes/fig2.pdf}
\caption{Tripartite Diffie-Hellman Key Exchange}
\end{figure}

Fig \ref{fig:3dh} illustrates Tripartite Diffie-Hellman key exchange. $a$, $b$, and $c$ are private key of Alice, Bob, and Carol, respectively.
They use $g^a$, $g^b$, $g^c$ as public key, and the shared key $K=e(g,g)^{abc}$.
Formally, we have
$$a,b,c \stackrel{\$}{\gets} Z^*_p, r \stackrel{\$}{\gets} Z^*_p$$
$$A=g^a, B=g^b, C=g^c$$
$$K=e(g,g)^{abc}$$



\section{IBE: Identity-Based Encryption}
\DIFaddbegin \DIFadd{When two parties communicate secure messages through a public key infrastructure, they need to go through a time-consuming and error-prone process to get each other's key and verify each other's identity through a Certificate Authority. 
Identity-based cryptography (IBC) seeks to reduce these barriers by requiring no preparation on the part of the message recipient, therefore saving the initial round trip. 
Identity based encryption can also be used to construct CCA-secure public key encryption and digital signatures. 
}

\DIFaddend IBE contains four steps: \emph{Setup}, \emph{KeyGen}, \emph{Enc}, and \emph{Dec}. We illustrate it in Figure \ref{fig:ibe}.
\DIFaddbegin \DIFadd{IBE relies on a trusted third party called Private Key Generator(PKG). 
}\DIFaddend In first step, \DIFdelbegin \DIFdel{Key authority get }\DIFdelend \DIFaddbegin \DIFadd{PKG gets }\DIFaddend a Master Public Key (\DIFdelbegin \DIFdel{MPK}\DIFdelend \DIFaddbegin \DIFadd{$mpk$}\DIFaddend ) and Master Signing Key (\DIFdelbegin \DIFdel{MSK) from $Setup(1^k)$}\DIFdelend \DIFaddbegin \DIFadd{$msk$) from $Gen(1^n)$}\DIFaddend . 
Then a user with an ID (in this example, ``Mike''), sends his ID to the \DIFdelbegin \DIFdel{key authority. 
The key authority }\DIFdelend \DIFaddbegin \DIFadd{PKG. 
The PKG }\DIFaddend generates the Signing Key of Mike with \DIFdelbegin \DIFdel{$KeyGen(MSK, ID)$ }\DIFdelend \DIFaddbegin \DIFadd{$KeyGen(msk, id)$ }\DIFaddend ans sends it back. 
Another \DIFdelbegin \DIFdel{use}\DIFdelend \DIFaddbegin \DIFadd{user}\DIFaddend , Alice, wants to send an encrypted message to Mike. 
She only has \DIFdelbegin \DIFdel{MPK }\DIFdelend \DIFaddbegin \DIFadd{$mpk$ }\DIFaddend and Mike's ID. 
So she encrypts the message with \DIFdelbegin \DIFdel{$c=Enc(MPK, ID=Mike, m)$}\DIFdelend \DIFaddbegin \DIFadd{$c=Enc(mpk, id=Mike, m)$}\DIFaddend , and sends the encrypted message $c$ to Mike. 
Mike decodes $c$ with \DIFdelbegin \DIFdel{$m=Dec(c, SK_{Mike})$}\DIFdelend \DIFaddbegin \DIFadd{$m=Dec(c, sk_{Mike})$}\DIFaddend . 
Notice that Alice never need to know Mike's public key. 
She only needs to remember MPK and other people's IDs.

\begin{figure}
\label{fig:ibe}
\centering
  \includegraphics[width=0.7\textwidth]{Old Scribe Notes/fig3.pdf}
\caption{Identity-Based Encryption}
\end{figure}

\DIFdelbegin \DIFdel{Formally, we have
}\DIFdelend \DIFaddbegin \DIFadd{Then we define IBE formally, 
}\DIFaddend 

\DIFdelbegin \begin{displaymath}\DIFdel{Pr\begin{bmatrix}
       (MPK, MSK) \gets Setup(1^k), \\[0.3em]
       SK_{ID} \gets KeyGen(MSK, ID), \\[0.3em]
       c \gets Enc(MPK, ID, m), \\[0.3em]
       m \gets Dec(SK_{ID}, c)
     \end{bmatrix}
      =1}\end{displaymath}%DIFAUXCMD
\DIFdelend \DIFaddbegin \begin{definition}[Identity-Based Encryption]
    \DIFadd{An }\textbf{\DIFadd{identity based encryption scheme}} \DIFadd{$\mathcal{E}_{id} = (G,K,E,D)$ is a tuple of four efficient algorithms: a }\textbf{\DIFadd{setup algorithm}} \DIFadd{$G$, a }\textbf{\DIFadd{key generation algorithm}} \DIFadd{$K$, an }\textbf{\DIFadd{encryption algorithm}} \DIFadd{$E$, and a }\textbf{\DIFadd{decryption algorithm}} \DIFadd{$D$.
    }\begin{itemize}
        \item \DIFadd{$G$ is a probabilistic algorithm invoked as $(mpk, msk)\stackrel{\$}{\gets} G(1^n)$, where $mpk$ is called the }\textbf{\DIFadd{master public key}} \DIFadd{and $msk$ is called the }\textbf{\DIFadd{master secret key}} \DIFadd{for the IBE scheme.
        }\item \DIFadd{$K$ is a probabilistic algorithm invoked as $sk_{id}\stackrel{\$}{\gets}K(msk,id )$, where $msk$ is the master secret key (as output by $S$), $id \in \mathcal{ID}$ is an identity, and $sk_{id}$ is a secret key for id.
        }\item \DIFadd{$E$ is a probabilistic algorithm invoked as $c\stackrel{\$}{\gets}E(mpk,id, m)$.
        }\item \DIFadd{$D$ is a deterministic algorithm invoked as $m\gets D(sk_{id}, c)$. Here $m$ is either a message or a special reject value $\bot$ (distinct from all messages).
    }\end{itemize}
\end{definition}

\DIFadd{As usual, we define the correctness of IBE to be the decryption undoes encryption, formally we have 
}\begin{definition}[Correctness of IBE]
\DIFadd{$\forall n, id, m$, we have
}\[
\DIFadd{Pr\begin{bmatrix}
   (mpk,msk) \gets G(1^n), \\[0.3em]
   sk_{id} \gets K(msk, ID), \\[0.3em]
   c \gets E(mpk, id, m), \\[0.3em]
   m \gets D(sk_{id}, c)
\end{bmatrix}
  =1 - \text{negl}(n)
}\]\DIFaddend 
\DIFaddbegin \end{definition}
\DIFaddend 

\DIFdelbegin \subsection{\DIFdel{Security Descriptions}}
%DIFAUXCMD
\addtocounter{subsection}{-1}%DIFAUXCMD
\DIFdelend \DIFaddbegin \DIFadd{Next we define the security of IBE scheme. 
The basic security definition considers an adversary who obtains the secret keys for a number of identities of its choice. 
The adversary should not be able to break semantic security for some other identity of its choice for which it does not have the secret key.
}\DIFaddend 

\DIFdelbegin \DIFdel{We have different security descriptions for IBE, as discussed in this section.
}\DIFdelend \DIFaddbegin \begin{definition}[Security of IBE]
    \DIFadd{For an IBE scheme $\mathcal{E}_{id}=(G,K,E,D)$ is secure if $\forall$ nuPPT $\mathcal{A}$,
    }\[
    \DIFadd{\Pr[\text{Exp}_{\pi,\mathcal{A}}^{IBE,CPA}(n)=1]=\text{negl}(n)
    }\]
\end{definition}
\DIFaddend 

\DIFdelbegin \subsection{\DIFdel{CCA1}}
%DIFAUXCMD
\addtocounter{subsection}{-1}%DIFAUXCMD
%DIFDELCMD < \begin{tabular}{ r c l }
%DIFDELCMD <   %%%
\textbf{\DIFdel{Challenger}} %DIFAUXCMD
%DIFDELCMD < & & %%%
\textbf{\DIFdel{Adversary}} %DIFAUXCMD
%DIFDELCMD < \\
%DIFDELCMD <   %%%
\DIFdel{$(MPK, MSK) \gets Setup(1^k)$ }%DIFDELCMD < & %%%
\DIFdel{$\xrightarrow{MPK}$ }%DIFDELCMD < &  \\
%DIFDELCMD <    & %%%
\DIFdel{$\xleftarrow{ID_1}$ }%DIFDELCMD < & \\
%DIFDELCMD <   %%%
\DIFdel{$SK_{ID_1} \gets KeyGen(MSK, ID_1)$ }%DIFDELCMD < & %%%
\DIFdel{$\xrightarrow{SK_{ID_1}}$ }%DIFDELCMD < & \\
%DIFDELCMD <   %%%
\DIFdel{$\vdots$ }%DIFDELCMD < & %%%
\DIFdel{$\vdots$ }%DIFDELCMD < & %%%
\DIFdel{$\vdots$ }%DIFDELCMD < \\
%DIFDELCMD <    & %%%
\DIFdel{$\xleftarrow{ID_i}$ }%DIFDELCMD < & \\
%DIFDELCMD <   %%%
\DIFdel{$SK_{ID_i} \gets KeyGen(MSK, ID_i)$ }%DIFDELCMD < & %%%
\DIFdel{$\xrightarrow{SK_{ID_i}}$ }%DIFDELCMD < & \\
%DIFDELCMD <    & %%%
\DIFdel{$\xleftarrow{ID^*, m_0, m_1}$ }%DIFDELCMD < & %%%
\DIFdel{$\forall i \in [q], ID^* \neq ID_i$}%DIFDELCMD < \\
%DIFDELCMD <   %%%
\DIFdel{$b \overset{\$}{\gets} \{0, 1\}$, $c^* = Enc(MPK, ID^*, m_b)$ }%DIFDELCMD < & %%%
\DIFdel{$\xrightarrow{c^*}$ }%DIFDELCMD < & \\
%DIFDELCMD <   %%%
\DIFdel{Output $1$ if $b' = b$, otherwise $0$ }%DIFDELCMD < & %%%
\DIFdel{$\xleftarrow{b'}$ }%DIFDELCMD < & \\
%DIFDELCMD < \end{tabular}
%DIFDELCMD < 

%DIFDELCMD < %%%
\subsection{\DIFdel{CCA2}}
%DIFAUXCMD
\addtocounter{subsection}{-1}%DIFAUXCMD
\DIFdel{In CCA2, we allow adversary to send further queries after getting $c^*$}\DIFdelend \DIFaddbegin \DIFadd{We then define the experiment $\text{Exp}_{\pi,\mathcal{A}}^{IBE,CPA}$}\DIFaddend .
\DIFdelbegin %DIFDELCMD < 

%DIFDELCMD < \begin{tabular}{ r c l }
%DIFDELCMD <   %%%
\textbf{\DIFdel{Challenger}} %DIFAUXCMD
%DIFDELCMD < & & %%%
\textbf{\DIFdel{Adversary}} %DIFAUXCMD
%DIFDELCMD < \\
%DIFDELCMD <   %%%
\DIFdel{$(MPK, MSK) \gets Setup(1^k)$ }%DIFDELCMD < & %%%
\DIFdel{$\xrightarrow{MPK}$ }%DIFDELCMD < &  \\
%DIFDELCMD <    & %%%
\DIFdel{$\xleftarrow{ID_1}$ }%DIFDELCMD < & \\
%DIFDELCMD <   %%%
\DIFdel{$SK_{ID_1} \gets KeyGen(MSK, ID_1)$ }%DIFDELCMD < & %%%
\DIFdel{$\xrightarrow{SK_{ID_1}}$ }%DIFDELCMD < & \\
%DIFDELCMD <    & %%%
\DIFdel{$\vdots$ }%DIFDELCMD < & \\
%DIFDELCMD <    & %%%
\DIFdel{$\xleftarrow{ID_i}$ }%DIFDELCMD < & \\
%DIFDELCMD <   %%%
\DIFdel{$SK_{ID_q} \gets KeyGen(MSK, ID_q)$ }%DIFDELCMD < & %%%
\DIFdel{$\xrightarrow{SK_{ID_q}}$ }%DIFDELCMD < & \\
%DIFDELCMD <    & %%%
\DIFdel{$\xleftarrow{ID^*, m_0, m_1}$ }%DIFDELCMD < & %%%
\DIFdel{$\forall i \in [q'], ID^* \neq ID_i$}%DIFDELCMD < \\
%DIFDELCMD <   %%%
\DIFdel{$b \overset{\$}{\gets} \{0, 1\}$, $c^* = Enc(MPK, ID^*, m_b)$ }%DIFDELCMD < & %%%
\DIFdel{$\xrightarrow{c^*}$ }%DIFDELCMD < & \\
%DIFDELCMD <    & %%%
\DIFdel{$\xleftarrow{ID_{q+1}}$ }%DIFDELCMD < & \\
%DIFDELCMD <   %%%
\DIFdel{$SK_{ID_{q+1}} \gets KeyGen(MSK, ID_{q+1})$ }%DIFDELCMD < & %%%
\DIFdel{$\xrightarrow{SK_{ID_{q+1}}}$ }%DIFDELCMD < & \\
%DIFDELCMD <   %%%
\DIFdel{$\vdots$ }%DIFDELCMD < & %%%
\DIFdel{$\vdots$ }%DIFDELCMD < & %%%
\DIFdel{$\vdots$ }%DIFDELCMD < \\
%DIFDELCMD <    & %%%
\DIFdel{$\xleftarrow{ID_{q'}}$ }%DIFDELCMD < & \\
%DIFDELCMD <   %%%
\DIFdel{$SK_{ID_{q'}} \gets KeyGen(MSK, ID_{q'})$ }%DIFDELCMD < & %%%
\DIFdel{$\xrightarrow{SK_{ID_{q'}}}$ }%DIFDELCMD < & \\
%DIFDELCMD <   %%%
\DIFdel{Output }\DIFdelend \DIFaddbegin \begin{definition}[IBE-CPA Experiment]
\DIFadd{We denote the experiment in the following order: 
}\begin{enumerate}
    \item \DIFadd{The challenger invokes $(mpk, msk)\stackrel{\$}{\gets} G(1^n)$ and send $mpk$ to adversary $\mathcal{A}$.
    }\item \DIFadd{$\mathcal{A}$ can make multiple key queries and generate desired ID $id^{*}$ and two message $(m_0, m_1)$. 
    }\item \DIFadd{Challenger random selects $b\stackrel{\$}{\gets}\{0,1\}$ and encrypt $c^{*}=E(mpk, id^{*},m_b)$ and send $c^{*}$ to $\mathcal{A}$.
    }\item \DIFadd{$\mathcal{A}$ can make more encryption queries based on $c^{*}$ and other id and message $(m_0,m_1)$. Note that throughout the process $\mathcal{A}$ can }\textbf{\DIFadd{never}} \DIFadd{make any query on $id^{*}$. 
    }\item \DIFadd{At the end, $\mathcal{A}$ generate $b'$ and send to challenger. 
    }\item \DIFadd{Challenger output }\DIFaddend $1$ if \DIFdelbegin \DIFdel{$b' = b$, otherwise $0$ }%DIFDELCMD < & %%%
\DIFdel{$\xleftarrow{b'}$ }%DIFDELCMD < & \\
%DIFDELCMD < \end{tabular}
%DIFDELCMD < 

%DIFDELCMD < %%%
\subsection{\DIFdel{Selective Security}}
%DIFAUXCMD
\addtocounter{subsection}{-1}%DIFAUXCMD
\DIFdel{In selective security , the adversary sends $ID^*$ before everything.
}%DIFDELCMD < 

%DIFDELCMD < \begin{tabular}{ r c l }
%DIFDELCMD <   %%%
\textbf{\DIFdel{Challenger}} %DIFAUXCMD
%DIFDELCMD < & & %%%
\textbf{\DIFdel{Adversary}} %DIFAUXCMD
%DIFDELCMD < \\
%DIFDELCMD <    & %%%
\DIFdel{$\xleftarrow{ID^*}$ }%DIFDELCMD < & %%%
\DIFdel{$\forall i \in [q], ID^* \neq ID_i$}%DIFDELCMD < \\
%DIFDELCMD <   %%%
\DIFdel{$(MPK, MSK) \gets Setup(1^k)$ }%DIFDELCMD < & %%%
\DIFdel{$\xrightarrow{MPK}$ }%DIFDELCMD < &  \\
%DIFDELCMD <    & %%%
\DIFdel{$\xleftarrow{ID_1}$ }%DIFDELCMD < & \\
%DIFDELCMD <   %%%
\DIFdel{$SK_{ID_1} \gets KeyGen(MSK, ID_1)$ }%DIFDELCMD < & %%%
\DIFdel{$\xrightarrow{SK_{ID_1}}$ }%DIFDELCMD < & \\
%DIFDELCMD <   %%%
\DIFdel{$\vdots$ }%DIFDELCMD < & %%%
\DIFdel{$\vdots$ }%DIFDELCMD < & %%%
\DIFdel{$\vdots$ }%DIFDELCMD < \\
%DIFDELCMD <    & %%%
\DIFdel{$\xleftarrow{ID_q}$ }%DIFDELCMD < & \\
%DIFDELCMD <   %%%
\DIFdel{$SK_{ID_q} \gets KeyGen(MSK, ID_q)$ }%DIFDELCMD < & %%%
\DIFdel{$\xrightarrow{SK_{ID_q}}$ }%DIFDELCMD < & \\
%DIFDELCMD <    & %%%
\DIFdel{$\xleftarrow{m_0, m_1}$ }%DIFDELCMD < & \\
%DIFDELCMD <   %%%
\DIFdel{$b \overset{\$}{\gets} \{0, 1\}$}\DIFdelend \DIFaddbegin \DIFadd{$b=b'$}\DIFaddend , \DIFdelbegin \DIFdel{$c^* = Enc(MPK, ID^*, m_b)$ }%DIFDELCMD < & %%%
\DIFdel{$\xrightarrow{c^*}$ }%DIFDELCMD < & \\
%DIFDELCMD <   %%%
\DIFdel{Output $1$ if $b' = b$,
    otherwise }\DIFdelend $0$ \DIFdelbegin %DIFDELCMD < & %%%
\DIFdel{$\xleftarrow{b'}$ }%DIFDELCMD < & \\
%DIFDELCMD < \end{tabular}
%DIFDELCMD < %%%
\DIFdelend \DIFaddbegin \DIFadd{otherwise. 
}\end{enumerate}
\end{definition}
\DIFaddend 

\DIFdelbegin \subsection{\DIFdel{Discussion 1}}
%DIFAUXCMD
\addtocounter{subsection}{-1}%DIFAUXCMD
\DIFdel{How does Bilinear Maps apply to IBE?
}\DIFdelend \DIFaddbegin \subsection{\DIFadd{IBE Construction from Pairing}}
\DIFadd{We then present a concrete IBE construction from pairing.
First, we will give the hardness assumption in this scheme called }\textbf{\DIFadd{bilinear Diffe-Hellman}} \DIFadd{assumption, or BDH. 
This assumption says that given random element $g_0^{\alpha},g_0^{\beta},g_0^{\gamma}\in\mathbb{G_0}$ and a few additional terms, the quantity $e(g0,g1)^{\alpha\beta\gamma}\in\mathbb{G}_T$ is computationally indistinguishable from a random element in GT.
}\DIFaddend 

\DIFdelbegin \DIFdel{Given Bilinear Maps: 
$(G, P, G_T, g, e)$, we have
}\DIFdelend \DIFaddbegin \begin{definition}[Decisional bilinear Diffe-Hellman]
    \DIFadd{Let $e: \mathbb{G}_0\times\mathbb{G}_1\rightarrow\mathbb{G}_T$ be a pairing where $\mathbb{G}_0,\mathbb{G}_1,\mathbb{G}_T$ are cyclic groups of prime order $q$ with generators $g_0 \in \mathbb{G}_0$ and $g_1 \in \mathbb{G}_1$. For a given adversary $\mathcal{A}$, the following distribution is distinguishable: 
    }\[
    \DIFadd{\{g_0^{\alpha},g_1^{\alpha},g_0^{\beta},g_1^{\gamma},e(g_0,g_1)^{\alpha\beta\gamma},  \alpha,\beta,\gamma\stackrel{\$}{\gets}\mathbb{Z}_q\} \approx^{c}
    \{g_0^{\alpha},g_1^{\alpha},g_0^{\beta},g_1^{\gamma},e(g_0,g_1)^{\delta},  \alpha,\beta,\gamma,\delta\stackrel{\$}{\gets}\mathbb{Z}_q\}
    }\]
\end{definition}
\DIFaddend 

\DIFdelbegin %DIFDELCMD < \begin{enumerate}
%DIFDELCMD < %%%
\DIFdelend \DIFaddbegin \DIFadd{Note that this assumption work even with $g_0=g_1$.
}

\DIFadd{We then present our IBE construction. 
}\begin{itemize}
    \DIFaddend \item \DIFdelbegin \DIFdel{$(G, P, G_T, g, e) \gets Setup(1^k)$
}\DIFdelend \DIFaddbegin \DIFadd{$G(1^n)$: 
    }\[
    \DIFadd{\alpha\stackrel{\$}{\gets}\mathbb{Z}_q, mpk\gets g^\alpha, msk\gets\alpha
    }\]
    \DIFadd{and output ($mpk,msk$)
    }\DIFaddend \item \DIFdelbegin \DIFdel{$s \gets Z^*_p$, and $H_1: \{0, 1\}^* \to G $, $H_2: G_T \to \{0, 1\}^n$
}\DIFdelend \DIFaddbegin \DIFadd{$K(msk=\alpha,id)$:
    }\[
    \DIFadd{sk_{id}\gets H(id)^\alpha
    }\]
    \DIFadd{where $H$ is a hash function $H:\{0,1\}^{*}\rightarrow\mathbb{G}$
    }\DIFaddend \item \DIFdelbegin \DIFdel{$MPK = (G, g^s, H_1, H_2)$, and $MSK = (s)$
}%DIFDELCMD < \end{enumerate}
%DIFDELCMD < %%%
\DIFdelend \DIFaddbegin \DIFadd{$E(mpk, id, m)$: 
    }\[
    \DIFadd{\beta\stackrel{\$}{\gets}\mathbb{Z}_q, c_1\gets g^{\beta}, c_2\gets e(mpk,H(id)^{\beta})\cdot m
    }\]
    \DIFadd{and output $(c_1,c_2)$.
    }\item \DIFadd{$D(sk_{id}, c=(c_1, c_2))$:
    }\[
    \DIFadd{m=\frac{c_2}{e(c_1,sk_{id})}
    }\]
\end{itemize}
\DIFadd{By the property of bilinear map, we can verify the correctness of this scheme, 
}\begin{align*}
    \DIFadd{m }&\DIFadd{= \frac{c_2}{e(c_1,sk_{id})} }\\
      &\DIFadd{= \frac{e(mpk,H(id)^{\beta})\cdot m}{e(c_1,sk_{id})} }\\
      &\DIFadd{= \frac{e(g^\alpha,H(id)^{\beta})\cdot m}{e(g^{\beta}, H(id)^{\alpha})} }\\
      &\DIFadd{= \frac{e(g,H(id))^{\alpha\beta}}{e(g, H(id))^{\alpha\beta}}\cdot m }\\
      &\DIFadd{= m
}\end{align*}
\DIFaddend 

\DIFdelbegin \DIFdel{Let's look at how we construct each function in IBE.
    }\DIFdelend \DIFaddbegin \DIFadd{We then prove the security property under random oracle model.
}\begin{theorem}
    \DIFadd{If decision BDH holds for e, H is modelled as a random oracle, then the above construction is a secure IBE scheme. 
}\end{theorem}
\begin{proof}
    \DIFadd{Let $\mathcal{A}$ be an adversary that breaks the IBE scheme, we can construct another adversary $\mathcal{B}$ such that it breaks the DBDH assumption.
}\DIFaddend 

    \DIFdelbegin \paragraph{\DIFdel{$KeyGen(s, ID)$:}}%DIFAUXCMD
\addtocounter{paragraph}{-1}%DIFAUXCMD
\DIFdel{~}%DIFDELCMD < \\
%DIFDELCMD < %%%
\DIFdelend \DIFaddbegin \DIFadd{The adversary $\mathcal{B}$ works as follows:
    }\DIFaddend \begin{enumerate}
        \item \DIFdelbegin \DIFdel{Output $SK_{ID} = (H_1(ID))^s$
}%DIFDELCMD < \end{enumerate}
%DIFDELCMD < 

%DIFDELCMD < %%%
\paragraph{\DIFdel{$Enc(MPK, ID, m)$:}}%DIFAUXCMD
\addtocounter{paragraph}{-1}%DIFAUXCMD
\DIFdel{~}%DIFDELCMD < \\
%DIFDELCMD < \begin{enumerate}
%DIFDELCMD < %%%
\DIFdelend \DIFaddbegin \DIFadd{$\mathcal{B}$ receives 5 elements as input $\{g^{\alpha},g^{\beta},g^{\gamma},z,  \alpha,\beta,\gamma\stackrel{\$}{\gets}\mathbb{Z}_q,z\in\mathbb{G}\}$, and $\mathcal{B}$ need to determine whether $z=e(g,g)^{\alpha\beta\gamma}$ or not. 
        }\DIFaddend \item \DIFdelbegin \DIFdel{$r \gets Z^*_p$
}\DIFdelend \DIFaddbegin \DIFadd{$\mathcal{B}$ send IBE public parameter $mpk=g^{\alpha}$ to IBE adversary $\mathcal{A}$.
        }\DIFaddend \item \DIFdelbegin \DIFdel{$c_1 = g^r$
}\DIFdelend \DIFaddbegin \DIFadd{Then $\mathcal{A}$ will make multiple $sk_{id}$ queries to $\mathcal{B}$. $\mathcal{B}$ responds them by (1) Choose $\rho\stackrel{\$}{\gets}\mathbb{Z}_q$ (2) Setting $H(id)=g^{\rho}$ (3) set the secret key be $sk_{id}=H(id)^{\alpha}=g^{\rho\cdot\alpha}$. One }\textbf{\DIFadd{exception}} \DIFadd{is that $\mathcal{B}$ will set a random $id'$ whose $H(id')=g^\beta$.
        }\DIFaddend \item \DIFdelbegin \DIFdel{$c_2 = m \oplus H_2(e(A, H_1(ID)^r))$, where $A = g^s$
}\DIFdelend \DIFaddbegin \DIFadd{After receiving the key query, $\mathcal{A}$ outputs $(id^{*}, m_0,m_1)$.  
        }\DIFaddend \item \DIFdelbegin \DIFdel{Output $(c_1, c_2)$
}\DIFdelend \DIFaddbegin \DIFadd{When $\mathcal{B}$ receives encryption query $(id^{*}, m_0, m_1)$, it first check if $\mathcal{A}$ have previously query $sk_{id^*}$ before, if yes, then abort. Otherwise, $\mathcal{B}$ choose $b\stackrel{\$}{\gets}\{0,1\}$ and encrypt $m_b$ using $(c_1=g^\gamma, c_2=e(msk,H(id')^\gamma)\cdot m_b)$ and send back to $\mathcal{A}$.
        }\item \DIFadd{$\mathcal{A}$ eventually output $b'$ to $\mathcal{B}$. And $\mathcal{B}$ output $1$ if $b'=b$ and $0$ otherwise. 
    }\DIFaddend \end{enumerate}
    \DIFaddbegin \DIFadd{Since $e(msk,H(id')^{\gamma})=e(g^\alpha,g^{\beta\gamma})=e(g,g)^{\alpha\beta\gamma}$, $\mathcal{B}$ can embedded the challenge to $\mathcal{A}$ and break DBDH. }\qed
\end{proof}
\DIFaddend 

\DIFdelbegin \paragraph{\DIFdel{$Dec(SK_{ID}, (c_1, c_2))$:}}%DIFAUXCMD
\addtocounter{paragraph}{-1}%DIFAUXCMD
\DIFdel{~}%DIFDELCMD < \\
%DIFDELCMD < \begin{enumerate}
%DIFDELCMD < %%%
\DIFdelend \DIFaddbegin \subsection{\DIFadd{Digital Signature from IBE}}
\DIFadd{We can directly derive a secure signature scheme from IBE. 
Given a secure IBE $\mathcal{E}_{id}=(G,K,E,D)$ with id space $\mathcal{ID}$ and message space $\mathcal{M}_{IBE}$, we construct a secure digital signature scheme $\mathcal{S} = (G',S',V')$ as follows: 
}\begin{itemize}
    \DIFaddend \item \DIFdelbegin \DIFdel{Get $e(A, H_1(ID)^r) = e(H_1(ID)^s, c_1) = e(SK_{ID}, c_1)$
}\DIFdelend \DIFaddbegin \DIFadd{$G'(1^n)$: run $(mpk, msk)\stackrel{\$}{\gets} G(1^n)$ and output $(mpk, msk)$ as the sign key pair, with $mpk$ as verification key and $msk$ as sign key.
    }\DIFaddend \item \DIFdelbegin \DIFdel{Get $m = c_2 \oplus H_2(e(A, H_1(ID))^r)$
}%DIFDELCMD < \end{enumerate}
%DIFDELCMD < 

%DIFDELCMD < \proof
%DIFDELCMD < %%%
\DIFdel{To prove this, we use a hybrid argument.
Assume we have two oracles with exact random functions, denoted as $O_{H_1}$ and $O_{H_2}$. 
One can request a random string from them with a query ID. The random strings are denoted as $H_1(ID)$ and $H_2(ID)$, respectively.
These two oracles keep track of query IDs and corresponding responses. 
If a query ID was seen before, they return the exact same response corresponding to it.
If not, they generate a random string, correspond the string to the ID, and return the string}\DIFdelend \DIFaddbegin \DIFadd{$S'(msk,m)$: Given message $m\in\mathcal{ID}$, compute $\sigma\stackrel{\$}{\gets}K(msk,m)$, output $\sigma$ as signature. 
    }\item \DIFadd{$V'(mpk,m,\sigma)$: Choose $r\stackrel{\$}{\gets}\mathcal{M}_{IBE}$, compute $c\stackrel{\$}{\gets}E(mpk,m,r)$, and accept if $D(\sigma,c) = r$}\DIFaddend . 
\DIFaddbegin \end{itemize}
\DIFaddend 

\DIFdelbegin \DIFdel{We first define $\mathcal{H}_0$, in which $H_1(ID)$ and $H_2(ID)$ are generated by the oracles. We use the construction described above.  
        }%DIFDELCMD < 

%DIFDELCMD < \begin{tabular}{ r c l }
%DIFDELCMD <   %%%
\textbf{\DIFdel{Challenger}} %DIFAUXCMD
%DIFDELCMD < & & %%%
\textbf{\DIFdel{Adversary}} %DIFAUXCMD
%DIFDELCMD < \\
%DIFDELCMD <    & %%%
\DIFdel{$\xleftarrow{\mathcal{G}, ID^*}$ }%DIFDELCMD < & %%%
\DIFdel{$\forall i \in [q], ID^* \neq ID_i$}%DIFDELCMD < \\
%DIFDELCMD <    & %%%
\DIFdel{$\xleftarrow{g^s}$ }%DIFDELCMD < & \\
%DIFDELCMD <    & %%%
\DIFdel{$\xleftarrow{O_{H_1}}$ }%DIFDELCMD < & \\
%DIFDELCMD <    & %%%
\DIFdel{$\xleftarrow{O_{H_2}}$ }%DIFDELCMD < & \\
%DIFDELCMD <    & %%%
\DIFdel{$\xleftarrow{ID_1}$ }%DIFDELCMD < & \\
%DIFDELCMD <   %%%
\DIFdel{$SK_{ID_1} \gets KeyGen(s, ID_1)$ }%DIFDELCMD < & %%%
\DIFdel{$\xrightarrow{SK_{ID_1}}$ }%DIFDELCMD < & \\
%DIFDELCMD <   %%%
\DIFdel{$\vdots$ }%DIFDELCMD < & %%%
\DIFdel{$\vdots$ }%DIFDELCMD < & %%%
\DIFdel{$\vdots$ }%DIFDELCMD < \\
%DIFDELCMD <    & %%%
\DIFdel{$\xleftarrow{ID_q}$ }%DIFDELCMD < & \\
%DIFDELCMD <   %%%
\DIFdel{$SK_{ID_q} \gets KeyGen(s, ID_q)$ }%DIFDELCMD < & %%%
\DIFdel{$\xrightarrow{SK_{ID_q}}$ }%DIFDELCMD < & \\
%DIFDELCMD <    & %%%
\DIFdel{$\xleftarrow{m_0, m_1}$ }%DIFDELCMD < & \\
%DIFDELCMD <   %%%
\DIFdel{$b \overset{\$}{\gets} \{0, 1\}$, $c^* = Enc(MPK, ID^*, m_b)$ }%DIFDELCMD < & %%%
\DIFdel{$\xrightarrow{c^*}$ }%DIFDELCMD < & \\
%DIFDELCMD <   %%%
\DIFdel{Output $1$ if $b' = b$, otherwise $0$ }%DIFDELCMD < & %%%
\DIFdel{$\xleftarrow{b'}$ }%DIFDELCMD < & \\
%DIFDELCMD < \end{tabular}
%DIFDELCMD < 

%DIFDELCMD < %%%
\DIFdel{Then we discard oracle's $H_1$, and use $H_1(ID) = g^{\alpha_{ID}}$, where $\alpha_{ID} \gets Z^*_p$. }\DIFdelend We \DIFdelbegin \DIFdel{denote this as $\mathcal{H}_1$. 
}\DIFdelend \DIFaddbegin \DIFadd{have the following theorem,
}\begin{theorem}
    \DIFadd{Let $\mathcal{E}_{id}$ be a secure IBE with message space is super-poly. Then the derive signature scheme $\mathcal{S}$ is a secure digital signature scheme. 
}\end{theorem}
\begin{proof}
    \DIFadd{Let $\mathcal{A}$ be an adversary that breaks the digital signature scheme, we can construct another adversary $\mathcal{B}$ such that breaks the IBE security.
}\DIFaddend 

    \DIFdelbegin \DIFdel{Then we change $SK_{ID}$ }\DIFdelend \DIFaddbegin \DIFadd{The BIE adversary $\mathcal{B}$ is modelled as follows:
    }\begin{enumerate}
        \item \DIFadd{$\mathcal{B}$ receives $mpk$ from the challenger, and forward $mpk$ as a signature public key to $\mathcal{A}$. 
        }\item \DIFadd{$\mathcal{A}$ makes a series of signing queries $m_0,\dots,m_n$ }\DIFaddend to \DIFdelbegin \DIFdel{$SK_{ID} = (H_1(ID))^s = (g^{\alpha_{ID}})^s$.
    We denote this as $\mathcal{H}_2$. 
    }%DIFDELCMD < 

%DIFDELCMD < %%%
\DIFdel{We have Bilinear Decision Diffie-Hellman (DDH). If $\mathcal{H}_2$ breaks DDH, then $\mathcal{H}_0$ can as well}\DIFdelend \DIFaddbegin \DIFadd{$\mathcal{B}$}\DIFaddend . \DIFaddbegin \DIFadd{$\mathcal{B}$ responds by issuing the corresponding key query to the challenger and forwarding the answer back the response to $\mathcal{A}$. 
        }\item \DIFadd{$\mathcal{A}$ will output a signature forgery $(m,\sigma)$ which it didn't issue the sign query $m$. 
        }\item \DIFadd{$\mathcal{B}$ then choose two random message $t_0,t_1\stackrel{\$}{\gets}\mathcal{M}_{IBE}$ and issue encryption query with the identity $m$.
        }\item \DIFadd{$\mathcal{B} $gets back the ciphertext $c\stackrel{\$}{\gets}E(mpk,m,t_b)$ for $b\in{0,1}$. Then it runs $t'\gets D(\sigma,c)$ and output $b'=t'$. 
    }\end{enumerate}
    \DIFadd{We observe that 
    }\begin{itemize}
        \item \DIFadd{when $b = 1$, then $c\stackrel{\$}{\gets}E(mpk, m,t_1)$, and $\mathcal{B}$ outputs 1 with probability the same as the probability of $\mathcal{A}$ breaks digital signature, we note as $SIGadv[\mathcal{A,S}]$
        }\item \DIFadd{when $b = 0$, then $c\stackrel{\$}{\gets}E(mpk, m,t_0)$, and $\mathcal{B}$ outputs 1 with probability $1/|\mathcal{M}_{IBE}|$ since $\mathcal{B}$ can only make random guess in the message space. 
    }\end{itemize}
    \DIFadd{We then have the probability of $\mathcal{B}$ break IBE scheme
    }\[
        \DIFadd{\frac{1}{2}(SIGadv}[\DIFadd{\mathcal{A,S}}] \DIFadd{+ 1/|\mathcal{M}_{IBE}|)
    }\]
    \DIFadd{which is not negligible if $SIGadv[\mathcal{A,S}]$ is not negligible. }\qed
\DIFaddend 

\DIFdelbegin \DIFdel{In DDH, we have $(g^a, g^b, g^c, e(g, g)^{abc}) \stackrel{c}{\simeq} (g^a, g^b, g^c, e(g, g)^r)$. 
        We denote $A = g^a$, $B = g^b$, $C = g^c$. And in $\mathcal{H}_2$, we have $A = g^s$, $B = H_1(ID^*)$, $C = c_1 = g^r$.
And in $c_2 = m \oplus H_2(e(g^s, H_1(ID^*))^r)$, we have $T = H_2(e(g^s, H_1(ID^*))^r) = e(g, g)^{abc}$. }%DIFDELCMD < 

%DIFDELCMD < %%%
\DIFdel{$\qed$
}%DIFDELCMD < 

%DIFDELCMD <  %%%
\DIFdelend \DIFaddbegin \end{proof}
 \DIFaddend