Enhanced trapdoor permutations ⇒ OT

Fully-black-box reduction · standard model · EGL85 · security loss: polynomial: receiver privacy is statistical, and a sender-privacy distinguisher with advantage $\epsilon$ predicts the hard-core bit of an obliviously sampled image, from which the Goldreich–Levin decoder inverts the permutation with probability $\Omega (\epsilon )$ in time $\mathrm{poly}(\lambda ,1/\epsilon )$

Statement

An enhanced trapdoor permutation yields 1-out-of-2 OT on bits secure against semi-honest parties, via the EGL protocol: the sender, holding $(x_0,x_1)$, samples $(f,\mathsf{td})\leftarrow \mathsf{Gen}(1^{\lambda })$ and sends $f$; the receiver, holding $c$, picks $z\stackrel{\$}{\leftarrow }\mathcal{D}$, sets $y_c=\mathsf{Eval}(f,z)$, samples $y_{1-c}$ obliviously from the domain, and sends $(y_0,y_1)$; the sender returns $x_b\oplus h(\mathsf{Invert}(\mathsf{td},y_b))$ for $b\in \{0,1\}$, where $h$ is a hard-core predicate, and the receiver unmasks $x_c$ with $h(z)$ — EGL85. Enhanced one-wayness ($f$ stays hard to invert on an obliviously sampled $y$ even given the sampling coins) keeps $x_{1-c}$ hidden from the receiver, who holds those coins — Gol04.

Sketch

Receiver privacy is statistical: $(y_0,y_1)$ are two independent uniform domain elements, up to the sampler’s statistical error, whatever $c$ is. Sender privacy: predicting $h(f^{-1}(y_{1-c}))$ from the sampling coins of $y_{1-c}$ is predicting a hard-core bit of an obliviously sampled image, and the Goldreich–Levin decoder turns such a predictor into an inverter, contradicting enhanced one-wayness.

Notes

• Gol04 introduces enhanced one-wayness; for a TDP whose domain sampler’s coins reveal a preimage, the protocol is insecure — Gol04.
• Enhanced TDPs suffice for EGL OT, while NIZK needs doubly enhanced TDPs; intermediate notions are separated — GR13.