PSI ⇒ OT
Statement
Let be a non-degenerate PSI protocol, that is, a semi-honest secure PSI protocol for a universe with and size bounds and , where a pair of bits is read as an element of by padding. The following is a 1-out-of-2 OT with message space , with the reference string of , that has sender privacy and receiver privacy: on inputs and , the parties run with sender set and receiver set , and the receiver outputs if its output set contains and otherwise — folklore.
Sketch
is if and otherwise, so a -correct PSI protocol gives a -correct OT. The sender’s view is simulatable from , which does not depend on , and the receiver’s view from , which depends on the sender’s pair only through — standard.
Notes
- The construction needs the intersection to go to the receiver alone: in two-sided PSI the sender also learns , which reveals unless — folklore.
- Conversely, semi-honest OT gives semi-honest PSI, through semi-honest secure computation of every functionality (semi-honest OT ⇒ semi-honest MPC, semi-honest 2PC ⇒ PSI) — GMW87, Gol04.