Overview

Attribute-based encryption

Public-key encryption in which a secret key decrypts a ciphertext exactly when a policy attached to one of them accepts the attributes attached to the other, even against colluding key holders.

What it is

An attribute-based encryption (ABE) scheme for a predicate $P$ has four algorithms. Setup, run by an authority, outputs a master public key and a master secret key. KeyGen uses the master secret key to issue a key for a value $y$ . Encrypt uses only the master public key to encrypt a message under a value $x$ . Decryption with the key for $y$ recovers the message whenever $P (x, y) = 1$ . Security requires that an adversary holding keys for any polynomial number of values $y_{1}, \dots, y_{q}$ , none satisfying $P (x^{*}, y_{i}) = 1$ , learns nothing about a message encrypted under the challenge $x^{*}$ . The value $x$ itself is public; hiding it is the stronger goal of predicate encryption. ABE grew out of fuzzy identity-based encryption ().

Core notions

KP-ABE and CP-ABE: in key-policy ABE the key carries the policy and the ciphertext carries attributes (); in ciphertext-policy ABE the roles are swapped ().
Policy class: threshold gates; Boolean formulas and monotone span programs, written as linear secret-sharing (LSSS) matrices; arithmetic branching programs (ABPs); $NC^{1}$ ; bounded-depth and unbounded-depth circuits; finite automata; Turing or RAM machines.
Collusion resistance: holders of unauthorized keys cannot combine them to decrypt. Standard ABE requires this for an unbounded number of keys.
Selective, semi-adaptive, adaptive: the adversary fixes the challenge attribute or policy before seeing the public key (selective), after the public key but before any key query (semi-adaptive), or at challenge time after adaptive key queries (adaptive, or full, security).
Universe and unboundedness: a small-universe scheme fixes a polynomial-size attribute set at setup; a large-universe scheme accepts arbitrary strings. "Unbounded" can refer independently to the universe, the attribute length, the policy size, or the circuit depth. Multi-use schemes let one attribute label several policy rows.
Succinctness: how public-key, secret-key, and ciphertext sizes grow with attribute length, policy size, and depth; "constant" means $poly (λ)$ in the security parameter $λ$ only.
Model and assumption: standard model, random-oracle model (ROM), or generic bilinear group model (GGM); static assumptions (k-Lin, LWE) versus q-type assumptions or strengthened LWE variants (succinct, evasive, circular).
Authority model: one central authority; multi-authority ABE, where independent authorities issue keys for their own attributes (); or registered ABE, where users generate their own keys and a transparent, secret-free aggregation step builds the public key ().

Main approaches

Pairing-based secret sharing: the master secret is shared along the policy and recovered in the target group. Expressive LSSS schemes are selective under q-type assumptions (); and target concrete efficiency in the GGM with random oracles.
Dual system encryption: semi-functional keys and ciphertexts give adaptive security under static assumptions, first in composite-order groups (), then through pair encodings () and prime-order predicate encodings (). gives adaptively secure $NC^{1}$ ABE from k-Lin.
Lattice key-homomorphic encodings: bounded-depth circuit ABE from LWE (, ), semi-adaptive with unbounded attribute length (), and adaptive for t-CNF policies with constant t (). Succinct LWE gives short keys and ciphertexts together (, ). Witness encryption gives a separate adaptive route ().
Reduced trust: lattice multi-authority ABE (, ) and registered ABE (, , ).

Notation used in the comparison table

Parameters below occur in efficiency or security bounds. Each meaning is scoped to its stated regime. Measured quantities are named in words; protocol objects are defined where used. Source aliases do not equate different regimes.

The numeric machine identifier I continues to count |I| rows; the set I is defined locally. Machine construction identifiers are unchanged.

