Unbalanced Private Computation on Set Intersection with Reduced Computation and Communication

Private computation on set intersection (PCSI) allows two parties to compute fine-grained functions on set intersection without revealing anything else. Although several efficient PCSI protocols are available in the literature, only recently have techniques been applied to improve their performance in an unbalanced setting, where the set size of one party is much smaller than the other. In this work, we focus on improving the efficiency of unbalanced PCSI based on the framework comprising shared characteristic (SC) and permuted private equality test (p-PEQT). Firstly, our key insight is that SC can be efficiently constructed from batch keyword private information retrieval (PIR), requiring only a single keyword PIR query instead of multiple PIR queries. We further provide a novel construction of batch keyword PIR that performs remarkably for small entries, and then propose a communication-efficient SC based on the batch keyword PIR. Secondly, previous p-PEQT protocols depend on public-key operations, leading to substantial computation overhead. We consider symmetric-key operations to efficiently construct p-PEQT. Specifically, our p-PEQT construction is based on distributed point function (DPF) and additionally improves online performance thanks to preprocessing. Finally, we obtain a series of unbalanced PCSI protocols with reduced computation and communication from our SC and p-PEQT, and these protocols are secure against semi-honest adversaries in the standard model. We implement our protocols and compare them with the state-of-the-art works. The experiments show that our PCSI-card achieves a 2.1× speedup under LAN setting and a 1.9× speedup under WAN setting. It also reduces communication by 1.1-1.8×, depending on the set sizes.