No fixed-construction reduction from selective to adaptive CP-ABE security

Unconditional · against fixed-construction reductions · folklore

Statement

Selective security of a CP-ABE scheme does not imply its adaptive CP-IND-CPA security when the scheme supports a superpolynomial-size family ${\mathcal{F}}^{\prime }$ of policies: any selectively secure $\mathsf{ABE}$ can be modified into a scheme ${\mathsf{ABE}}^{\prime }$ that is still selectively secure but not CP-IND-CPA-secure — folklore. The construction ruled out is the identity map (selective security of a scheme implying adaptive security of the same scheme); building a different adaptively secure CP-ABE scheme from a selectively secure one is not ruled out.

Sketch

${\mathsf{ABE}}^{\prime }$ runs $\mathsf{Setup}$ and appends $f_r\stackrel{\$}{\leftarrow }{\mathcal{F}}^{\prime }$ to $\mathsf{pp}$; $\mathsf{Enc}(\mathsf{pp},f,m)$ outputs $m$ in the clear when $f=f_r$ and is unchanged otherwise. An adaptive adversary reads $f_r$ from $\mathsf{pp}$, makes no key queries, and challenges on $f_r$, winning with advantage $1$. A selective adversary commits to $f^{\ast }$ before $f_r$ is drawn, so $f^{\ast }=f_r$ with probability $1/|{\mathcal{F}}^{\prime }|$; otherwise the game is the selective game of $\mathsf{ABE}$, with $f_r$ sampled by the reduction, so ${\mathsf{ABE}}^{\prime }$ stays selectively secure.

Notes

• Complexity leveraging recovers adaptive security only by guessing $f^{\ast }$, at a loss of the number of admissible challenge policies, and so needs selective security against correspondingly small advantage — folklore.
• The KP-ABE analogue puts a uniformly random attribute set $x_r\subseteq \mathcal{U}$ in $\mathsf{pp}$ and needs $2^{|\mathcal{U}|}$ superpolynomial; leveraging there loses $2^{|\mathcal{U}|}$ — folklore.
• For HIBE and ABE systems with a checkability property on keys and ciphertexts (any two private keys that are both supposed to decrypt a ciphertext decrypt it to the same message), any simple black-box reduction to a non-interactive assumption suffers an exponential degradation of security — LW14.