Efficient Batched Oblivious PRF with Applications to Private Set Intersection

By Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, Ni Trieu. Conference on Computer and Communications Security, 2016

440 citations recorded by the source corpus.

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 efficient when used to generate a large batch of OPRF instances. The cost to realize m OPRF instances is roughly the cost to realize 3:5m 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 efficient 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.6 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 220-size sets, regardless of the bitlength of the items. For very large sets, our protocol is only 4:3 slower than the insecure naive hashing approach for PSI.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/f9dbf7a5b6c8f2aa809992381442d81164060f7c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Efficient Pseudorandom Correlation Generators: Silent OT Extension and More (2019, background): “OPRFs serve as the main building blocks in recent protocols for private set intersection [56].”
A Pragmatic Introduction to Secure Multi-Party Computation (2019, methodology): “We will present current state-of-the art two-party PSI (Kolesnikov et al., 2016).”
Scalable Private Set Intersection Based on OT Extension (2018, methodology): “Overall, we view our work as complementary to the work of [Kolesnikov et al. 2016], where one can instantiate the underlying code based on the parameters to achieve the best overall performance.”
Improved Private Set Intersection Against Malicious Adversaries (2017, background): “[23,22,16] that rely heavily on oblivious transfers.”
Practical Multi-party Private Set Intersection from Symmetric-Key Techniques (2017, background): “The previous OPPRF constructions can be instantiated with any any number t of points. inherit the same t . block from [26] only supports t = 1. construction tailored for the case of t = 1, and for small values of n The main challenges are: (1) ℛ should not know whether he is whether x = x i for…”
An Efficient Toolkit for Computing Private Set Operations (2017, background): “The existing works of [23,22,19] provide even faster designs though these use inherently symmetric primitives which are not comparable with our work.”
Labeled PSI from Fully Homomorphic Encryption with Malicious Security (2018, methodology): “Transfer (OT) extension protocols [36, 42], which enable a functionality very similar to a traditional OPRF.”
Scalable Private Set Union from Symmetric-Key Techniques (2019, methodology): “We emphasize that, although cumbersome, it is possible to incorporate all of the [36] relaxations into the definitions.”
Fast Private Set Intersection from Homomorphic Encryption (2017, background): “The theoretical communication complexity of [37] is”
On Deploying Secure Computing Commercially: Private Intersection-Sum Protocols and their Business Applications (2019, methodology): “We refer the reader to [34] for details, and omit them here since the distinction does not have a significant impact on our protocol or proofs).”