CCF-BSF: CIF: Small: Distributed Information Retrieval: Private, Reliable, and Efficient

数字时代是以信息无处不在为基础的。访问存储在“云”中的远程服务器上的相关数据的能力已成为日常生活中不可或缺的资源。许多在线服务允许用户查询公共数据集的数据项，例如地图方向、股票报价和航班价格等等。数字内容提供商也依赖于用户查询来识别用户想要的内容。不幸的是，这样的查询有可能泄露关于用户的高度敏感信息，从而损害他们的隐私。例如，机构投资者在股票市场数据库中查询某些股票的价值时，可能不愿意透露他们对这些股票的兴趣，因为这可能会影响它们的价格。另一个例子是，大多数人都非常不愿意把自己的媒体消费习惯暴露在一个可能被黑客攻击或传唤的中央服务器上。可以令人信服地说，访问这些媒体消费档案可以揭示一个人的性取向、政治倾向和文化背景。大量的研究致力于保证数据的安全性和完整性的方法。然而，致力于保护“用户”隐私的工作要少得多。高效、可靠地从分布式数据库中检索信息，并从信息论上保证用户的隐私，是本项目的重点。相关的研究领域被称为私人信息检索。虽然该领域的大多数现有结果都是理论性的，但该项目的主要目标是弥合私有信息检索理论与分布式存储实践之间的差距。因此，这项调查的潜在结果可能超出学术研究的范围，有助于新技术和新产品。私有信息检索（Private information retrieval， PIR）是Chor、Goldreich、Kushilevitz和Sudan在20多年前的开创性论文中提出的概念，传统上是在理论计算机科学和密码学中进行研究的，重点是用户与存储数据库的服务器之间通信的复杂性。虽然多年来在这一领域取得了重大突破，但流行的模式一直是在几个非通信服务器上复制数据库。这种复制会导致大量的存储开销，这是不希望看到的。此外，由于分布式存储编码的进步，最近人们认识到，如果数据库复制被“数据库编码”所取代，那么编码理论方法的全部力量就可以用来解决这个问题。虽然前景非常光明，但这方面的研究仍处于起步阶段。这个项目的目标是继承数据库编码的思想，并遵循它的最终潜力。为了实现这一目标，本文提出了以下问题：(1)PIR的信息论能力是什么？也就是说，在各种情况下，每个下载位可以私下检索的最大信息量是多少？(2) PIR的最优存储开销是多少？我们能在不复制存储数据的情况下实现隐私和高效通信（在下载和上传上）吗？(3)在存在诸如恶意或串通服务器、不同步数据和/或通信错误等障碍的情况下，如何保持隐私和下载效率？(4)分布式存储系统的代码容忍和修复节点故障，同时使数据同时可供多个用户使用。我们如何将PIR协议与这种编码结合起来？(5)在各种理想的PIR特性（如下载效率、存储开销和对错误/共谋/节点故障的弹性）之间的最佳权衡是什么？这一建议是私人机构和该领域其他机构最近开展的研究的自然结果。先前的相关工作将为本项目雄心勃勃的研究目标的快速进展提供跳板。通过这次调查获得的知识、技术和定性见解有望为该领域的基础做出贡献，并帮助弥合PIR理论和分布式存储实践之间的差距。

The digital age is predicated on information being ubiquitous. The ability to access relevant data stored on remote servers "in the cloud" has become an indispensable resource in everyday lives. Numerous online services let users query public datasets for data items such as map directions, stock quotes, and flight prices, to name a few. Digital content providers also rely on user queries to identify the content desired by the user. Unfortunately, such queries have the potential to reveal highly-sensitive information *about the users*, thereby compromising their privacy. For example, institutional investors querying a stock-market database for the value of certain stocks may prefer not to reveal their interest in these stocks since it could influence their price. As another example, most people are deeply uncomfortable with exposing their media consumption diet to a centralized server that can be targeted by hacking or subpoena. It can be convincingly argued that access to such media consumption profiles can reveal the person's sexual orientation, political leanings, and cultural affiliations.A great deal of research has been devoted to methods that guarantee the security and integrity of *the data*. Much less work, however, has been devoted to protecting the privacy of *the user*. Efficient and reliable retrieval of information from distributed databases, with information-theoretic guarantees of user privacy, is the focus of this project. The relevant area of research is known as private information retrieval. While most of the existing results in this area are theoretical, a major goal in this project is to bridge the gap between the theory of private information retrieval and the practice of distributed storage. As such, potential outcomes of this investigation may extend beyond the scope of academic research, contributing to new technologies and products.Private information retrieval (PIR), conceived in the seminal papers of Chor, Goldreich, Kushilevitz, and Sudan over 20 years ago, has been traditionally studied in theoretical computer science and cryptography, with emphasis on the complexity of the communication between the user and the servers that store the database. While major breakthroughs have been achieved in this area over the years, the prevailing paradigm has always been that of replicating the database on several non-communicating servers. Such replication leads to a significant storage overhead, which is undesirable. Moreover, motivated by advances in coding for distributed storage, it was recently recognized that if database replication is replaced by *database coding*, the full power of coding-theoretic methods can be brought to bear on the problem. While extremely promising, this line of research is still in its infancy. The goal of this project is to follow-up on the database coding idea, and follow it through to its ultimate potential. In pursuit of this goal, the following questions are addressed:(1) What is the information-theoretic capacity of PIR? That is, what is the maximum amount of information that can be privately retrieved per downloaded bit, under various scenarios?(2) What is the optimal storage overhead of PIR? Can we achieve both privacy and efficient communication (on the download and upload) without replicating the stored data even once?(3) How can both privacy and download efficiency be maintained in the presence of impediments such as malicious or colluding servers, unsynchronized data, and/or communication errors?(4) Codes for distributed storage systems tolerate and repair node failures while making the data available to several users at once. How can we combine PIR protocols with such coding?(5) What is the best possible tradeoff between the various desirable PIR features, such as download efficiency, storage overhead, and resilience to errors/collusions/node-failures?This proposal is a natural outgrowth of the research recently carried out by the PIs and others in this area. Prior related work will provide a springboard for rapid progress toward the ambitious research objectives of this project. Knowledge, techniques, and qualitative insights gained through this investigation are expected to contribute to the foundations of the field, and to help bridge the gap between the theory of PIR and the practice of distributed storage.