Paper 2020/623

PSI-Stats: Private Set Intersection Protocols Supporting Secure Statistical Functions

Jason H. M. Ying and Shuwei Cao and Geong Sen Poh and Jia Xu and Hoon Wei Lim

Abstract

Private Set Intersection (PSI) enables two parties, each holding a private set to securely compute their intersection without revealing other information. This paper considers settings of secure statistical computations over PSI, where both parties hold sets containing identifiers with one of the parties having an additional positive integer value associated with each of the identifiers in her set. The main objective is to securely compute some desired statistics of the associated values for which its corresponding identifiers occur in the intersection of the two sets. This is achieved without revealing the identifiers of the set intersection. This has many useful business applications, for examples in measuring effectiveness of advertising campaigns. In many cases, the parties wish to know various statistical information with regards to the set intersection and the associated integer values. For instance, information relating to arithmetic mean, geometric mean, harmonic mean, standard deviation, minimum, maximum, range or an approximate distribution of the sum composition. A potential use case is for a credit card company to provide the percentage of high spending to a shopping mall based on their common customers. Therefore, in this paper we introduce various mechanisms to enable secure computation of statistical functions, which we collectively termed PSI-Stats. The proposed protocols maintain strong privacy guarantee, that is computations are performed without revealing the identifiers of the set intersection to both parties. Implementations of our constructions are also carried out based on a simulated dataset as well as on actual datasets in the business use cases that we defined, in order to demonstrate practicality of our solution. PSI-Stats has a lower communication overhead compared to the current state-of-the-art circuit-based PSI protocol of Pinkas et al. (EUROCRYPT'19) by a factor of at least 3.9x and consequently has a lower run time than the latter at low network bandwidth settings from our experiments. Our solution is more tailored towards business applications where communication cost is the primary consideration.

Note: Include acknowledgement and additional experiments.