首页    期刊浏览 2024年11月05日 星期二
登录注册

文章基本信息

  • 标题:Differentially-Private Multi-Party Sketching for Large-Scale Statistics
  • 本地全文:下载
  • 作者:Seung Geol Choi ; Dana Dachman-soled ; Mukul Kulkarni
  • 期刊名称:Proceedings on Privacy Enhancing Technologies
  • 电子版ISSN:2299-0984
  • 出版年度:2020
  • 卷号:2020
  • 期号:3
  • 页码:153-174
  • DOI:10.2478/popets-2020-0047
  • 语种:English
  • 出版社:Sciendo
  • 摘要: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.
  • 关键词:differential privacy;sketching algorithms;secure computation
国家哲学社会科学文献中心版权所有