Efficient Batched Oblivious PRF with Applications to Private Set Intersection

We describe a lightweight protocol for oblivious evaluation of a pseudorandom function (OPRF) in the presence of semihonest adversaries. In an OPRF protocol a receiver has an input r; the sender gets output s and the receiver gets output F( s; r), where F is a pseudorandom function and s is a random seed. Our protocol uses a novel adaptation of 1-out-of-2 OT-extension protocols, and is particularly e ffi cient when used to generate a large batch of OPRF instances. The cost to realize m OPRF instances is roughly the cost to realize 3.5 m instances of standard 1-out-of-2 OTs (using state-of-the-art OT extension). We explore in detail our protocol's application to semihonest secure private set intersection (PSI). The fastest state-of-the-art PSI protocol (Pinkas et al., Usenix 2015) is based on e ffi cient OT extension. We observe that our OPRF can be used to remove their PSI protocol's dependence on the bit- length of the parties' items. We implemented both PSI protocol variants and found ours to be 3.1-3.6x faster than Pinkas et al. for PSI of 128-bit strings and sufficiently large sets. Concretely, ours requires only 3.8 seconds to securely compute the intersection of 2(20) -size sets, regardless of the bit length of the items. For very large sets, our protocol is only 4.3 x slower than the insecure naive hashing approach for PSI.