Semi-honest 2PC + PRF ⇒ OPRF

Free reduction · standard model · folklore · security loss: none

Statement

Let be a PRF with key space and domain for polynomials and , and a protocol that securely computes the functionality against semi-honest adversaries, which exists when semi-honest 2PC is achieved. Then is a semi-honest secure OPRF — folklore.

Sketch

is efficient and its inputs have fixed polynomial lengths, so is a polynomial-time functionality and has a protocol; for each corrupted party, the OPRF’s semi-honest security game is the semi-honest 2PC game for , and pseudorandomness is the hypothesis on — standard.

Notes

  • Every PRF gives one of this form: re-keying by the coins of , for with the number of coins uses, leaves the PRF game unchanged and gives key space , and restricting the domain to for a polynomial preserves pseudorandomness — folklore.
  • With , and secure with abort against a malicious adversary corrupting one party (2PC), the same construction gives an OPRF with malicious security (2PC + PRF ⇒ malicious OPRF) — folklore.
  • Conversely, an OPRF with a group range gives semi-honest OT (OPRF ⇒ OT) — folklore — and semi-honest OT gives semi-honest secure computation of every functionality (semi-honest OT ⇒ semi-honest MPC) — GMW87, Gol04.