Private Information Retrieval Over Networks
Abstract
Private information retrieval, PIR, refers to the problem of downloading information from publicly accessible databases such that no database individually learns anything about the identity of the downloaded message. In PIR, a user (retriever) designs a set of queries that it submits to the databases, such that, when the databases respond truthfully, the user can reconstruct the desired message, and at the same time, user queries leak no information about the userÕs interest in the desired message. PIR has originated in the computer science literature, in relatively simple and idealistic settings, such as, the availability of ideally replicated databases, availability of noiseless channels over which to access the databases, presence of only a single user accessing the databases with no network or side-information considerations, absence of any additional external security threats during the downloads, and so on. The goal of this proposed work is to develop a comprehensive information-, communication- and network-theoretic approach to the PIR problem, and conversely, to bring the PIR viewpoint to the problem of secure/private information dissemination in network settings. Specifically, our goal is to: 1) bring information-theoretic concepts such as capacity and capacity-achieving optimum retrieval schemes into various extended PIR settings; 2) introduce communication-theoretic concepts such as noisy channels, multi-accessing, broadcasting, resource allocation into realistic PIR formulations; 3) incorporate network-theoretic approaches such as multi-hop networks with various forms of side-information availability throughout the network (e.g., in the form of cached data) into new novel PIR formulations; and 4) conversely, bring the PIR viewpoint from the computer science community into the secure/private information dissemination problems in network information-theoretic and network communication-theoretic settings to enrich and expand security/privacy solutions over networks. The scientific goal of this project is to develop PIR solutions for general network structures applicable to the Army. Our proposed project has four major research thrusts: 1) arbitrary content PIR, where we consider arbitrary content placement in the databases that are neither replicated nor coded; 2) wiretapped PIR, where we consider the security of the downloaded information during the retrieval process against external adversaries together with the privacy of the data from the databases under various different eavesdropping scenarios; 3) wireless PIR, where we consider realistic noisy and fading wireless channels, multi-user access to databases, broadcast replies from the databases, device-to-device and peer-to-peer PIR, and joint optimization of communication rates and PIR rates; and 4) networked PIR, where we consider end-to-end private delivery in multi-hop networks with various forms of data cached at intermediate nodes with friendly and adversarial nodes in between. The main new capability that we will offer as a result of this proposed research is the ability to connect to information sources and extract information from them, without them being able to tell which information has been extracted. More generally, the proposed research will provide ability to route information in networks composed of friendly and unfriendly nodes without these nodes being able to understand the identity or the content of the routed information. The applications of this approach range from wireless ad-hoc networks to the cloud and data centers, and will provide a paradigm shift for information extraction, information security, and information privacy.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jul 09, 2020
- Source ID
- W911NF2010142
Entities
People
- Sennur Ulukus
Organizations
- Army Contracting Command
- United States Army
- University of Maryland