CIF: Small: Statistical Data Privacy: Fundamental Limits and Efficient Algorithms

隐私权是一项基本的个人权利。在大数据时代，大量个人数据的收集既有自愿的（如常旅客/购物者奖励），也有非自愿的（如美国人口普查或医疗记录）。在这个信息时代，人们随时可以搜索信息，并将不同来源的信息联系起来（使用数据分析和/或推荐系统），隐私侵犯是一种不祥的预兆。用户信息的匿名化是一种经典技术，但容易受到关联攻击：通过将匿名化数据库与另一个（可能是公开可用的）去匿名化数据库关联，用户的隐私仍然可能被泄露。摆脱匿名化限制的一个方法是发布一个随机数据库；这为通过数据发布泄露的任何用户身份提供了合理的否认。为用户在场/不在场的可否认性提供保证的系统方法是差分隐私的技术领域，它为具有任意侧信息的对手提供强大的隐私保证。我们最感兴趣的是描述那些随机化“刚好足够”的隐私机制，使发布的数据库尽可能忠实于预期的数据库，从而提供最大的效用。基于最近将信息论和统计数据隐私领域（通过假设检验上下文）联系起来的工作，并展示了在中、低隐私制度的最新技术水平上呈指数级改善的新型隐私机制（例如，在添加的噪声方差方面），该项目的目标有三个方面：(a)表征在各种规范设置中隐私和效用之间权衡的基本限制；(b)发现可在实践中有效执行的（接近）最佳机制；(c)利用假设检验的操作背景寻求统计数据隐私的自然概念（超越差分隐私）。在当今的信息时代，隐私是一个中心的、多方面的社会和技术问题。该项目侧重于这一多方面领域的技术方面，并试图在当前完善的隐私概念（差异隐私）的背景下发现隐私-效用权衡的基本限制。预期的结果是基本的，并立即适用于各种实际情况。具体而言，将详细研究涉及基因组数据发布和智能电表数据发布的两个具体实践设置。由于隐私问题，基因组和智能电表数据基本上是不可用的，这剥夺了广泛的数据分析和此类分析的实际意义。该项目将构建并发布一个消毒工具的软件套件，包括作为该项目一部分发现的隐私机制。

Privacy is a fundamental individual right. In the era of big data, large amounts of data about individuals are collected both voluntarily (e.g., frequent flier/shopper incentives) and involuntarily (e.g. US Census or medical records). With the ready ability to search for information and correlate it across distinct sources (using data analytics and/or recommender systems), privacy violation takes on an ominous note in this information age. Anonymization of user information is a classical technique, but is susceptible to correlation attacks: by correlating the anonymized database with another (perhaps publicly available) deanonymized database, a user's privacy could still be divulged. A way out of the limitations of anonymization is to release a randomized database; this offers plausible deniability of any user identity breached via the data release. A systematic way of providing guarantees for the deniability of user presence/absence is the technical field of differential privacy, providing strong privacy guarantees against adversaries with arbitrary side information. It is of fundamental interest to characterize privacy mechanisms that randomize "just enough" to keep the released database as true to the intended one as possible, providing maximal utility. Based on recent work connecting the areas of information theory and statistical data privacy (via a hypothesis testing context) and demonstrating novel privacy mechanisms that exponentially improve (in terms of variance of noise added, say) upon the state of the art for medium and low privacy regimes, the objective of the project is threefold: (a) characterize the fundamental limits to tradeoffs between privacy and utility in a variety of canonical setting; (b) discover (near) optimal mechanisms that can be efficiently implemented in practice; and (c) seek natural notions of statistical data privacy (beyond differential privacy) using the operational context of hypothesis testing. Privacy is a central, and multifaceted, social and technological issue of today's information age. This project is focused on the technical aspect of this multifaceted area, and seeks to discover fundamental limits to privacy-utility tradeoffs in the context of currently well established notions of privacy (differential privacy). The expected results expected are fundamental and immediately applicable to a variety of practical settings. Specifically, two concrete practical settings involving genomic data release and smart meter data release will be studied in detail. Due to privacy concerns, genomic and smart meter data is simply unavailable at large -- depriving widespread data analytics and practical implications of such analysis. This project will build and release a software suite of sanitization tools, involving the privacy mechanisms discovered as part of this project.