Local Differential Privacy: a tutorial
Björn Bebensee
Abstract
In the past decade analysis of big data has proven to be extremely valuable in many contexts. Local Differential Privacy (LDP) is a state-of-the-art approach which allows statistical computations while protecting each individual user’s privacy. Unlike Differential Privacy no trust in a central authority is necessary as noise is added to user inputs locally. In this paper we give an overview over different LDP algorithms for problems such as locally private heavy hitter identification and spatial data collection. Finally, we will give an outlook on open problems in LDP.
中文速览
大规模数据收集中如何在不侵犯用户隐私的前提下提取有用统计信息，是当前的核心挑战；本地差分隐私（Local Differential Privacy，LDP）通过让每位用户在本地对自己的数据加噪后再上传，从根本上消除了对中心化可信方的依赖。本文系统梳理了LDP的理论基础与主流算法，涵盖频率估计（frequency oracle）、高频项识别（heavy hitter identification）、项集挖掘（itemset mining）以及空间数据收集等核心问题，并详细介绍了Google的RAPPOR和Apple基于count-mean sketch的两套真实落地方案。综合对比显示，不同算法在误差界、通信开销和计算复杂度上各有权衡，而现有实际部署中隐私参数ε的选取缺乏透明度（如Apple每日累计隐私损失可高达ε=16），暴露出理论保障与工程实践之间的明显落差。这项综述为后续研究者提供了清晰的技术图谱，并指出了连续数据高效处理、更紧误差下界证明等尚待突破的开放问题，对隐私计算领域的理论研究和产业应用均具有重要参考价值。
原文 arXiv:1907.11908;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1907.11908v1