Sub-exponentially selective HIBE ⇒ adaptive HIBE

Fully-black-box reduction · standard model · folklore · security loss: multiplicative $|{\Sigma }^{\le d}|$

Statement

Every sub-exponentially IND-sHIBE-CPA-secure HIBE scheme, with constant $ϵ>0$, is IND-HIBE-CPA-secure whenever $|{\Sigma }^{\le d}|\cdot 2^{-{\lambda }^{ϵ}}$ is negligible: an adaptive adversary with advantage $\delta$ yields a selective adversary of similar size with advantage $\delta /|{\Sigma }^{\le d}|$ (complexity leveraging) — folklore.

Sketch

The reduction samples ${\overrightarrow{id}}^{\prime }\stackrel{\$}{\leftarrow }{\Sigma }^{\le d}$, commits to it as its selective challenge and runs the adaptive adversary, forwarding extraction queries and aborting with a random bit if the adversary queries a prefix of ${\overrightarrow{id}}^{\prime }$ or challenges on another vector. The guess is independent of the adversary’s view, so it equals the adversary’s challenge with probability $1/|{\Sigma }^{\le d}|$, and then the admissible adversary never triggers an abort; the reduction’s advantage is the adversary’s divided by $|{\Sigma }^{\le d}|$.

Notes

• Polynomial selective security does not suffice: when ${\Sigma }^{\le d}$ is superpolynomial, IND-sHIBE-CPA security of a scheme does not imply its IND-HIBE-CPA security (No fixed-construction reduction from IND-sHIBE-CPA to IND-HIBE-CPA security) — folklore.
• The IBE analogue loses the size $|\mathcal{I}|$ of the identity space (Sub-exponential IND-sID-CPA ⇒ IND-ID-CPA security) — BB04.