TDP ⇒ PKE

Fully-black-box reduction · standard model · GM84

Statement

A family of trapdoor permutations $f$ with hard-core predicate $b$ gives a CPA-secure PKE scheme: $\mathsf{pk}$ is the permutation index, $\mathsf{sk}$ its trapdoor, a bit $m$ is encrypted as $\mathsf{Enc}(\mathsf{pk},m)=(f(x),b(x)\oplus m)$ for $x\stackrel{\$}{\leftarrow }\mathcal{D}$, and longer messages bit by bit — GM84, Yao82a. A hard-core predicate need not be assumed: for every trapdoor permutation $f$, $g(x,r)=(f(x),r)$ is a trapdoor permutation with hard-core predicate $⟨x,r⟩\mathrm{mod}2$ — GL89.

Sketch

Decryption recovers $x=\mathsf{Invert}(\mathsf{sk},c_1)$ and outputs $c_2\oplus b(x)$. A CPA adversary distinguishing encryptions of $0$ from encryptions of $1$ predicts $b(x)$ from $f(x)$ with the same advantage, contradicting hard-coreness of $b$; a hybrid over bit positions covers longer messages.

Notes

• Yao82a states the construction for trapdoor functions with a hard bit, decryption recovering the encryption randomness $x$.