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

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

Paper 2017/738

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

Mihaela Ion, Ben Kreuter, Erhan Nergiz, Sarvar Patel, Shobhit Saxena, Karn Seth, 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.

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Contact author(s): benkreuter @ google com
History: 2017-08-01: received
Short URL: https://ia.cr/2017/738
License: CC BY

BibTeX

@misc{cryptoeprint:2017/738,
      author = {Mihaela Ion and Ben Kreuter and Erhan Nergiz and Sarvar Patel and Shobhit Saxena and Karn Seth and David Shanahan and Moti Yung},
      title = {Private Intersection-Sum Protocol with Applications to Attributing Aggregate Ad Conversions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/738},
      year = {2017},
      url = {https://eprint.iacr.org/2017/738}
}