OWF + iO ⇒ PKE

Free reduction · standard model · SW14 · security loss: additive: at most twice the sum of the PRG, iO and punctured-PRF advantages, one hybrid each, and $2^{-\lambda }$ for a uniform $t^{\ast }$ in the PRG’s image, with the PRG and the punctured PRF built from the one-way function at a polynomial loss

Statement

iO for all polynomial-size circuits together with a one-way function implies IND-CPA-secure PKE — SW14.

Sketch

The secret key is a puncturable PRF key $K$; the public key is an obfuscation of the program $(m,r)\mapsto (t,F(K,t)\oplus m)$ with $t=\mathsf{PRG}(r)$. The proof replaces $t^{\ast }$ by a uniform string, which lies outside the PRG’s image with overwhelming probability, punctures $K$ at $t^{\ast }$ — the punctured program agrees with the original on every input, so iO hides the switch — and applies pseudorandomness at the punctured point.

Notes

• The same punctured-programs technique also gives IND-CCA-secure PKE — SW14.
• Efficiency: a ciphertext is $2\lambda$ bits longer than the message — SW14.