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

CCF-BSF：CIF：小型：分布式信息检索：私密、可靠且高效

• 批准号: 1719139
• 负责人: Alexander Vardy
• 金额: $ 45万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1719139&HistoricalAwards=false
• 关键词: CCF; BSF; CIF; Small; Distributed

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.

数字时代是基于无处不在的信息。访问远程服务器上存储的相关数据“在云中”的能力已成为日常生活中必不可少的资源。众多在线服务使用户可以查询公共数据集，以了解一些数据项，例如地图方向，股票报价和飞行价格。数字内容提供商还依靠用户查询来识别用户所需的内容。不幸的是，此类查询有可能揭示有关用户 *的高度敏感信息 *，从而损害其隐私。例如，机构投资者向股市数据库查询某些股票的价值可能不愿意揭示其对这些股票的兴趣，因为这可能会影响其价格。作为另一个例子，大多数人对将其媒体消费饮食暴露于可以通过黑客或传票来针对的集中式服务器感到非常不舒服。可以令人信服地认为，获得此类媒体消费概况可以揭示该人的性取向，政治倾向和文化隶属关系。大量研究致力于保证 *数据 *的安全性和完整性 *的方法。但是，工作的工作少得多，致力于保护 *用户 *的隐私。该项目的重点是用户隐私的信息理论保证，从分布式数据库中有效且可靠地检索信息。研究领域称为私人信息检索。尽管该领域的大多数现有结果都是理论上的，但该项目的主要目标是弥合私人信息检索理论与分布式存储实践之间的差距。因此，这项调查的潜在结果可能超出了学术研究的范围，为新技术和产品做出了贡献。尽管多年来在这一领域取得了重大突破，但普遍的范式一直是将数据库复制到几个非通信服务器上。这样的复制导致大量存储开销，这是不可取的。此外，由于编码分布式存储的进步的动机，最近人们认识到，如果数据库复制被 *数据库编码 *取代，则可以将编码理论方法的全部功能带入问题上。尽管非常有前途，但这种研究仍处于起步阶段。该项目的目的是跟进数据库编码的想法，并遵循其最终潜力。为了实现这一目标，解决了以下问题：（1）PIR的信息理论能力是什么？也就是说，在各种情况下，可以私下检索到可以私下检索的最大信息？（2）PIR的最佳存储开销是什么？我们可以在不复制存储数据的情况下实现隐私和有效的沟通（在下载和上传）吗？（3）如何在存在障碍的情况下保持隐私和下载效率，例如恶意或串联服务器，不同步的数据以及/或通信错误？我们如何将PIR协议与此类编码相结合？（5）各种理想的PIR功能（例如下载效率，存储开销和对错误/碰撞/节点 - 费用的弹性）之间最好的折衷是什么？这项提议是最近在此领域进行的PIS和其他研究的自然产物。先前的相关工作将为朝着该项目的雄心勃勃的研究目标提供快速进步的跳板。通过这项调查获得的知识，技术和定性见解有望为该领域的基础做出贡献，并有助于弥合PIR理论与分布式存储实践之间的差距。

项目成果

Private Proximity Retrieval

• DOI: 10.1109/isit.2019.8849249
• 发表时间: 2019-07
• 期刊: 2019 IEEE International Symposium on Information Theory (ISIT)
• 作者: T. Etzion;O. W. Gnilke;David A. Karpuk;Eitan Yaakobi;Yiwei Zhang

Probabilistic existence of large sets of designs

大量设计的概率存在

• DOI: 10.1016/j.jcta.2020.105286
• 发表时间: 2020
• 期刊: Series A
• 作者: Lovett, Shachar;Rao, Sankeerth;Vardy, Alexander
• 通讯作者: Vardy, Alexander

Codes for Endurance-Limited Memories

耐力有限记忆的代码

• DOI: 10.23919/isita.2018.8664328
• 发表时间: 2018
• 期刊: Proceedings of the IEEE International Symposium on Information Theory and its Applications (ISITA
• 作者: Chee, Yeow Meng;Horovitz, Michal;Vardy, Alexander;Vu, Van Khu;Yaakobi, Eitan
• 通讯作者: Yaakobi, Eitan

Reconstruction from Deletions in Racetrack Memories

从赛马场记忆中的删除中重建

• DOI: 10.1109/itw.2018.8613352
• 发表时间: 2018
• 期刊: Proceedings of the IEEE Information Theory Workshop (ITW
• 作者: Chee, Yeow Meng;Gabrys, Ryan;Vardy, Alexander;Vu, Van Khu;Yaakobi, Eitan
• 通讯作者: Yaakobi, Eitan

Explicit and Efficient WOM Codes of Finite Length

显式高效的有限长度WOM代码

• DOI: 10.1109/tit.2019.2946483
• 发表时间: 2020
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Chee, Yeow Meng;Kiah, Han Mao;Vardy, Alexander;Yaakobi, Eitan
• 通讯作者: Yaakobi, Eitan