Private information retrieval with flexible privacy and storage limits
Private Information Retrieval With Arbitrary Privacy Requirements: Introduction and Capacity Results
Information TheoryCryptography and SecurityNetworking and Internet Architecture
Summary
The paper deals with how to get data secretly from multiple servers when each data piece needs different privacy rules. It extends traditional methods where every server must not know which data is asked for to cases allowing some servers to know certain queries. The authors study this in systems modeled as networks (graphs) of servers that store and share messages in various ways. They find limits and rules for how efficiently private retrieval can be done depending on these privacy and storage setups. They also introduce a new server structure that had not been studied before but looks balanced and simple.
What this means in practice
- •For cloud storage providers: Design private data retrieval systems tailored to different privacy needs and server storage patterns, improving flexibility and efficiency.
- •For network architects: Model and optimize data storage layouts that balance privacy constraints and retrieval efficiency using new graph structures introduced here.
Authors
Mohamed Nomeir, Shreya Meel, Sennur Ulukus
Abstract
In this paper, we introduce the problem of private information retrieval (PIR) under arbitrary privacy requirements, in a graph-based storage system. This formulation is motivated by the server storage limitations, abundance of data (messages) and heterogeneous data privacy requirements. Under the arbitrary privacy requirement, each message has to be retrieved privately from a pre-specified subset of servers, where the subset always includes the servers storing it. Thus, each server is associated with a privacy set, which pre-specifies the message indices that should be privately retrieved from it. This setting is a generalization of the classical PIR setting, where the required message index needs to be kept private from all servers, i.e., there, the privacy set of each server comprises all message indices. Our setting is also a bridge between the newly formulated local PIR (LPIR) setting and the classical PIR setting, where in the former, the privacy set is exactly the set of stored message indices. In this paper, we derive general lower and upper bounds on the PIR capacity for general graphs, under certain privacy requirements, that capture the essence of both LPIR and classical PIR. Then, we focus on path and cyclic storage graphs under these and more fine-grained settings, for which we derive capacity results for certain cases, and establish lower and upper bounds for others. Their low degree allows for a more in-depth understanding of the new privacy formulation and admits more privacy requirement settings compared to other simple graphs. Finally, we introduce a new graph structure, the pyramid storage graph, to model server storage. Although this graph has never been investigated in the literature in any PIR context, it enjoys a nice symmetric structure for message storage and replication patterns.