oblivious-transfer trapdoor hard-core-predicate
Updated Wed, 08 Jun 2022 19:29:52 GMT

Understanding Lindell's proof of (semi-honest) oblivous transfer

In Lindell's tutorial "How to simulate it" [2016/046], section 4.3, he gives a semi-honest protocol for oblivious transfer, based on enhanced trapdoor permutations and a corresponding hard-core predicate. I don't understand some details in the proof and hope somebody can explain it to me.

He gives the following definition: $B$ is a hard-core predicate of a trapdoor permutation $f_\alpha$ if:

for every non-uniform PPT adversary $A$ there exists a negligible function $\mu(n)$ such that for all $n$: $$ \Pr[A(1^n, \alpha, r) = B(\alpha, f_\alpha^{-1}(S(\alpha; r)))] \leq \frac{1}{2} + \mu(n), $$

where $\alpha$ is an index in the collection of functions $\{f_ \alpha\}$ and $S$ samples (almost uniformly) in the range/domain of $f_\alpha$.

Protocol 4.2 computes OT-functionality $((b_0,b_1), \sigma) \mapsto (\lambda, b_\sigma)$ as follows:

  • $P_1$ sends index $\alpha$ of a trapdoor function $f_\alpha$, where $P_1$ knows the trapdoor but $P_2$ does not.
  • $P_2$ samples random $x_\sigma$ and $y_{1-\sigma}$, computes $y_\sigma=f_\alpha(x_\sigma)$, and sends $(y_0, y_1)$.
  • $P_1$ uses the trapdoor to compute $x_0$ and $x_1$, then sends $B(\alpha, x_0) \oplus b_0$ and $B(\alpha, x_1) \oplus b_1$.
  • $P_2$ computes $B(\alpha, x_\sigma)$ and can therefore output $b_\sigma$.

Part of the proof of security (Theorem 4.3) constructs a simulator $S_2$ for corrupt party $P_2$ (the recipient), by showing that if you can distinguish the output of $S_2$ from that of $P_2$, you can use that to construct an algorithm $A$ that breaks the assumption that $B$ is a hard-core predicate, summarized as follows:

Algorithm $A$ [...] receives $(1^n, \alpha, r)$ for input. $A$'s aim is to guess $B(\alpha, S(\alpha; r))$.

However, there is no guessing because you can simply compute $B(\alpha, S(\alpha; r))$, right?

The final equation of the proof computes $\Pr[A(1^n, \alpha, r) = B(\alpha, x)]$, but it is unclear to me here what $x$ is in this expression (the preceding paragraph only mentions how to sample $x_\sigma$). Given the definition of the hard-core predicate, I would have expected to see $f_\alpha^{-1}$ in this part of the proof.


The answer is that it's me and not you. There was a typo in the proof and indeed $x$ referred to here is $f^{-1}_\alpha(S(\alpha,r))$. I have made the change in the proof and updated the ePrint paper. Thank you for pointing out the typo.

Comments (2)

  • +0 – Great! Thank you for writing the tutorial. I'm still going through it but so far it has been very helpful. — Apr 19, 2021 at 14:38  
  • +1 – You are most welcome! I am really glad that it's helpful. — Apr 19, 2021 at 14:43  

External Links

External links referenced by this document: