TC: Small: Provably Private Microdata Publishing

数据是信息时代的关键资源。然而，数据的可用性往往会引起隐私问题。许多数据共享场景需要对数据进行匿名化，以保护隐私。然而，大多数现有的数据匿名化技术只能满足薄弱的隐私概念，这些概念依赖于对对手的特定假设，并且提供的保护不足。近年来，差分隐私的优雅概念逐渐被接受为回答统计查询的隐私概念选择。然而，大多数关于差异隐私的研究都集中在回答交互式查询上，并且在满足差异隐私的同时发布微数据有一些负面结果。无论如何，许多数据共享场景需要共享微数据，需要进行研究来弥合这一差距。该项目旨在弥合差异隐私的优雅概念与在保持效用的同时发布微数据的实际困难之间的差距。在PI使用随机抽样和“安全”k-匿名化来满足差异隐私的初步结果的基础上，该项目旨在推进保护隐私的微数据发布的科学理解和具体技术的最新水平。研究活动包括开发(1)实用的匿名化方法，可以证明满足差异隐私，同时能够处理高维数据；(2)放宽差异化隐私，更适合微数据发布；(3)隐私理论和技术很容易应用于一系列数据处理算法，称为本地化算法，允许使用输入扰动技术进行可证明的私有微数据发布；(4)社交网络数据和网络轨迹数据发布的隐私理念与技术。数据匿名化技术的进步将使社会受益，因为它可以更好地平衡为公共利益而发布数据的需要和保护个人隐私的需要。该项目还包括开发一门关于数据隐私的研究生研讨会课程，并为两名研究生提供支持。

Data is a key resource in this information age. The availability of data, however, often causes privacy concerns. Many data sharing scenarios require data be anonymized for privacy protection. Most existing data anonymization techniques, however, satisfy only weak privacy notions that rely on particular assumptions about the adversaries, and provide inadequate protection. In recent years, the elegant notion of differential privacy has gradually been accepted as the privacy notion of choice for answering statistical queries. Most research on differential privacy, however, focuses on answering interactive queries, and there are several negative results on publishing microdata while satisfying differential privacy. Regardless, many data sharing scenarios require sharing of microdata, and research is needed to bridge this gap.This project aims at bridging the gap between the elegant notion of differential privacy, and the practical difficulty of publishing microdata while preserving utility. Building on the preliminary results of the PI on using random sampling together with "safe" k-anonymization to satisfy differential privacy, this project aims at advancing the state of the art of both scientific understanding and specific techniques for privacy-preserving microdata publishing. Research activities include developing (1) Practical anonymization methods that can be proven to satisfy differential privacy, while capable of handling high-dimensional data; (2) Relaxations of differential privacy that are more suitable for microdata publishing; (3) Privacy theory and techniques that are easily applied to a family of data sanitization algorithms called localized algorithms, enabling the usage of input perturbation techniques for provably-private microdata publishing; (4) Privacy notions and techniques for publishing social network data and network trace data.Advances in data anonymization techniques will benefit the society by providing a better balance between the need to release data to serve public interest and the need to protect individuals' privacy. This project also involves developing a graduate seminar course on data privacy, and supports two graduate students.