Differentially-Private Multi-Party Sketching for Large-Scale Statistics
| Autor: | Seung Geol Choi, Dana Dachman-Soled, Arkady Yerukhimovich, Mukul Kulkarni |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Ethics
021110 strategic defence & security studies Scale (ratio) sketching algorithms Computer science 0211 other engineering and technologies QA75.5-76.95 0102 computer and information sciences 02 engineering and technology BJ1-1725 secure computation 01 natural sciences Data science 010201 computation theory & mathematics differential privacy Electronic computers. Computer science General Earth and Planetary Sciences General Environmental Science |
| Zdroj: | Proceedings on Privacy Enhancing Technologies, Vol 2020, Iss 3, Pp 153-174 (2020) |
| ISSN: | 2299-0984 |
| Popis: | We consider a scenario where multiple organizations holding large amounts of sensitive data from their users wish to compute aggregate statistics on this data while protecting the privacy of individual users. To support large-scale analytics we investigate how this privacy can be provided for the case of sketching algorithms running in time sub-linear of the input size. We begin with the well-known LogLog sketch for computing the number of unique elements in a data stream. We show that this algorithm already achieves differential privacy (even without adding any noise) when computed using a private hash function by a trusted curator. Next, we show how to eliminate this requirement of a private hash function by injecting a small amount of noise, allowing us to instantiate an efficient LogLog protocol for the multi-party setting. To demonstrate the practicality of this approach, we run extensive experimentation on multiple data sets, including the publicly available IP address data set from University of Michigan’s scans of internet IPv4 space, to determine the trade-offs among efficiency, privacy and accuracy of our implementation for varying numbers of parties and input sizes. Finally, we generalize our approach for the LogLog sketch and obtain a general framework for constructing multi-party differentially private protocols for several other sketching algorithms. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|