PKE ⇒ OWF

Fully-black-box reduction · standard model · IL89 · security loss: polynomial; tight for a perfectly correct scheme, where one inversion yields a secret key that decrypts the challenge

Statement

If a CPA-secure PKE scheme exists, so does a one-way function — IL89. This is an instance of IL89’s theorem that private-key encryption, identification, commitment and coin flipping each require one-way functions.

Sketch

For a perfectly correct scheme, $f(r):=\mathsf{pk}$ where $(\mathsf{sk},\mathsf{pk})=\mathsf{KeyGen}(1^{\lambda };r)$ is one-way: an inverter returns $r^{\prime }$ with $\mathsf{KeyGen}(1^{\lambda };r^{\prime })=({\mathsf{sk}}^{\prime },\mathsf{pk})$, and perfect correctness makes ${\mathsf{sk}}^{\prime }$ decrypt every ciphertext under $\mathsf{pk}$, so the reduction decrypts the CPA challenge. IL89’s general argument uses distributional inverters and does not need perfect correctness.

Notes

• The converse has no relativizing proof: relative to a random permutation with a $\mathbf{PSPACE}$-complete oracle, one-way functions exist and PKE does not (No relativizing reduction from OWF to PKE) — IR89.