BIGDATA: F: DKA: Scalable, Private Algorithms for Continual Data Analysis

BIGDATA：F：DKA：用于持续数据分析的可扩展、私有算法

• 批准号: 1832766
• 负责人: Adam Smith
• 金额: $ 2.15万
• 依托单位: Trustees of Boston University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-08-24 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1832766&HistoricalAwards=false
• 关键词: BIGDATA; DKA; Scalable; Private; Algorithms

For the very same reasons that big data is transforming modern life, it also presents a profound threat to privacy and the control of personal information. A major challenge associated with big data is to enable statistical analysis of complex data sets, without compromising the privacy of the individuals whose data they contain. Addressing this challenge is both necessary, since access to many data sources is restricted due to privacy concerns, and difficult, as numerous attacks on supposedly anonymized data demonstrate. This project will investigate the design and limitations of algorithms for the private, continual analysis of time-varying data sets. That is, it will study algorithms that release information about a data set as it is collected (say, in the form of a data stream from the web, or a long-term sociological study). The research will advance the state of the art in the private analysis of "big" -- massive, complex, time-varying -- data. If successful, the project will provide enabling technologies that facilitate research in areas where access to sensitive data is limited by confidentiality concerns.The project will focus on the design of algorithms that satisfy differential privacy -- a rigorous notion of privacy that is widely studied in computer science and related fields. The privacy implications of sequential releases are still poorly understood, and relatively few of the algorithms developed in the extensive recent literature on private data analysis allow for sequential releases with high accuracy. The two major thrusts of the project are (1) algorithms for the "continual release" model, and (2) algorithms for the "local" model, which offers even stronger privacy guarantees. The work will provide novel algorithmic design techniques and understanding of complexity-theoretic limitations of algorithms for these models. The research will entail advances in related areas such as learning theory, statistical inference and streaming algorithms. The project will also include educational, outreach and work-force training activities designed to broaden the impact of the research.For further information see the project web site at: http://www.cse.psu.edu/~asmith/projects/continual/

出于同样的原因，大数据正在改变现代生活，它也对隐私和个人信息的控制构成了深刻的威胁。与大数据相关的一个主要挑战是能够对复杂数据集进行统计分析，同时又不损害数据所包含的个人的隐私。解决这一挑战既是必要的，因为由于隐私问题，对许多数据源的访问受到限制，而且也很困难，正如对所谓匿名数据的大量攻击所表明的那样。 该项目将研究用于时变数据集的私密、持续分析的算法的设计和局限性。 也就是说，它将研究在收集数据集时发布有关数据集信息的算法（例如，以来自网络的数据流或长期社会学研究的形式）。这项研究将推动对“大”数据（海量、复杂、随时间变化的数据）进行私人分析的最先进水平。如果成功，该项目将提供支持技术，促进对敏感数据的访问因保密问题而受到限制的领域的研究。该项目将重点关注满足差异隐私的算法设计——差异隐私是一种严格的隐私概念，在计算机科学及相关领域。顺序发布的隐私影响仍然知之甚少，并且在最近有关私人数据分析的大量文献中开发的算法相对较少允许高精度的顺序发布。该项目的两大主旨是（1）“持续发布”模型的算法，以及（2）“本地”模型的算法，提供更强的隐私保证。这项工作将提供新颖的算法设计技术以及对这些模型算法的复杂性理论限制的理解。该研究将带来学习理论、统计推理和流算法等相关领域的进步。该项目还将包括旨在扩大研究影响的教育、外展和劳动力培训活动。有关更多信息，请参阅项目网站：http://www.cse.psu.edu/~asmith/projects/连续/

项目成果

When is non-trivial estimation possible for graphons and stochastic block models?‡

什么时候可以对图子和随机块模型进行非平凡的估计？

• DOI: 10.1093/imaiai/iax010
• 发表时间: 2017
• 期刊: Information and Inference: A Journal of the IMA
• 作者: McMillan, Audra;Smith, Adam
• 通讯作者: Smith, Adam

Testing Lipschitz Functions on Hypergrid Domains

在超网格域上测试 Lipschitz 函数

• DOI: 10.1007/s00453-015-9984-y
• 发表时间: 2016
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: Awasthi, Pranjal;Jha, Madhav;Molinaro, Marco;Raskhodnikova, Sofya
• 通讯作者: Raskhodnikova, Sofya

Instantiability of RSA-OAEP Under Chosen-Plaintext Attack

• DOI: 10.1007/s00145-016-9238-4
• 发表时间: 2010-08
• 期刊: Journal of Cryptology
• 影响因子: 3
• 作者: Eike Kiltz;Adam O'Neill;Adam D. Smith

Is Interaction Necessary for Distributed Private Learning?

• DOI: 10.1109/sp.2017.35
• 发表时间: 2017-05
• 期刊: 2017 IEEE Symposium on Security and Privacy (SP)
• 作者: Adam D. Smith;Abhradeep Thakurta;Jalaj Upadhyay

Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism

• DOI: 10.1109/focs.2016.60
• 发表时间: 2016-10
• 期刊: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: Sofya Raskhodnikova;Adam D. Smith