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制度的有用性。本项目旨在建立一个完整的个人信息检索系统的信息论观点，为设计私密、安全、高效的信息检索系统提供重要的理论指导。在这种整体观点的框架下，该项目试图确定信息理论的限制，并开发有效的代码构造，以在重要的系统约束(包括通信、存储、复杂性和安全性)之间进行最佳权衡。这种整体观点超越了许多信息理论研究，这些研究侧重于系统约束的一个方面，即通信成本。预计该项目将大大推进最先进的技术：它寻求对一般信息检索系统中不同限制之间的权衡提供更好的平衡和全面的理解。该奖项反映了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.