Multi-key Private Matching for Compute

Prasad Buddhavarapu; Benjamin M Case; Logan Gore; Andrew Knox; Payman Mohassel; Shubho Sengupta; Erik Taubeneck; Min Xue

Paper 2021/770

Multi-key Private Matching for Compute

Prasad Buddhavarapu, Benjamin M Case, Logan Gore, Andrew Knox, Payman Mohassel, Shubho Sengupta, Erik Taubeneck, and Min Xue

Abstract

We extend two-party private set union for secure computation, by considering matching between records having multiple identifiers (or keys), for example email and phone. In the classical setting of this problem, two parties want to perform various downstream computations on the union of two datasets. The union is computed by joining two datasets with the help of a single agreed upon identifier, say email. By extending this to joining records with multiple identifiers, we bring it much closer to real world uses where the match rate and match quality can be greatly improved by considering multiple identifiers. We introduce an extension to the Private-ID protocol [3] which outputs a full outer join (union) of two datasets by a match logic that can join rows containing multiple identifiers. We also introduce new techniques for privately sharding the protocol across multiple servers. Both constructions are based on Decisional Diffie–Hellman (DDH) assumptions.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint. MINOR revision.
Keywords: private set intersection private identity matching
Contact author(s): bmcase @ fb com
History: 2021-06-09: received
Short URL: https://ia.cr/2021/770
License: CC BY

BibTeX

@misc{cryptoeprint:2021/770,
      author = {Prasad Buddhavarapu and Benjamin M Case and Logan Gore and Andrew Knox and Payman Mohassel and Shubho Sengupta and Erik Taubeneck and Min Xue},
      title = {Multi-key Private Matching for Compute},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/770},
      year = {2021},
      url = {https://eprint.iacr.org/2021/770}
}