Selective-ID IBE ⇒ CCA-secure PKE (CHK)

Fully-black-box reduction · standard model · CHK04 · security loss: additive: the CCA advantage is at most the selective-ID IBE advantage plus the strong one-time unforgeability advantage, plus the target-collision advantage when verification keys are hashed

Statement

An IND-sID-CPA-secure IBE scheme, combined with a strongly unforgeable one-time signature scheme whose verification keys, hashed into $\{0,1{\}}^{\lambda }$ by a target-collision-resistant hash when longer, are identities, yields an IND-CCA2-secure PKE scheme — CHK04. The public key is the IBE master public key. To encrypt $m$, sample a one-time key pair $(\mathsf{vk},{\mathsf{sk}}_{\mathrm{ots}})$, encrypt $c\leftarrow \mathsf{Enc}(mpk,H(\mathsf{vk}),m)$ to the identity $H(\mathsf{vk})$, with $H$ the identity map when $\mathsf{vk}\in \{0,1{\}}^{\lambda }$ and otherwise a target-collision-resistant hash keyed in the public key, and output $(\mathsf{vk},c,\mathsf{Sign}({\mathsf{sk}}_{\mathrm{ots}},c))$; decryption verifies the signature, extracts the key for identity $H(\mathsf{vk})$ and decrypts $c$.

Sketch

The reduction samples the challenge’s ${\mathsf{vk}}^{\ast }$ first and declares $H({\mathsf{vk}}^{\ast })$ as its selective target identity. It answers a decryption query $(\mathsf{vk},c,\sigma )$ with $H(\mathsf{vk})\ne H({\mathsf{vk}}^{\ast })$ by extracting the key for $H(\mathsf{vk})$; a valid query with $\mathsf{vk}={\mathsf{vk}}^{\ast }$ and $(c,\sigma )$ different from the challenge’s is a strong one-time forgery, and one with $\mathsf{vk}\ne {\mathsf{vk}}^{\ast }$ and $H(\mathsf{vk})=H({\mathsf{vk}}^{\ast })$ is a target collision. The challenge then embeds the IBE challenge for identity $H({\mathsf{vk}}^{\ast })$ — CHK04.

Notes

• The identity space must be super-polynomial: with polynomially many identities, an adversary samples one-time key pairs until one maps to the challenge identity, re-signs the challenge ciphertext and has it decrypted — standard.
• Strongly unforgeable one-time signatures exist given one-way functions, which IBE implies through IBE ⇒ PKE — Gol04.
• With BB04’s selective-ID IBE under the decisional bilinear Diffie–Hellman assumption, the transform gives IND-CCA2 PKE from pairings without random oracles — BB04b, CHK04.
• Efficiency: one one-time key generation and signature per ciphertext, and the ciphertext grows by a verification key and a signature. Replacing the signature by a MAC and a commitment shortens ciphertexts — BCHK07.