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


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
private set intersectionprivate identity matching
Contact author(s)
bmcase @ fb com
2021-06-09: received
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.