NIKE ⇒ PKE

Fully-black-box reduction · standard model · folklore · security loss: tight: one NIKE challenge per run of the CPA adversary

Statement

Let $(\mathsf{Gen},\mathsf{Combine})$ be a NIKE with key space $\mathcal{K}=\{0,1{\}}^{\ell }$ whose shared key is indistinguishable from uniform given both honestly generated public keys. Then $\mathsf{KeyGen}:=\mathsf{Gen}$, $\mathsf{Enc}(\mathsf{pk},m):=({\mathsf{pk}}^{\prime },\mathsf{Combine}({\mathsf{sk}}^{\prime },\mathsf{pk})\oplus m)$ for fresh $({\mathsf{pk}}^{\prime },{\mathsf{sk}}^{\prime })\leftarrow \mathsf{Gen}(1^{\lambda })$, and $\mathsf{Dec}(\mathsf{sk},({\mathsf{pk}}^{\prime },c)):=\mathsf{Combine}(\mathsf{sk},{\mathsf{pk}}^{\prime })\oplus c$ is an IND-CPA-secure PKE with $\mathcal{M}=\{0,1{\}}^{\ell }$ — folklore.

Sketch

Correctness is NIKE correctness. Given a NIKE challenge $(\mathsf{pk},{\mathsf{pk}}^{\prime },k)$, the reduction gives $\mathcal{A}$ the public key $\mathsf{pk}$ and the challenge ciphertext $({\mathsf{pk}}^{\prime },k\oplus m_b)$ for its own bit $b$, and outputs $[b^{\prime }=b]$: for the real shared key this is the CPA game, and for uniform $k$ the ciphertext is independent of $b$.

Notes

• Instantiated with Diffie–Hellman, with $\oplus$ replaced by the group operation, the construction is ElGamal encryption (DDH ⇒ PKE) — ElGamal85.
• The same construction works from any two-message key exchange, with the initiator’s message as the public key — folklore.