2PC + PRF ⇒ Malicious 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 with abort against a malicious adversary corrupting one party, which exists when 2PC is achieved. Then is an OPRF with malicious security — folklore.

Sketch

is efficient and its inputs have fixed polynomial lengths, so is a polynomial-time functionality and has a protocol. An input that the simulator substitutes for a corrupted party in the ideal execution of is a string of length or , so it lies in or as the malicious OPRF’s ideal execution requires, and malicious security of the OPRF is security with abort of that protocol for , together with pseudorandomness of , which is the hypothesis — standard.

Notes

  • The construction needs the key space and domain to contain every string of their lengths: a corrupted party may hand the trusted party of the 2PC ideal execution any string of the input length, while the malicious OPRF’s ideal execution admits only and . For a PRF with for some , a corrupted server that inputs makes the client output — folklore.
  • Every PRF whose domain contains for a polynomial 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 , e.g. for , preserves pseudorandomness — folklore.
  • A semi-honest 2PC protocol run on in place of gives a semi-honest secure OPRF (semi-honest 2PC + PRF ⇒ OPRF) — folklore.