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

数字时代的前提是信息无处不在。访问存储在“云”远程服务器上的相关数据的能力已成为日常生活中不可或缺的资源。许多在线服务允许用户查询公共数据集的数据项，如地图方向，股票报价和航班价格，仅举几例。数字内容提供商还依赖于用户查询来识别用户期望的内容。不幸的是，这样的查询有可能泄露用户的高度敏感信息，从而损害他们的隐私。例如，机构投资者在查询股票市场数据库中某些股票的价值时，可能不愿意透露他们对这些股票的兴趣，因为这可能会影响它们的价格。另一个例子是，大多数人对将他们的媒体消费饮食暴露在一个集中的服务器上感到非常不舒服，这个服务器可能会成为黑客或传票的目标。可以令人信服地认为，访问这些媒体消费档案可以揭示一个人的性取向，政治倾向和文化背景。大量的研究已经致力于保证数据安全和完整的方法。然而，致力于保护用户隐私的工作却少得多。从分布式数据库中高效可靠地检索信息，并保证用户隐私的信息理论，是该项目的重点。相关的研究领域被称为私人信息检索。虽然这一领域的大多数现有成果都是理论性的，但本项目的一个主要目标是弥合私人信息检索理论与分布式存储实践之间的差距。因此，这项研究的潜在成果可能会超出学术研究的范围，有助于新的技术和产品。私人信息检索（PIR），在20多年前Chor，Goldreich，Kushilevitz和Sudan的开创性论文中构思，传统上一直在理论计算机科学和密码学中研究，重点是用户和存储数据库的服务器之间通信的复杂性。虽然多年来在这一领域取得了重大突破，但普遍的模式一直是在几个不通信的服务器上复制数据库。这样的复制导致显著的存储开销，这是不期望的。此外，由于分布式存储编码的进步，最近人们认识到，如果数据库复制被 * 数据库编码 * 所取代，那么编码理论方法的全部力量就可以解决这个问题。虽然非常有前途，但这一研究仍处于起步阶段。这个项目的目标是跟进数据库编码的想法，并遵循它的最终潜力。在追求这一目标，解决了以下问题：（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.