TDP ⇒ PKE

Fully-black-box reduction · standard model · GM84 · security loss: factor $\ell$ over the hard-core-bit advantage for $\ell$-bit messages, from the hybrid over bit positions, tight for one bit; with the Goldreich–Levin predicate, a predictor of advantage $\epsilon$ gives an inverter succeeding with probability $\Omega (\epsilon )$ in time $\mathrm{poly}(n,1/\epsilon )$ for $n$-bit inputs

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$.
• Efficiency: for a hard-core predicate $b$, bit-by-bit encryption sends $(f(x),b(x)\oplus m)$ per plaintext bit, one element of $\mathcal{D}$ and one bit, at one evaluation of $f$. Iterating $f$ as in the Blum–Micali–Yao generator encrypts an $\ell$-bit message as $(f^{\ell }(x),m\oplus (b(x),b(f(x)),\dots ,b(f^{\ell -1}(x))))$, one element of $\mathcal{D}$ plus $\ell$ masked bits, with $\ell$ evaluations to encrypt and $\ell$ inversions to decrypt. With the Goldreich–Levin predicate $⟨x,r⟩$ the public string $r$ is sent as well, $2n+\ell$ bits in all for an $n$-bit domain — standard.