Delegated Private Matching for Compute

Dimitris Mouris; Daniel Masny; Ni Trieu; Shubho Sengupta; Prasad Buddhavarapu; Benjamin Case

Paper 2023/012

Delegated Private Matching for Compute

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.

Abstract

Private matching for compute (PMC) establishes a match between two datasets owned by mutually distrusted parties ( and ) 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 to untrusted cloud servers, called delegates, allowing multiple smaller parties to provide inputs containing identifiers and associated values. Our Delegated Private Matching for Compute protocols, called DPMC and DPMC, establish a join between the datasets of party and multiple delegators 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 DPMC 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 for the total protocol execution and by at least for the computation on the delegators.

Note: Our protocols are open-source at https://github.com/facebookresearch/Private-ID.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Proceedings on Privacy Enhancing Technologies (PoPETs) 2024
Keywords: Oblivious pseudorandom function private identity matching private record linkage secure multiparty computation
Contact author(s): jimouris @ udel edu
daniel masny @ rub de
nitrieu @ asu edu
ssengupta @ meta com
bprasad @ meta com
bmcase @ meta com
History: 2023-12-30: last of 2 revisions; 2023-01-03: received; See all versions
Short URL: https://ia.cr/2023/012
License: CC BY

BibTeX

@misc{cryptoeprint:2023/012,
      author = {Dimitris Mouris and Daniel Masny and Ni Trieu and Shubho Sengupta and Prasad Buddhavarapu and Benjamin Case},
      title = {Delegated Private Matching for Compute},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/012},
      year = {2023},
      url = {https://eprint.iacr.org/2023/012}
}