Private Information Retrieval With Arbitrary Privacy Requirements: Introduction and Capacity Results
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.
Related
- The Capacity of Private Information Retrieval from Coded Storage Systems with Colluding, Robust and Byzantine Servers
- Mass-Capacity Rigidity for Asymptotically Flat Manifolds with Arbitrary Ends
- Asynchronous Replanning in Two Population Linear Quadratic Mean Field Games: Information Requirements and Stability
- Boolean threshold functions, neuron capacity, and memory retrieval
- Weak Private Information Retrieval for Graph-based Storage under ε-privacy
BibTeX
@misc{nomeir2026private,
title = {{Private Information Retrieval With Arbitrary Privacy Requirements: Introduction and Capacity Results}},
author = {Mohamed Nomeir and Shreya Meel and Sennur Ulukus},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15875},
eprint = {2609.15875},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15875},
}
RIS
TY - UNPB
TI - Private Information Retrieval With Arbitrary Privacy Requirements: Introduction and Capacity Results
AU - Mohamed Nomeir
AU - Shreya Meel
AU - Sennur Ulukus
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.15875
UR - https://arxiv.org/abs/2609.15875
AB - 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.
ER -