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.

Symmetric CP-ABE

In symmetric CP-ABE (secret-key CP-ABE), there are no public parameters: all parties must hold a key from the authority. Encryption takes the encryptor’s key ${\mathsf{sk}}_{x_e}$ and may only embed a policy $f$ that the encryptor’s own attribute set satisfies, $f(x_e)=1$.

A symmetric CP-ABE scheme is a tuple $\mathsf{ABE}=(\mathsf{Setup},\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ with respect to attribute universe $\mathcal{U}$, policy class $\mathcal{F}$, and message space $\mathcal{M}$:

• $\mathsf{Setup}(1^{\lambda })\to \mathsf{msk},$ outputs a master secret key with no public parameters.
• $\mathsf{KeyGen}(\mathsf{msk},x)\to {\mathsf{sk}}_x,$ takes $\mathsf{msk}$ and $x\subseteq \mathcal{U}$, outputting a key bound to $x$.
• $\mathsf{Enc}({\mathsf{sk}}_x,f,m)\to c,$ takes an encryptor key ${\mathsf{sk}}_x$, a policy $f\in \mathcal{F}$ with $f(x)=1$, and $m\in \mathcal{M}$.
• $\mathsf{Dec}({\mathsf{sk}}_{x^{\prime }},c)\to m\in \mathcal{M}$ or $\perp ,$ succeeds when the decryptor’s attribute set $x^{\prime }$ satisfies the ciphertext policy.

The IND-CCA2 game adds an encryption oracle ${\mathcal{O}}_{\mathrm{enc}}$ absent from standard CP-ABE: since encryption requires a key, the adversary can query encryptions under keys it legitimately holds. The key oracle’s admissibility constraint — no queried ${\mathsf{sk}}_x$ with $f^{\ast }(x)=1$ — also bounds what the adversary can submit to ${\mathcal{O}}_{\mathrm{enc}}$.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{sym\text{-}cca2}}_{\ABE,\calA}(\secpar)$}
\begin{algorithmic}
\State $\msk \gets \Setup(1^\secpar)$; $b \getsr \bits$
\State $\calO_{\mathrm{key}}(x) := \KeyGen(\msk, x)$
\State $\calO_{\mathrm{enc}}(\sk_x, f, m) := \Enc(\sk_x, f, m)$
\Comment{$\sk_x$ must be a prior output of $\calO_{\mathrm{key}}$}
\State $\calO_{\mathrm{dec}}(\sk_x, c) := \Dec(\sk_x, c)$
\State $(f^*, m_0, m_1, \stA) \gets \calA^{\calO_{\mathrm{key}}, \calO_{\mathrm{enc}}, \calO_{\mathrm{dec}}}(1^\secpar)$
\Comment{$\calA$ may not have queried $\calO_{\mathrm{key}}(x)$ for $f^*(x) = 1$}
\State $\sk_{x_e} \gets \KeyGen(\msk, x_e)$
\Comment{Challenger-chosen $x_e \subseteq \calU$ with $f^*(x_e) = 1$}
\State $c^* \gets \Enc(\sk_{x_e}, f^*, m_b)$
\State $b' \gets \calA^{\calO_{\mathrm{key}}, \calO_{\mathrm{enc}}, \calO_{\mathrm{dec}}}(c^*, \stA)$
\Comment{No $\calO_{\mathrm{key}}(x)$ with $f^*(x) = 1$; no $\calO_{\mathrm{dec}}(\cdot, c^*)$}
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

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

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

is negligible.

Other results

• ABE ⇒ Fuzzy IBE
• ABE ⇒ HIBE
• ABE ⇒ BE
• 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
• BDH ⇒ ABE
• GGM ⇒ ABE
• BDH ⇒ ABE
• BDH ⇒ IBE
• BDH ⇒ ABE
• BDH ⇒ HIBE
• [[k-linear-assumption-to-abe-rw13|$k$-Linear assumption ⇒ ABE]]
• Hash function + PRF ⇒ Symmetric CP-ABE

Participates in

Builds on Attribute-based encryption

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

Produces Attribute-based encryption

• BDH ⇒ ABE
• Evasive LWE ⇒ ABE
• Evasive LWE ⇒ ABE
• GGM ⇒ ABE
• [[k-linear-assumption-to-abe-rw13|$k$-Linear assumption ⇒ ABE]]
• Succinct LWE ⇒ ABE

Barriers

• No reduction from IPPE to ABE