TWC: Small: Fundamental Limits in Differential Privacy

差分隐私已经成为平衡个人隐私和社会以及商业数据使用的一种有充分基础的方法。其基本思想是在分析结果中加入随机噪声，足以掩盖任何单个数据对分析的影响，从而保护个人隐私。虽然存在提供差异隐私的一般方法，但在许多情况下，界限并不严格；增加的噪音比需要的多。本项目使用信息理论技术来探讨差分隐私中基本的隐私/准确性权衡。拟议研究的成功将使我们朝着一个更安全、更有保障的国家迈进，在这个国家，对个人隐私的尊重不会受到损害。拟议的研究与一项教育计划紧密结合，该计划旨在开发一门关于隐私算法基础的新研究生课程。本项目将研究几个主题：(1)通过应用信息理论工具和方法来确定实现差异隐私的严格界限，表征隐私保障与发布数据效用之间的基本权衡；(2)为个人设计数据私有化机制，实现计算效率和效用与隐私之间的最佳权衡；(3)为复杂数据处理系统的宏观分析提供隐私演算，这些系统由各个组件组成，每个组件都有自己的隐私保证。隐私演算旨在提供新的表示和计算工具来表征隐私组件如何在大型系统中相互作用，类似于网络演算如何允许研究人员使用线性系统中熟悉的工具来表征复杂的非线性通信系统。

Differential Privacy has emerged as a well-grounded approach to balancing personal privacy and societal as well as commercial use of data. The basic idea is to add random noise to analysis results sufficient to obscure the impact of any single individual's data on the analysis, thus protecting individual privacy. While general approaches to providing differential privacy exist, in many cases the bounds are not tight; more noise is added than needed. This project uses information theoretic techniques to explore the fundamental privacy/accuracy tradeoffs in differential privacy. The success of the proposed research will make progress towards a safer and more secure nation where the respect for individuals' privacy is not compromised. The proposed research is strongly integrated with an education plan that aims to develop a new graduate level course on algorithmic foundations of privacy.This project will investigate several topics: (1) characterizing the fundamental tradeoffs between the privacy guarantee and the utility of the released data, by applying information theoretic tools and methods to identify tight bounds on achieving differential privacy; (2) designing data privatization mechanisms for individuals that achieve both computational efficiency and the optimal tradeoffs between utility and privacy; and (3) providing a privacy calculus for macroscopic analyses of complex data processing systems, consisting of various components each with its own privacy guarantees. The privacy calculus aims to provide new representations and computational tools for characterizing how privacy components interact in a large system, analogous to how network calculus allows researchers to characterize complex non-linear communication systems using familiar tools from linear systems.