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 {\mathcal{U}}^{\ast }$, 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 (or equivalently, as Linear Secret-Sharing Schemes (LSSS)), which subsume threshold gates and conjunctions.

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 converts one to the other at a polynomial cost in $|\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. This structural observation is useful for intuition but does not give a black-box security reduction. In particular, a selective KP-ABE security proof does not imply adaptive CP-ABE security via the syntactic swap, because the two games have different admissibility constraints and different distributions of challenge objects.

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 (KP-ABE) generalizes Fuzzy IBE: threshold-$t$ overlap policies are monotone formulas
• ABE (KP-ABE) subsumes HIBE: tree-structured delegation can be expressed as a depth-bounded formula, though KP-ABE does not expose a native $\mathsf{Delegate}$ algorithm
• ABE (CP-ABE) subsumes BE: set-membership policies $f^{\ast }(x)=[x\in S^{\ast }]$ are a special case of monotone DNF
• ABE is incomparable to IPPE: IPPE achieves attribute-hiding but only captures inner-product predicates; KP/CP-ABE handles arbitrary monotone formulas but leaks the policy
• GPSW06 introduced KP-ABE and gave the first construction for monotone formulas, proving selective security under DBDH — GPSW06
• BSW07 introduced CP-ABE with a construction proved secure in the generic group model — BSW07
• Wat11 gave the first CP-ABE with a standard-model proof of selective security under DBDH — Wat11
• The dual system encryption technique of Wat09 gives adaptively secure IBE, HIBE, and ABE under simple pairing-based assumptions — Wat09
• RW13 gives large-universe KP-ABE and CP-ABE constructions for any monotone formula under variants of the $k$-linear assumption — RW13