Sub-exponentially selective HIBE ⇒ adaptive HIBE

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

Statement

For an HIBE scheme, an adaptive adversary with advantage $\delta$ yields a selective adversary of similar size with advantage $\delta /|{\Sigma }^{\le d}|$ (complexity leveraging) — folklore. Hence a sub-exponentially IND-sHIBE-CPA-secure HIBE, with constant $ϵ>0$, yields an IND-HIBE-CPA-secure HIBE for every depth $d\le \lambda /2$: run it at security parameter ${\lambda }^{\prime }=\lceil {\lambda }^{2/ϵ}\rceil$ with alphabet restricted to $\{0,1{\}}^{\lambda }$, padded to ${\lambda }^{\prime }$ bits, so that $|{\Sigma }^{\le d}|\le 2^{\lambda d+1}$ and a polynomial-size adaptive adversary has advantage at most $2^{\lambda d+1-{\lambda }^2}\le 2^{1-{\lambda }^2/2}$ — 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) — BB04b.