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.