Cryptology ePrint Archive: Report 2021/770

Multi-key Private Matching for Compute

Prasad Buddhavarapu and Benjamin M Case and Logan Gore and Andrew Knox and Payman Mohassel and Shubho Sengupta and 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.

Category / Keywords: cryptographic protocols / private set intersection, private identity matching

Date: received 8 Jun 2021

Contact author: bmcase at fb com

Available format(s): PDF | BibTeX Citation

Version: 20210609:062713 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]