PRF ⇒ CPA-secure SKE

Fully-black-box reduction · standard model · BDJR97 · security loss: factor 2 in the PRF advantage, plus $O(\ell q^2/2^n)$ for $q$ encryptions of $\le \ell$ blocks

Statement

A PRF $\mathsf{PRF}=(\mathsf{KeyGen},\mathsf{Eval})$ with domain and range $\{0,1{\}}^n$ yields a CPA-secure SKE scheme via randomized counter mode: for $m_1,\dots ,m_{\ell }\in \{0,1{\}}^n$, $\mathsf{Enc}(k,m_1\cdots m_{\ell }):=\left(r,(\mathsf{Eval}(k,r+1)\Vert \cdots \Vert \mathsf{Eval}(k,r+\ell ))\oplus (m_1\Vert \cdots \Vert m_{\ell })\right)$ with a fresh $r\stackrel{\$}{\leftarrow }\{0,1{\}}^n$ per encryption and counters taken modulo $2^n$; $\mathsf{Dec}$ recomputes the pad from $r$ — BDJR97, who analyse it as their stateless XOR scheme, and its stateful variant, with concrete bounds in terms of the PRF advantage and the number of blocks encrypted.

Sketch

One hybrid per world replaces $\mathsf{Eval}(k,\cdot )$ by a uniformly random function; each pad block is then a fresh one-time pad unless the counter windows $[r+1,r+\ell ]$ of two encryptions overlap, a birthday event over $\{0,1{\}}^n$ of probability $O(\ell q^2/2^n)$ for $q$ encryptions.

Notes

• Efficiency: an $\ell$-block message costs $\ell$ PRF calls to encrypt or decrypt, and the ciphertext is one block, the nonce $r$, longer than the message — standard.