Communication-Efficient Private Join and Compute over Distributed Input Sets

Abstract: In this presentation, we focus on the inner-product variant of private join and compute (PJC), which computes the inner product over matching records from two private datasets.  Instead of assuming each party holds the entire dataset, we focus on the scenario where relevant datasets are distributed across multiple data owners.  In many applications such as privacy-preserving ad conversion measurement, having each party hold the entire dataset is often unrealistic in practice.  No existing PJC protocols directly support distributed input sets across multiple clients, while straightforward generic approaches introduce substantial overhead.   To achieve this goal, we propose an efficient approximate PJC protocol for distributed input sets while keeping the communication sublinear in the input size.  We work in the semi-honest setting and use two non-colluding servers that learn nothing beyond the final approximation.  We propose a novel adaptation of the Gödel Prize-winning AMS sketch redesigned for efficient evaluation under somewhat homomorphic encryption.  Concretely, we show a new form of structured randomness that can be homomorphically generated from short seeds using just 3 levels of multiplication while maintaining the best plaintext accuracy bound.  Based on our optimized implementation, clients can insert each input element into an encrypted sketch in 30 ms, which has a size of 250 KB, independent of input size.  The servers can recover the final output within seconds, orders of magnitude faster than the generic method.

Joint work: Xinran Cai, Wei Dong, Hanlin Liu, Yunqing Sun, Xiao Wang.

Suggested readings

• Communication-Efficient Private Join and Compute over Distributed Input Sets (ia.cr/2026/1812)