Cryptology ePrint Archive: Report 2017/738

Private Intersection-Sum Protocol with Applications to Attributing Aggregate Ad Conversions

Mihaela Ion and Ben Kreuter and Erhan Nergiz and Sarvar Patel and Shobhit Saxena and Karn Seth and David Shanahan and Moti Yung

Abstract: In this work, we consider the Intersection-Sum problem: two parties hold datasets containing user identifiers, and the second party additionally has an integer value associated with each user identifier. The parties want to learn the number of users they have in common, and the sum of the associated integer values, but “nothing more”. We present a novel protocol tackling this problem using Diffie-Hellman style Private Set Intersection techniques together with Paillier homomorphic encryption. We prove security of our protocol in the honest-but-curious model. We also discuss applications for the protocol for attributing aggregate ad conversions. Finally, we present a variant of the protocol, which allows aborting if the intersection is too small, in which case neither party learns the intersection-sum.

Category / Keywords:

Date: received 31 Jul 2017

Contact author: benkreuter at google com

Available format(s): PDF | BibTeX Citation

Version: 20170801:152257 (All versions of this report)

Short URL: ia.cr/2017/738

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]