Delegated Private Matching For Compute
Authors: Dimitris Mouris (University of Delaware), Daniel Masny (Meta Inc.), Ni Trieu (Arizona State University), Shubho Sengupta (Meta Inc.), Prasad Buddhavarapu (Meta Inc.), Benjamin Case (Meta Inc.)
Volume: 2024
Issue: 2
Pages: 49–72
DOI: https://doi.org/10.56553/popets-2024-0040
Abstract: Private matching for compute (PMC) establishes a match between two datasets owned by mutually distrusted parties (C and P) and allows the parties to input more data for the matched records for arbitrary downstream secure computation without rerunning the private matching component. The state-of-the-art PMC protocols only support two parties and assume that both parties can participate in computationally intensive secure computation. We observe that such operational overhead limits the adoption of these protocols to solely powerful entities as small data owners or devices with minimal computing power will not be able to participate.
We introduce two protocols to delegate PMC from party P to untrusted cloud servers, called delegates, allowing multiple smaller P parties to provide inputs containing identifiers and associated values. Our Delegated Private Matching for Compute protocols, called DPMC and DsPMC, establish a join between the datasets of party C and multiple delegators P based on multiple identifiers and compute secret shares of associated values for the identifiers that the parties have in common. We introduce a rerandomizable encrypted oblivious pseudorandom function (OPRF) primitive, called EO, which allows two parties to encrypt, mask, and shuffle their data. Note that EO may be of independent interest. Our DsPMC protocol limits the leakages of DPMC by combining our EO scheme and secure three-party shuffling. Finally, our implementation demonstrates the efficiency of our constructions by outperforming related works by approximately 10x for the total protocol execution and by at least 20x for the computation on the delegators.
Keywords: Oblivious pseudorandom function, private identity matching, private record linkage, secure multiparty computation
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
