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系统的整体信息论观点，为设计私密、安全、高效的信息检索系统提供重要的理论指导。在这个整体视图的框架中，该项目试图确定信息理论的限制，并为重要的系统约束（包括通信、存储、复杂性和安全性）之间的最佳权衡开发有效的代码结构。这种整体的观点超越了许多关注系统约束的单一方面，即通信成本的信息论研究。预计该项目将大大推进最先进的技术：它寻求对一般信息检索系统中不同约束之间的权衡提供更好的平衡和全面的理解。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.