Collaborative Research: CIF: Small: Communication, Storage, Complexity, and Security: A Holistic View on the Fundamental Limits and Code Designs for Private Information Retrieval

如今，功能强大且无处不在的传感器和设备可以收集各种人类活动和自然现象的数据。这些数据集通常被聚合并存储在分布式存储系统中，然后可以根据需要从该系统中检索信息以进行处理和计算。使这样的系统的私人和安全是至关重要的，这激发了私人信息检索（PIR）系统的研究，它可以提供强大的隐私保证访问这些数据库中的信息。确定担保水平有助于评估PIR制度的效用。本项目旨在发展一个PIR系统的整体信息论观点，这可以为设计私有的，安全的，高效的信息检索系统提供重要的理论指导。在这个整体观点的框架下，该项目旨在确定信息理论的限制，并开发有效的代码结构，以实现重要系统约束（包括通信、存储、复杂性和安全性）之间的最佳权衡。这种整体观点超越了许多信息理论研究，这些研究集中在系统约束的一个方面，即通信成本。该项目预计将显着推进国家的最先进的：它旨在提供一个更好的平衡和全面的理解之间的权衡不同的限制，在一般的信息检索systems.This奖项反映了NSF的法定使命，并已被认为是值得的支持，通过评估使用基金会的智力价值和更广泛的影响审查标准。

Powerful and ubiquitous sensors and devices nowadays can collect data on all types of human activities and natural phenomena. These data sets are usually aggregated and stored in a distributed storage system, from which information can then be retrieved as needed for processing and computation. Making such systems private and secure is of paramount importance, which has motivated the study of private information retrieval (PIR) systems, which can provide strong privacy guarantees on the access to information in these databases. Characterizing the level of guarantees will help assess the usefulness of a PIR system. This project aims to develop a holistic information theoretic view of PIR systems, which can provide important theoretical guidance on the design of private, secure, and efficient information retrieval systems. In the framework of this holistic view, this project seeks to identify the information theoretic limits and develop efficient code constructions for the optimal tradeoffs between important system constraints, including communication, storage, complexity, and security. This holistic view goes beyond many information theoretic studies that focus on a single aspect of the system constraints, namely the communication cost. The project is expected to significantly advance the state-of-the-art: it seeks to provide a better balanced and comprehensive understanding on the tradeoffs between different constraints in general information retrieval systems.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.