Attribute-based encryption

Attribute-based encryption (ABE) generalizes IBE by replacing exact-identity matching with expressive Boolean access policies. The decryption relation is a pair $(f,x)\in \mathcal{F}\times 2^{\mathcal{U}}$, where $f$ is a monotone Boolean formula over attributes from universe $\mathcal{U}$ and $x\subseteq \mathcal{U}$ is an attribute set; decryption succeeds if and only if $f(x)=1$. ABE comes in two dual flavors depending on which component travels with the key and which with the ciphertext:

Variant	Key holds	Ciphertext holds
KP-ABE (Key-Policy)	policy $f$	attribute set $x$
CP-ABE (Ciphertext-Policy)	attribute set $x$	policy $f$

Policies are typically expressed as monotone Boolean formulas, which subsume threshold gates and conjunctions, or more generally as Linear Secret-Sharing Schemes (LSSS), which are strictly more expressive at polynomial size — KW93.

Syntax

An ABE scheme is a tuple of efficient algorithms $\mathsf{ABE}=(\mathsf{Setup},\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ with respect to attribute universe $\mathcal{U}$, policy class $\mathcal{F}$, 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 master secret key $\mathsf{msk}$,
• $\mathsf{KeyGen}(\mathsf{msk},\cdot )\to \mathsf{sk},$ is a (possibly randomized) algorithm that takes $\mathsf{msk}$ and either a policy $f\in \mathcal{F}$ (KP-ABE) or an attribute set $x\subseteq \mathcal{U}$ (CP-ABE), outputting a secret key,
• $\mathsf{Enc}(\mathsf{pp},\cdot ,m)\to c,$ is a randomized algorithm that takes $\mathsf{pp}$, either an attribute set $x\subseteq \mathcal{U}$ (KP-ABE) or a policy $f\in \mathcal{F}$ (CP-ABE), and $m\in \mathcal{M}$, outputting $c\in \mathcal{C}$,
• $\mathsf{Dec}(\mathsf{sk},c)\to m,$ is a deterministic algorithm that takes a secret key and ciphertext, outputting $m\in \mathcal{M}$ or $\perp$.

Decryption succeeds if and only if the associated $(f,x)$ pair satisfies $f(x)=1$.

Properties

Correctness

An ABE scheme $\mathsf{ABE}$ is $(1-\epsilon )$-correct if for all $\lambda \in \mathbb{N}$, policy-attribute pairs $(f,x)$ with $f(x)=1$, and $m\in \mathcal{M}$,

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

where $f_{\mathrm{key}}$ and $f_{\mathrm{ct}}$ denote whichever of $\{f,x\}$ is placed in the key vs. ciphertext by the variant, over $(\mathsf{pp},\mathsf{msk})\leftarrow \mathsf{Setup}(1^{\lambda })$ and randomness of $\mathsf{KeyGen}$ and $\mathsf{Enc}$.

KP-ABE: IND-CPA Security

In KP-ABE, the adversary queries keys for policies of its choice. The challenge is an attribute set $x^{\ast }$ and two messages. Admissibility: no queried policy $f$ may satisfy $f(x^{\ast })=1$.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{kp\text{-}cpa}}_{\ABE,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\pp, \msk) \gets \Setup(1^\secpar)$; $b \getsr \bits$
\State $\calO_{\mathrm{key}}(f) := \KeyGen(\msk, f)$
\State $(x^*, m_0, m_1, \stA) \gets \calA^{\calO_{\mathrm{key}}}(1^\secpar, \pp)$
\Comment{$\calA$ may not have queried $\calO_{\mathrm{key}}(f)$ for $f(x^*) = 1$}
\State $c^* \gets \Enc(\pp, x^*, m_b)$
\State $b' \gets \calA^{\calO_{\mathrm{key}}}(c^*, \stA)$
\Comment{$\calA$ may not query $\calO_{\mathrm{key}}(f)$ for $f(x^*) = 1$}
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

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

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

is negligible.

CP-ABE: IND-CPA Security

