Cryptology ePrint Archive: Report 2020/599

Private Matching for Compute

Prasad Buddhavarapu and Andrew Knox and Payman Mohassel and Shubho Sengupta and Erik Taubeneck and Vlad Vlaskin

Abstract: We revisit the problem of two-party private set intersection for aggregate computation which we refer to as private matching for compute. In this problem, two parties want to perform various downstream computation on the intersection of their two datasets according to a previously agreed-upon identifier. We observe that prior solutions to this problem have important limitations. For example, any change or update to the records in either party's dataset triggers a rerun of the private matching component; and it is not clear how to support a streaming arrival of one party's set in small batches without revealing the match rate for each individual batch. We introduce two new formulations of the private matching for compute problem meeting these requirements, called private-ID and streaming private secret shared set intersection, and design new DDH-based constructions for both. Our implementation shows that when taking advantage of the inherent parallelizability of these solutions, we can execute the matching for datasets of size upto 100 million records within an hour.

Category / Keywords: cryptographic protocols / private set operations, secure two-party computation, private matching

Date: received 20 May 2020, last revised 20 May 2020

Contact author: paymanm at fb com

Available format(s): PDF | BibTeX Citation

Version: 20200522:151524 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]