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

点击翻译按钮获取中文摘要

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.