CAREER:Information Theoretic Methods for Private Information Retrieval and Search in Distributed Storage Systems

最近的数据革命正在推动现代社会和经济进步的许多方面。这些海量数据中的大部分现在都存储在云端，以便无数希望共享信息的用户可以轻松访问，例如照片、视频、出版物、观点和科学数据。不幸的是，这是以牺牲用户的隐私为代价的，用户的在线活动可以被用来描述他/她的个人资料，这使得大部分人很容易成为歧视和可能受到迫害的目标。本研究旨在通过关注分布式存储系统（DSSs）中的私有信息检索（PIR）和搜索问题来解决云数据的隐私挑战。PIR方案使用户能够查询数据，而不会泄露有关查询的信息，从而不会泄露他们的个人偏好、倾向、健康状况或其他特征。经典的信息论PIR方案要求数据被复制，在数据呈指数增长的情况下，这不是一个可扩展的解决方案。本研究旨在为研究编码方案创建一个统一的框架，除了提供数据可靠性外，还可以满足私人查询的需要。提出的研究重点是(i)明确构建代码和PIR方案，解决分布式存储的实际和重要方面，如存储成本、网络通信成本、磁盘读取、延迟和计算；（ii）为私隐关键字搜寻提供明确的编码和方案；（iii）描述可靠性、隐私性和不同系统开销之间的基本限制和权衡；（iv）在真实的基因组和社会科学数据上测试方案的软件实现。该项目还包括一些教育和推广工作，包括开发新的公开可访问的在线内容，内容涉及分布式存储系统中的信息理论、安全和隐私，以及通过PI所在机构的全球领袖计划进行大学前推广。

The recent data revolution is driving many aspects of modern societal and economic progress. Most of this massive data is now stored in the cloud to enable easy access for a myriad of users who wish to share information including, for example, photos, videos, publications, opinions, and scientific data. Unfortunately, this has come at the expense of the user's privacy whose online activity can be used to profile him/her, making large parts of the population an easy target for discrimination and possible persecution. This research aims at addressing the privacy challenge of data in the cloud by focusing on the problem of Private Information Retrieval (PIR) and Search in distributed storage systems (DSSs). PIR schemes enable users to query data without revealing information about the queries and hence their personal preferences, tendencies, health, or other traits.Classical information theoretic PIR schemes require data to be replicated, which is not a scalable solution given the exponential growth of data. This research aims at creating a unified framework for studying coding schemes that, in addition to providing data reliability, cater to the need of private queries. The focus of the proposed research is on (i) explicit constructions of codes and PIR schemes that address practical and important aspects of distributed storage, such as storage cost, network communication cost, disk reads, latency and computations; (ii) explicit constructions of codes and schemes for private keyword search; (iii) characterization of the fundamental limits and tradeoffs between reliability, privacy and the different system overheads; (iv) testing software implementations of the schemes on real genomic and social science data. The project also incorporates several educational and outreach efforts, including the development of new publicly accessible online content on information theory, security, and privacy in distributed storage systems as well as pre-college outreach through the Global Leaders Program at the PI's institution.