Identity-based encryption

An identity-based encryption (IBE) scheme allows a sender to encrypt to an arbitrary string identity (such as an email address) without requiring the recipient to distribute a public key in advance. A trusted key generation center (KGC) holds a master secret key and issues per-identity decryption keys on demand. IBE eliminates the need for a public-key infrastructure by replacing public keys with identities.

Syntax

An IBE scheme is a tuple of efficient algorithms $\mathsf{IBE}=(\mathsf{Setup},\mathsf{Extract},\mathsf{Enc},\mathsf{Dec})$ with respect to identity space $\mathcal{I}$, message space $\mathcal{M}$, and ciphertext space $\mathcal{C}$:

• $\mathsf{Setup}(1^{\lambda })\to (\mathsf{pp},\mathsf{msk}),$ is a randomized algorithm that outputs public parameters $\mathsf{pp}$ and a master secret key $\mathsf{msk}$,
• $\mathsf{Extract}(\mathsf{msk},id)\to {\mathsf{sk}}_{id},$ is a (possibly randomized) algorithm that takes the master secret key $\mathsf{msk}$ and an identity $id\in \mathcal{I}$, outputting a per-identity secret key ${\mathsf{sk}}_{id}$,
• $\mathsf{Enc}(\mathsf{pp},id,m)\to c,$ is a randomized algorithm that takes $\mathsf{pp}$, an identity $id\in \mathcal{I}$, and a message $m\in \mathcal{M}$, outputting a ciphertext $c\in \mathcal{C}$,
• $\mathsf{Dec}({\mathsf{sk}}_{id},c)\to m,$ is a deterministic algorithm that takes a secret key ${\mathsf{sk}}_{id}$ and ciphertext $c\in \mathcal{C}$, outputting a message $m\in \mathcal{M}$ or $\perp$ to indicate failure.

Properties

Correctness

An IBE scheme $\mathsf{IBE}$ is $(1-\epsilon )$-correct if for all $\lambda \in \mathbb{N}$, $id\in \mathcal{I}$, and $m\in \mathcal{M}$,

$$\mathrm{Pr}\left[\mathsf{Dec}(\mathsf{Extract}(\mathsf{msk},id),\mathsf{Enc}(\mathsf{pp},id,m))=m\right]\ge 1-\epsilon ,$$

over $(\mathsf{pp},\mathsf{msk})\leftarrow \mathsf{Setup}(1^{\lambda })$ and the randomness of $\mathsf{Extract}$ and $\mathsf{Enc}$. When $\epsilon =0$, we say $\mathsf{IBE}$ is perfectly correct.

IND-ID-CPA Security

In the adaptive IND-ID-CPA game, the adversary may query the key extraction oracle ${\mathcal{O}}_{\mathrm{ext}}$ for any identity of its choice throughout both phases. The only constraint is admissibility: it may not extract a key for the challenge identity ${id}^{\ast }$.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{id\text{-}cpa}}_{\IBE,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\pp, \msk) \gets \Setup(1^\secpar)$; $b \getsr \bits$
\State $\calO_{\mathrm{ext}}(\mathit{id}) := \Extract(\msk, \mathit{id})$
\State $(\mathit{id}^*, m_0, m_1, \stA) \gets \calA^{\calO_{\mathrm{ext}}}(1^\secpar, \pp)$
\Comment{$\calA$ may not query $\calO_{\mathrm{ext}}(\mathit{id}^*)$}
\State $c^* \gets \Enc(\pp, \mathit{id}^*, m_b)$
\State $b' \gets \calA^{\calO_{\mathrm{ext}}}(c^*, \stA)$
\Comment{$\calA$ may not query $\calO_{\mathrm{ext}}(\mathit{id}^*)$}
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

An IBE scheme $\mathsf{IBE}$ is IND-ID-CPA-secure if for all efficient admissible $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{IBE},\mathcal{A}}^{\mathrm{id}\text{-}\mathrm{cpa}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{IBE},\mathcal{A}}^{\mathrm{id}\text{-}\mathrm{cpa}}(\lambda )=1\right]-1\right|$$

is negligible. The admissibility constraint is necessary: without it, $\mathcal{A}$ trivially wins by extracting ${\mathsf{sk}}_{{id}^{\ast }}$ and decrypting.

IND-sID-CPA Security (Selective)

In the selective variant, the adversary must commit to the challenge identity ${id}^{\ast }$ before the public parameters are generated. This is a strictly weaker notion than adaptive IND-ID-CPA.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{sid\text{-}cpa}}_{\IBE,\calA}(\secpar)$}
\begin{algorithmic}
\State $\mathit{id}^* \gets \calA(1^\secpar)$
\Comment{$\calA$ commits to challenge identity before seeing $\pp$}
\State $(\pp, \msk) \gets \Setup(1^\secpar)$; $b \getsr \bits$
\State $\calO_{\mathrm{ext}}(\mathit{id}) := \Extract(\msk, \mathit{id})$
\State $(m_0, m_1, \stA) \gets \calA^{\calO_{\mathrm{ext}}}(\pp)$
\Comment{$\calA$ may not query $\calO_{\mathrm{ext}}(\mathit{id}^*)$}
\State $c^* \gets \Enc(\pp, \mathit{id}^*, m_b)$
\State $b' \gets \calA^{\calO_{\mathrm{ext}}}(c^*, \stA)$
\Comment{$\calA$ may not query $\calO_{\mathrm{ext}}(\mathit{id}^*)$}
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

An IBE scheme $\mathsf{IBE}$ is IND-sID-CPA-secure if for all efficient admissible $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{IBE},\mathcal{A}}^{\mathrm{sid}\text{-}\mathrm{cpa}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{IBE},\mathcal{A}}^{\mathrm{sid}\text{-}\mathrm{cpa}}(\lambda )=1\right]-1\right|$$

is negligible. Any IND-ID-CPA-secure scheme is also IND-sID-CPA-secure; the converse requires a complexity-leveraging argument that incurs a polynomial security loss in $|\mathcal{I}|$.

Variations

IND-ID-CCA Security

Analogously to PKE, the CCA variant additionally provides the adversary with a decryption oracle $\mathcal{D}(c):=\mathsf{Dec}({\mathsf{sk}}_{{id}^{\ast }},c)$ in both phases. The admissibility condition extends to: the adversary may not query ${\mathcal{O}}_{\mathrm{ext}}({id}^{\ast })$, and may not query $\mathcal{D}(c^{\ast })$ after the challenge is issued.

Other results

• IBE implies PKE: set the public key to $\mathsf{pp}$ and the per-user public key to $id$; the KGC plays the role of a CA but without issuing certificates
• IBE is generalized by HIBE, which adds a delegation algorithm allowing any identity to issue keys for its sub-identities
• IBE is generalized by Fuzzy IBE, which allows partial identity matching via a threshold overlap condition
• IBE is a special case of both KP-ABE and CP-ABE with singleton policies
• The first practical IBE construction uses Weil pairings and is CCA-secure in the random oracle model under CBDH — BF01
• The first adaptive IBE in the standard model under simple assumptions uses the dual system encryption technique — Wat09