Symbol	Meaning	Regime	Paper aliases
λ	Computational security parameter.	All ABE families.	writes λ
m	Number of attributes in the set carried by a key (CP-ABE) or a ciphertext (KP-ABE).	Set-based ABE only.	writes T
U	Cardinality of the finite attribute universe; distinct from attribute-vector length.	Small-universe ABE.	writes n; writes \|U\|
n₁	Number of LSSS matrix rows, or access-tree leaves.	Linear secret-sharing policies.	writes n₁; writes ℓ
n₂	Number of columns of the LSSS matrix.	Linear secret-sharing policies.	writes n₂; writes n
\|I\|	Number of satisfying LSSS rows used in reconstruction; the row-index set is defined in the surrounding text.	LSSS decryption.	writes I; writes I
τ	Largest number of LSSS rows labelled by one attribute.	Multi-use LSSS policies.	writes τ
ℓ	Attribute-vector or input-string length; the number of coordinates, not Hamming weight.	Vector, circuit, and automaton inputs.	writes ℓ; writes ℓ; writes n; writes n; writes ℓ; writes \|x\|; writes \|x\|; writes L; writes L; writes n
\|Q\|	Number of states of a finite automaton.	ABE for DFA and NFA.	writes \|Q\|; writes \|Γ\|
d	Circuit or formula depth bound.	Circuit/formula ABE; gate convention must be stated.	writes d; writes D
s	Circuit size in the source gate model.	Circuit ABE.	writes \|C\|; writes N
M	Bound on the magnitude of intermediate values of an arithmetic circuit.	Arithmetic-circuit ABE from evasive LWE.	writes M
B	Digit base of the lookup tables.	Lookup-table lattice ABE.	writes B
p	Prime order of the pairing groups.	Pairing-based ABE; generic-group security bounds.	writes p; writes p; writes p
k	Parameter of the k-Lin assumption.	Pairing-based assumption families.	No paper spelling asserted.
𝔾₁	The first source group of an asymmetric (Type III) pairing e:𝔾₁ × 𝔾₂ → 𝔾_T; \(	\mathbb{G}_1	\) is the size of one element in bits.	Type III pairing-based ABE, and Type I schemes counted in a Type III port a paper states.	writes 𝔾
𝔾₂	The second source group of an asymmetric (Type III) pairing; \(	\mathbb{G}_2	\) is the size of one element, larger than \(	\mathbb{G}_1	\) on the usual curves.	Type III pairing-based ABE.	writes ℍ
𝔾_T	The target group of the row's pairing; \(	\mathbb{G}_T	\) is the size of one element.	Pairing-based ABE.	No paper spelling asserted.
𝔾	The source group of a symmetric (Type I) pairing e:𝔾 × 𝔾 → 𝔾_T of prime order p, for a scheme no paper ports to Type III; \(	\mathbb{G}	\) is the size of one element.	Type I pairing-based ABE without a stated Type III port.	No paper spelling asserted.
𝔾_N	The source group of a composite-order pairing, of order a product of primes; \(	\mathbb{G}_N	\) is the size of one element.	Composite-order ABE without a stated prime-order port.	No paper spelling asserted.
ℤ_p	Exponents modulo the group order p; \(	\mathbb{Z}_p	\) is the size of one.	Pairing-based ABE.	No paper spelling asserted.
ℤ_N	Exponents modulo the composite order N of a composite-order pairing; \(	\mathbb{Z}_N	\) is the size of one.	Composite-order ABE.	No paper spelling asserted.
n	LWE secret dimension.	Lattice ABE.	writes n
q	LWE or ciphertext modulus.	Lattice ABE.	writes q
ℤ_q	Integers modulo q; \(	\mathbb{Z}_q	\) is the size of one.	Lattice ABE.	No paper spelling asserted.
m̄	Width of the lattice matrices: the number of columns of a public matrix such as A ∈ ℤn×m̄q, of order n log q at least.	Lattice ABE; written apart from m, the attributes in a set.	writes m; writes m; writes m; writes m
R_q	The ring ℤ_q[X]/(Xⁿ + 1) of degree n; \(	\mathcal{R}_q	\) is one element at full width, n⌈log₂ q⌉ bits.	Ring-LWE ABE.	writes R_q

This topic covers ABE and relatives that change its trust model or functionality: multi-authority and registered ABE, distributed monotone-policy and broadcast encryption, and multi-input ABE. Predicate and functional encryption appear only where they supply a construction route or a barrier.

New to the area? Start here

Vipul Goyal, Omkant Pandey, Amit Sahai, Brent Waters · ACM CCS 2006
John Bethencourt, Amit Sahai, Brent Waters · IEEE Symposium on Security and Privacy 2007
Brent Waters · PKC 2011
Allison Lewko, Tatsuaki Okamoto, Amit Sahai, Katsuyuki Takashima, Brent Waters · EUROCRYPT 2010
Sergey Gorbunov, Vinod Vaikuntanathan, Hoeteck Wee · STOC 2013
Susan Hohenberger, George Lu, Brent Waters, David Wu · EUROCRYPT 2023