OPRF ⇒ OT

Fully-black-box reduction · standard model · folklore

Statement

Let be a semi-honest secure OPRF, , whose domain contains two distinct points and whose range is a finite group with and efficiently computable operation and inverse, written additively. 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 sender samples , the parties run with server input and client input , the sender sends , and the receiver subtracts its OPRF output from the -th entry — folklore.

Sketch

A -correct OPRF gives a -correct OT. The sender’s view consists of , the coins it used to sample , and its OPRF view; the OPRF view and the reference string can be replaced by the simulator’s output on , which is independent of , so the view is independent of up to the OPRF advantage. The receiver’s OPRF view and the reference string can be replaced by the simulator’s output on ; then is pseudorandom given by PRF security for , and masks as a one-time pad — standard.

Notes