WE + PRG ⇒ PKE (GGSW)

Free reduction · standard model · GGSW13 · security loss: additive: the PKE advantage is at most twice the PRG advantage plus the witness-encryption advantage plus 2^{-λ}

Statement

Witness encryption for $\mathbf{NP}$ and a length-doubling PRG $G$ yield an IND-CPA-secure PKE scheme: the secret key is a seed $s$, the public key is $G(s)$, a ciphertext is $\mathsf{Enc}(1^{\lambda },x=G(s),m)$ for the statement ”$x$ is in the image of $G$”, and $s$ is the decryption witness — GGSW13.

Sketch

Replace the public key by a uniform string $u$, which the adversary cannot notice by PRG security. With probability at least $1-2^{-\lambda }$, $u$ is outside the image of $G$, a false statement, so soundness security of the witness encryption hides the message — GGSW13.