Paper 2019/723

On Deploying Secure Computing Commercially: Private Intersection-Sum Protocols and their Business Applications

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

Abstract

In this work, we describe how to deploy a cryptographic secure computation protocol for routine use in industry. Based on our experience, we identify major preliminaries and enabling factors which we found to be critical to the successful deployment of such technology as a practical, and uniquely positioned method for solving the task at hand. The specific technical problem that we tackled is that of computing Private Intersection-Sum. In this setting two parties hold datasets containing user identifiers, and one of the parties additionally has an integer value associated with each of its user identifiers. The parties want to learn (1) the number of users they have in common and (2) the sum of the integer values associated with these users, without revealing any more information about their private inputs. Private Intersection-Sum is not an arbitrary question, but rather arose naturally and was concretely defined based on a given central business need: computing aggregate conversion rate (or effectiveness) of advertising campaigns. This problem has both great practical value and important privacy considerations, and represents a type of analysis that occurs surprisingly commonly. Among the factors that enabled our deployment, in this work we consider in more depth the technical issue of protocol choice and its performance implications. Specifically, we present a study involving three novel protocols for computing Private Intersection-Sum, which leverage three different basic protocol techniques including Random Oblivious Transfer, encrypted Bloom filters, and Diffie–Hellman style (Pohlig–Hellman specifically) double masking. We compare the three protocols under different instantiations of an additive homomorphic encryption, which is used as a building block in each protocol. We implement our constructions and compare their actual communication and computation overheads. Finally, we analyze the advantages of the DDH-based protocol which make it the solution of choice for our deployment setting.