Bilinear pairing ⇒ CP-ABE

Free reduction · generic group model · BSW07

Statement

In a bilinear group, the Bethencourt–Sahai–Waters scheme is a ciphertext-policy ABE whose policies are monotone trees of threshold gates over attributes, which are arbitrary strings hashed into the group. It is CP-IND-CPA-secure against adversaries that are generic in the bilinear group, with the hash modeled as a random oracle — BSW07.

Sketch

The scheme masks the message by $e(g,g{)}^{\alpha s}$ and secret-shares $s$ down the access tree, each leaf $y$ carrying $g^{q_y(0)}$ and $H(\mathrm{att}(y){)}^{q_y(0)}$ for its share $q_y(0)$; a key for an attribute set $S$ is $D=g^{(\alpha +r)/\beta }$ together with $g^{r}H(j{)}^{r_j}$ and $g^{r_j}$ for each $j\in S$, under one fresh $r$. Pairing $D$ with $h^s=g^{\beta s}$ gives $e(g,g{)}^{(\alpha +r)s}$ and leaf pairings give $e(g,g{)}^{r{q}_y(0)}$; the generic group analysis shows that $e(g,g{)}^{rs}$ can be cancelled only by interpolating such leaf terms of a single key whose attributes satisfy the tree, so colluding users cannot pool their attributes.

Notes

• A ciphertext under an access tree with leaf set $Y$ consists of $2|Y|+1$ source-group elements and one target-group element, a key for $S$ of $2|S|+1$ source-group elements, and decryption costs two pairings per leaf used to satisfy the tree plus one — BSW07.
• Selectively secure CP-ABE for monotone formulas exists in the standard model under the non-interactive decisional $q$-parallel BDHE assumption, and less efficiently under DBDH — Wat11.