n-BDHE ⇒ BE

Fully-black-box reduction · standard model · BGW05 · security loss: tight up to a factor 2: one run of the adversary, whose advantage is at most twice the decision $n$-BDHE advantage

Statement

If the decision bilinear Diffie–Hellman exponent assumption with parameter $n$, a $q$-type variant of BDH, holds in a prime-order bilinear group, there is a public-key BE scheme for $n$ users, secure against any number of colluding revoked users, with $O(1)$-size ciphertexts and private keys and an $O(n)$-size public key. Security is selective (static in BGW05’s terms): the adversary commits to the target set before setup — BGW05.

Sketch

The public key is $v=g^{\gamma }$ together with the powers $g_i=g^{{\alpha }^i}$ for $i\in \{1,\dots ,2n\}\setminus \{n+1\}$, and user $i$ holds $d_i=g_i^{\gamma }$. A broadcast to $S$ has header $(g^t,(v{\prod }_{j\in S}{g}_{n+1-j}{)}^t)$ and session key $e(g_{n+1},g{)}^t$, which any $i\in S$ recovers from $d_i$ and the published powers although $g_{n+1}$ is never published. Given a decision $n$-BDHE instance $(g,h,g_1,\dots ,g_n,g_{n+2},\dots ,g_{2n},Z)$ and the committed target set $S^{\ast }$, the reduction sets $v=g^u/{\prod }_{j\in S^{\ast }}{g}_{n+1-j}$ for a uniform exponent $u$, which lets it compute $d_i$ for every $i\notin S^{\ast }$, and gives the adversary the challenge header $(h,h^u)$ with session key $Z$.

Notes

• Efficiency: the header is two group elements and a private key one, and decryption uses two pairings; a generalization trades header size against public-key size, making both $O(\sqrt{n})$ group elements — BGW05.