Distributed Measurement with Private Set-Union Cardinality
Ellis Fenske, Akshaya Mani, Aaron M. Johnson, Micah Sherr · 2017
This paper introduces a cryptographic protocol for efficiently aggregating a count of unique items across a set of data parties privately - that is, without exposing any information other than the count. Our protocol allows for more secure and useful statistics gathering in privacy-preserving distributed systems such as anonymity networks; for example, it allows operators of anonymity networks such as Tor to securely answer the questions: how many unique users are using the distributed service? and how many hidden services are being accessed?. We formally prove the correctness and security of our protocol in the Universal Composability framework against an active adversary that compromises all but one of the aggregation parties. We also show that the protocol provides security against adaptive corruption of the data parties, which prevents them from being victims of targeted compromise. To ensure safe measurements, we also show how the output can satisfy differential privacy.