Sub-exponential IND-sID-CPA Security ⇒ IND-ID-CPA Security

Fully-black-box reduction · standard model · BB04b · security loss: multiplicative $|\mathcal{I}|$

Statement

For an IBE scheme with identity space $\mathcal{I}$, every efficient adaptive (IND-ID-CPA) adversary with advantage $\delta$ yields a selective (IND-sID-CPA) adversary of similar size with advantage $\delta /|\mathcal{I}|$ (complexity leveraging) — BB04b. Hence a sub-exponentially IND-sID-CPA-secure IBE, with constant $ϵ>0$, yields an IND-ID-CPA-secure IBE: run it at security parameter ${\lambda }^{\prime }=\lceil {\lambda }^{2/ϵ}\rceil$ with identities restricted to $\{0,1{\}}^{\lambda }$, padded to ${\lambda }^{\prime }$ bits. A polynomial-size adaptive adversary with advantage $\delta$ gives a selective adversary of size below $2^{{\lambda }^{\prime ϵ}}$ for large $\lambda$, with advantage $\delta /2^{\lambda }\le 2^{-{\lambda }^{\prime ϵ}}\le 2^{-{\lambda }^2}$, so $\delta \le 2^{\lambda -{\lambda }^2}$ — folklore. A merely negligible selective advantage does not suffice, since the identity space has at least $2^{\lambda }$ elements.

Sketch

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

Notes

• The HIBE analogue loses the number $|{\Sigma }^{\le d}|$ of identity vectors (Sub-exponentially selective HIBE ⇒ adaptive HIBE) — folklore.