Not Just Summing: The Identifier Leakage of Private-Join-and-Compute and its Improvement

In this work, we focus on the Private Intersection-Sum (PIS) with cardinality problem: two parties hold datasets containing user identifiers, and the second party additionally has an integer value associated with each user identifier. Both parties want to learn the number of users they have in common, and the sum of the integer values associated with a user, without revealing anything more. To this end, Google proposed a PIS protocol and released the open-source library Private-Join-and-Compute. And the security of the protocol has been proven in the honest-but-curious model. However, this study found a potential shortcoming in the Private-Join-and-Compute library: the user identifier stealing attack against the PIS protocol based on a special input data structure. An improved PIS protocol is proposed based on differential privacy technology, and the Private-Join-and-Compute open-source library is optimized. Through a security proof and formal analysis based on the Tamarin tool, we show that the improved PIS protocol successfully resists the discovered attack without obvious additional overhead.

I. Introduction

The private set intersection (PSI) protocol [1] enables two or more parties to privately compute the intersection of their private sets and does not disclose any information to any participating party other than the elements in the intersection. This protocol has been extensively applied in the real world. For example, in a business-to-consumer (B2C) environment, it is used to check and warn weak password accounts of Google's browser Chrome [2]. In the consumer-to-consumer (C2C) environment, it has been proposed to prevent cheating in online games [3]. In response to the recent epidemic of COVID-19, a scheme based on the PSI protocol for contact tracing has been proposed [4]. In addition, the PSI protocol is also widely used in privacy access scenarios such as mobile applications [5], [6].