Multiparty Reach and Frequency Histogram: Private, Secure, and Practical
Authors: Badih Ghazi (Google Research), Ben Kreuter (Google), Ravi Kumar (Google Research), Pasin Manurangsi (Google Research), Jiayu Peng (Google), Evgeny Skvortsov (Google), Yao Wang (Google), Craig Wright (Google)
Volume: 2022
Issue: 1
Pages: 373–395
DOI: https://doi.org/10.2478/popets-2022-0019
Abstract: Consider the setting where multiple parties each hold a multiset of users and the task is to estimate the reach (i.e., the number of distinct users appearing across all parties) and the frequency histogram (i.e., fraction of users appearing a given number of times across all parties). In this work we introduce a new sketch for this task, based on an exponentially distributed counting Bloom filter. We combine this sketch with a communication-efficient multi-party protocol to solve the task in the multi-worker setting. Our protocol exhibits both differential privacy and security guarantees in the honest-but-curious model and in the presence of large subsets of colluding workers; furthermore, its reach and frequency histogram estimates have a provably small error. Finally, we show the practicality of the protocol by evaluating it on internet-scale audiences.
Keywords: reach, frequency histogram, sketching, differential privacy, multiparty computation
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
