No fixed-construction reduction from IND-sHIBE-CPA Security (Selective) to IND-HIBE-CPA Security

Unconditional · against fixed-construction reductions · folklore

Statement

When the identity-vector space ${\Sigma }^{\le d}$ is superpolynomial, selective IND-sHIBE-CPA security of a HIBE scheme does not imply its adaptive IND-HIBE-CPA security, so the identity map is no reduction from selective to adaptive security: any selectively secure $\mathsf{HIBE}$ can be modified to output plaintexts in the clear for one identity vector drawn into its own $\mathsf{pp}$, which a selective adversary, committing before $\mathsf{Setup}$ runs, cannot anticipate — folklore.

Sketch

Given a selectively secure $\mathsf{HIBE}$, let ${\mathsf{HIBE}}^{\prime }$ run $\mathsf{Setup}$ and append a uniform $\vec{r}\in {\Sigma }^d$ to $\mathsf{pp}$; $\mathsf{Enc}(\mathsf{pp},\overrightarrow{id},m)$ outputs $m$ in the clear when $\overrightarrow{id}=\vec{r}$ and is unchanged otherwise. An adaptive adversary reads $\vec{r}$ from $\mathsf{pp}$, makes no key queries, and challenges on $\vec{r}$, winning with advantage $1$. A selective adversary commits to ${\overrightarrow{id}}^{\ast }$ before $\vec{r}$ is drawn and hits it with probability at most $|\Sigma {|}^{-d}$; otherwise its game is the selective game of $\mathsf{HIBE}$ with $\vec{r}$ sampled by the reduction, so ${\mathsf{HIBE}}^{\prime }$ stays selectively secure.

Notes

• Complexity leveraging recovers adaptive security only by guessing the challenge identity vector, at a loss of $|{\Sigma }^{\le d}|$, so its hypothesis is sub-exponential selective security, strictly stronger than selective security — folklore.
• For HIBE and ABE systems with a checkability property on keys and ciphertexts (any two different 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 loses a factor exponential in the hierarchy depth — LW14.
• An adaptively secure HIBE can be built from any selectively secure IBE, hence from the depth-1 restriction of any selectively secure HIBE — GKR25.