International Association
for Cryptologic Research

Private computation on (labeled) set intersection (PCSI/PCLSI) is a secure computation protocol that allows two parties to compute fine-grained functions on set intersection, including cardinality, cardinality-sum, secret shared intersection and arbitrary functions. Recently, some computationally efficient PCSI protocols have emerged, but a limitation on these protocols is the communication complexity, which scales (super)-linear with the size of the large set. This is of particular concern when performing PCSI in the unbalanced case, where one party is a constrained device with a small set, and the other is a service provider holding a large set.

In this work, we first formalize a new ideal functionality called shared characteristic and its labeled variety called shared characteristic with labels, from which we propose the frameworks of PCSI/PCLSI protocols. By instantiating our frameworks, we obtain a series of efficient PCSI/PCLSI protocols, whose communication complexity is linear in the size of the small set, and logarithmic in the large set.

We demonstrate the practicality of our protocols with implementations. Experiment results show that our protocols outperform previous ones and the larger difference between the sizes of two sets, the better our protocols perform. For input set sizes $2^{10}$ and $2^{22}$ with items of length $128$ bits, our PCSI requires only $4.62$MB of communication to compute the cardinality; $4.71$MB of communication to compute the cardinality-sum. Compared with the state-of-the-art PCSI proposed by Chen et al., there are $ 58 \times$ and $77 \times$ reductions in the communication cost of computing cardinality and cardinality-sum.