BDH ⇒ ABE

Fully-black-box reduction · standard model · GPSW06 · security loss: tight up to a factor 2: one run of the selective adversary, whose advantage is at most twice the DBDH advantage

Statement

If decisional bilinear Diffie–Hellman (DBDH) holds, there is a key-policy ABE for monotone access structures (monotone Boolean formulas or LSSS) that is selectively KP-IND-CPA-secure: the adversary commits to the challenge attribute set before $\mathsf{Setup}$ runs — GPSW06.

Sketch

$\mathsf{Setup}$ publishes $e(g,g{)}^y$ and per-attribute elements $T_i=g^{t_i}$; a key for an access structure secret-shares $y$ over its leaves, and a ciphertext for attribute set $\gamma$ blinds the message by $e(g,g{)}^{ys}$ alongside $T_i^s$ for $i\in \gamma$. The selective reduction embeds a DBDH challenge $(g^a,g^b,g^c,Z)$ as $y=ab$, $s=c$, simulates keys for structures unsatisfied by the committed ${\gamma }^{\ast }$, and outputs the adversary’s guess as its decision on $Z=e(g,g{)}^{abc}$.

Notes

• The ciphertext-policy counterpart, selectively secure CP-ABE for monotone formulas in the standard model, has ciphertext size linear in the formula under decisional $q$-parallel BDHE; a less efficient scheme rests on DBDH — Wat11.
• In the small-universe construction a ciphertext for attribute set $\gamma$ is one element of ${\mathbb{G}}_T$ and $|\gamma |$ elements of $\mathbb{G}$, a key has one element of $\mathbb{G}$ per leaf of its access structure, and the public parameters have one element of $\mathbb{G}$ per attribute of the universe and one of ${\mathbb{G}}_T$ — GPSW06.