Paper 2020/029

Differentially-Private Multi-Party Sketching for Large-Scale Statistics

Seung Geol Choi, Dana Dachman-Soled, Mukul Kulkarni, and Arkady Yerukhimovich


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 datasets, including the publicly available IP address data set from University of Michigan’s scans of internet IPv4 space, to determine the tradeoffs 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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
multiparty computationdifferential privacybig datasketching
Contact author(s)
danadach @ umd edu
choi @ usna edu
mukul @ cs umass edu
arkady @ gwu edu
2020-01-13: received
Short URL
Creative Commons Attribution


      author = {Seung Geol Choi and Dana Dachman-Soled and Mukul Kulkarni and Arkady Yerukhimovich},
      title = {Differentially-Private Multi-Party Sketching for Large-Scale Statistics},
      howpublished = {Cryptology ePrint Archive, Paper 2020/029},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.