OPRF ⇒ PSI
Statement
Let be an OPRF with super-polynomial range: a semi-honest secure, -correct OPRF, , whose domain contains for a polynomial , whose range has negligible, and whose collision bound is negligible. For every pair of polynomial size bounds and , in particular for and , the following is a semi-honest secure PSI protocol for and size bounds and , and hence a non-degenerate one, with reference string made of independent reference strings of : the sender samples ; for the -th element of the parties run on with server input and client input , and the receiver obtains ; the sender sends the sorted list of the values for and outputs the number of executions of ; the receiver outputs — folklore.
Sketch
Correctness fails only if one of the at most executions of errs or for one of the at most pairs , , so by a union bound it fails with probability at most , where is the correctness of . For a corrupted receiver, each OPRF view is replaced by the OPRF simulator’s output on , after which is used only at points of and can be replaced by a random function, whose values on are uniform and independent of the rest, so the view is simulatable from . For a corrupted sender, each OPRF view is replaced by the simulator’s output on , jointly with the receiver’s OPRF outputs , and the receiver then outputs except on the same collision event, of probability at most since the sets are fixed before is sampled — standard.
Notes
- HL08 base set intersection on secure evaluation of a pseudorandom function, with one protocol secure against malicious adversaries under a relaxed definition (simulatable when one party is corrupted, only private in an indistinguishability sense when the other is) and one fully simulatable against covert adversaries, and JL09 obtain set intersection secure against malicious adversaries from an OPRF for the Dodis–Yampolskiy PRF.
- An OPRF with a group range also gives semi-honest OT directly (OPRF ⇒ OT) — folklore.