Hierarchical identity-based encryption

A hierarchical identity-based encryption (HIBE) scheme extends IBE by organizing identities into a tree: an entity at depth $k$ holds an identity vector $\overrightarrow{id}=({id}_1,\dots ,{id}_k)$ where ${id}_1$ is the root domain and each subsequent component refines the identity. Any node can delegate a decryption key to any of its children without involvement of the root KGC. HIBE models real-world key delegation in organizations and DNS-style identity hierarchies.

Syntax

An HIBE scheme is a tuple of efficient algorithms $\mathsf{HIBE}=(\mathsf{Setup},\mathsf{Extract},\mathsf{Delegate},\mathsf{Enc},\mathsf{Dec})$ with respect to maximum depth $d$, alphabet $\Sigma$, message space $\mathcal{M}$, and ciphertext space $\mathcal{C}$. Identity vectors are tuples $\overrightarrow{id}=({id}_1,\dots ,{id}_k)\in {\Sigma }^{\le d}$:

• $\mathsf{Setup}(1^{\lambda },d)\to (\mathsf{pp},\mathsf{msk}),$ is a randomized algorithm that outputs public parameters $\mathsf{pp}$ (including the depth bound $d$) and master secret key $\mathsf{msk}$,
• $\mathsf{Extract}(\mathsf{msk},\overrightarrow{id})\to {\mathsf{sk}}_{\overrightarrow{id}},$ is a (possibly randomized) algorithm that takes $\mathsf{msk}$ and an identity vector $\overrightarrow{id}$ of any depth, outputting a secret key ${\mathsf{sk}}_{\overrightarrow{id}}$,
• $\mathsf{Delegate}({\mathsf{sk}}_{\overrightarrow{id}},{id}^{\prime })\to {\mathsf{sk}}_{\overrightarrow{id}\Vert {id}^{\prime }},$ is a (possibly randomized) algorithm that takes a key for $\overrightarrow{id}$ and a child identity component ${id}^{\prime }\in \Sigma$, outputting a key for the extended identity $\overrightarrow{id}\Vert {id}^{\prime }$,
• $\mathsf{Enc}(\mathsf{pp},\overrightarrow{id},m)\to c,$ is a randomized algorithm that takes $\mathsf{pp}$, an identity vector $\overrightarrow{id}$, and $m\in \mathcal{M}$, outputting $c\in \mathcal{C}$,
• $\mathsf{Dec}({\mathsf{sk}}_{{\overrightarrow{id}}^{\prime }},c)\to m,$ is a deterministic algorithm that takes a secret key and ciphertext, outputting $m\in \mathcal{M}$ or $\perp$.

Correctness requires that a ciphertext encrypted for $\overrightarrow{id}$ can be decrypted by ${\mathsf{sk}}_{{\overrightarrow{id}}^{\prime }}$ for any ${\overrightarrow{id}}^{\prime }=\overrightarrow{id}$, and also by any key derived from ${\mathsf{sk}}_{{\overrightarrow{id}}^{\prime }}$ via $\mathsf{Delegate}$. Note: keys derived via $\mathsf{Delegate}$ are typically less efficient (larger) than those from $\mathsf{Extract}$; in many constructions key size grows by $O(1)$ group elements per delegation level.

The alphabet $\Sigma$ contains $\{0,1{\}}^{\lambda }$, as the identity space of an IBE scheme does. With a constant-size alphabet and constant depth there are only constantly many identity vectors, and one PKE key pair per vector, published together, meets the notion — standard.

Properties

Correctness

An HIBE scheme $\mathsf{HIBE}$ is $(1-\epsilon )$-correct if for all $\lambda \in \mathbb{N}$, $\overrightarrow{id}\in {\Sigma }^{\le d}$, and $m\in \mathcal{M}$,

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

over $(\mathsf{pp},\mathsf{msk})\leftarrow \mathsf{Setup}(1^{\lambda },d)$ and the randomness of $\mathsf{Extract}$ and $\mathsf{Enc}$; and similarly for any key obtained by a sequence of $\mathsf{Delegate}$ calls from a root-extracted key.

IND-HIBE-CPA Security

The adaptive IND-HIBE-CPA game is similar to IBE but with a stronger admissibility constraint: since any key for a prefix ${\overrightarrow{id}}^{\ast }[\mathrm{1..}k]$ ($k\le |{\overrightarrow{id}}^{\ast }|$) can be used to delegate down to ${\mathsf{sk}}_{{\overrightarrow{id}}^{\ast }}$, the adversary may not extract any ancestor (prefix) of the challenge identity, including ${\overrightarrow{id}}^{\ast }$ itself.

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

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

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

is negligible. The prefix constraint is necessary because $\mathsf{Delegate}$ is publicly computable from an ancestor key.

IND-sHIBE-CPA Security (Selective)

In the selective variant, the adversary commits to the challenge identity ${\overrightarrow{id}}^{\ast }$ before $\mathsf{Setup}$ runs. When $|{\Sigma }^{\le d}|$ is superpolynomial, selective security of a scheme does not imply its adaptive security, and guessing ${\overrightarrow{id}}^{\ast }$ recovers adaptive security only at a loss factor of $|{\Sigma }^{\le d}|$ — folklore. For HIBE schemes with a checkability property on keys and ciphertexts, any simple black-box reduction proving adaptive security from a non-interactive assumption loses a factor exponential in $d$ — LW14. An adaptively secure HIBE can be built from any selectively secure IBE — GKR25.

Sub-exponential IND-sHIBE-CPA Security

An HIBE scheme $\mathsf{HIBE}$ is sub-exponentially IND-sHIBE-CPA-secure if there is a constant $ϵ>0$ such that for all sufficiently large $\lambda$, every admissible selective adversary $\mathcal{A}$ of size at most $2^{{\lambda }^{ϵ}}$ has advantage at most $2^{-{\lambda }^{ϵ}}$.

Variations

Anonymous HIBE

An anonymous HIBE additionally hides the recipient identity $\overrightarrow{id}$ from the ciphertext, so an eavesdropper learns neither the payload nor the intended recipient.

Other results

• HIBE ⇒ IBE
• IND-sID-CPA Security (Selective) ⇒ HIBE
• BBG05 achieves $O(1)$ ciphertext size and $O(d)$ key size — BBG05
• The first adaptive HIBE in the standard model under simple assumptions uses dual system encryption — Wat09

Participates in

Builds on Hierarchical identity-based encryption

• Anonymous HIBE ⇒ HIBE (via Anonymous HIBE)
• Selectively secure HIBE ⇒ Selectively secure IBE (via IND-sHIBE-CPA Security (Selective))
• HIBE ⇒ IBE
• Sub-exponentially selective HIBE ⇒ adaptive HIBE (via Sub-exponential IND-sHIBE-CPA Security)

Produces Hierarchical identity-based encryption

• Anonymous HIBE ⇒ HIBE
• DBDH + DLIN ⇒ HIBE
• IND-sID-CPA Security (Selective) ⇒ HIBE
• LWE ⇒ Selectively secure HIBE (bonsai trees) (via IND-sHIBE-CPA Security (Selective))
• Sub-exponentially selective HIBE ⇒ adaptive HIBE (via IND-HIBE-CPA Security)

Barriers

• No fixed-construction reduction from IND-sHIBE-CPA Security (Selective) to IND-HIBE-CPA Security (via IND-HIBE-CPA Security, IND-sHIBE-CPA Security (Selective))