PSI ⇒ OT

Fully-black-box reduction · standard model · folklore · security loss: a factor of 2

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