PRC ⇒ SKE

Fully-black-box reduction · standard model · CG24 · security loss: CPA advantage at most twice the PRC pseudorandomness advantage (one hybrid per world)

Statement

An $L$-bit PRC $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ is an SKE scheme with message space $\{0,1{\}}^L$ and ciphertext space $\{0,1{\}}^n$: robustness against the identity channel gives $(1-\mathrm{negl}(\lambda ))$-correctness, and PRC pseudorandomness is IND$-CPA security, which implies CPA security — CG24.

Sketch

In each world of the CPA game, one pseudorandomness hybrid replaces the answers ${\mathsf{Enc}}_k(m_b)$ by uniform $n$-bit strings; the oracle then ignores its input, so $b$ is information-theoretically hidden.