In CP-ABE, the adversary queries keys for attribute sets of its choice. The challenge is a policy $f^{\ast }$ and two messages. Admissibility: no queried attribute set $x$ may satisfy $f^{\ast }(x)=1$.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{cp\text{-}cpa}}_{\ABE,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\pp, \msk) \gets \Setup(1^\secpar)$; $b \getsr \bits$
\State $\calO_{\mathrm{key}}(x) := \KeyGen(\msk, x)$
\State $(f^*, m_0, m_1, \stA) \gets \calA^{\calO_{\mathrm{key}}}(1^\secpar, \pp)$
\Comment{$\calA$ may not have queried $\calO_{\mathrm{key}}(x)$ for $f^*(x) = 1$}
\State $c^* \gets \Enc(\pp, f^*, m_b)$
\State $b' \gets \calA^{\calO_{\mathrm{key}}}(c^*, \stA)$
\Comment{$\calA$ may not query $\calO_{\mathrm{key}}(x)$ for $f^*(x) = 1$}
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

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

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

is negligible.

Selective Security

In both KP-ABE and CP-ABE, the selective variant requires the adversary to commit to the challenge ($x^{\ast }$ in KP-ABE, $f^{\ast }$ in CP-ABE) before $\mathsf{Setup}$ runs. Selective security is strictly weaker than adaptive security; complexity leveraging BB04b converts one to the other at a loss factor of $2^{|\mathcal{U}|}$ for KP-ABE, but the conversion for CP-ABE can incur exponential loss in the formula size.

Variations

Syntactic Duality of KP-ABE and CP-ABE

KP-ABE and CP-ABE are syntactically dual: swapping the roles of $\mathsf{KeyGen}$ and $\mathsf{Enc}$ converts one definition into the other. The correspondence is between definitions, not a transformation of schemes. Selective security does not imply adaptive security in either flavor — folklore; see no-selective-security-to-cp-abe-ind-cpa-security.

Large-Universe ABE

In small-universe ABE, all supported attributes are registered at $\mathsf{Setup}$ time and embedded into the public parameters; the universe size is bounded a priori. In large-universe constructions, attributes can be arbitrary strings not known at $\mathsf{Setup}$; keys and ciphertexts for new attributes can be created at any time without re-running $\mathsf{Setup}$. Large-universe constructions are necessary for real-world deployments where the set of possible attributes cannot be fixed in advance — RW13.

Policy Hiding

Standard KP-ABE and CP-ABE leak the access policy: in KP-ABE the policy $f$ is visible in the key, and in CP-ABE the policy $f^{\ast }$ is visible in the ciphertext. Hiding the policy from unauthorized parties requires additional techniques. IPPE is a key stepping stone toward full policy hiding, since inner-product predicates are both expressive and attribute-hiding.

Other results

• ABE ⇒ Fuzzy IBE
• The GPSW06 KP-ABE supports delegation of private keys, which subsumes HIBE — GPSW06
• ABE ⇒ BE
• BDH ⇒ ABE
• Bilinear pairing ⇒ CP-ABE (generic bilinear group model)
• DBDH + DLIN ⇒ IBE
• DBDH + DLIN ⇒ HIBE
• $k$-Linear assumption ⇒ ABE
• Large-universe KP-ABE and CP-ABE in prime-order bilinear groups, selectively secure in the standard model under two $q$-type assumptions — RW13

Participates in

Builds on Attribute-based encryption

• ABE ⇒ BE
• ABE ⇒ Fuzzy IBE
• ABE ⇒ IBE

Produces Attribute-based encryption

• BDH ⇒ ABE
• Bilinear pairing ⇒ CP-ABE (via CP-ABE: IND-CPA Security)
• Evasive circular LWE ⇒ ABE
• Evasive LWE + Tensor LWE ⇒ ABE
• $k$-Linear assumption ⇒ ABE
• LWE with sub-exponential ratio ⇒ Selectively secure ABE for circuits (GVW) (via Selective Security)
• Succinct LWE ⇒ ABE

Barriers

• No fixed-construction reduction from selective to adaptive CP-ABE security (via Selective Security, CP-ABE: IND-CPA Security)