Private Information Retrieval With Arbitrary Privacy Requirements: Introduction and Capacity Results
- URL: http://arxiv.org/abs/2609.15875v1
- Date: Mon, 14 Sep 2026 17:03:36 GMT
- Title: Private Information Retrieval With Arbitrary Privacy Requirements: Introduction and Capacity Results
- Abstract summary: We introduce the problem of private information retrieval (PIR) under arbitrary privacy requirements, in a graph-based storage system.<n>This formulation is motivated by the server storage limitations, abundance of data (messages) and heterogeneous data privacy requirements.<n>We derive general lower and upper bounds on the PIR capacity for general graphs, under certain privacy requirements.
- Score: 39.20087907351314
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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 papers
- Local Private Information Retrieval for Graph-Based Replicated Systems [39.20087907351314]
We rethink the definition of privacy in multi-server, graph-replicated private information retrieval (PIR) systems.<n>In our proposed privacy setting, the user is concerned with hiding the message index from a particular server.<n>We coin this relaxed privacy requirement as local user privacy and the resulting PIR problem as local PIR on the graph.
arXiv Detail & Related papers (2026-08-31T17:50:47Z) - Weak Private Information Retrieval for Graph-based Storage [3.425341633647624]
Private information retrieval (G-PIR) on a graph-based storage system involves a client which seeks to retrieve a desired file via a query-response protocol.<n>We propose a G-WPIR scheme for arbitrary graphs, and identify the trade-offs it achieves between rate and privacy.
arXiv Detail & Related papers (2026-07-23T07:55:59Z) - Private Information Retrieval With Arbitrary Privacy Requirements for Graph-Based Storage [39.20087907351314]
We reformulate the definition of privacy in the private information retrieval problem to accommodate flexible privacy requirements.<n>We focus on graph-replicated PIR, with a generalized privacy requirement, instead of requiring all messages to be private from all servers.
arXiv Detail & Related papers (2026-05-11T17:27:33Z) - Local Private Information Retrieval: A New Privacy Perspective for Graph-Based Replicated Systems [39.20087907351314]
We introduce a novel setting where the user's privacy is governed by the servers' storage structure.<n>In particular, while retrieving a message from a server, the user is concerned with hiding their desired message index from the server.<n>We coin this privacy requirement as local user privacy and the resulting PIR problem as local PIR on the graph.
arXiv Detail & Related papers (2026-05-11T17:25:10Z) - The Role of Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems [43.914623898157856]
We study the problem of SPIR on graph-replicated database systems.<n>Each message is replicated at exactly two servers.<n>We quantify the minimum amount of common randomness required to achieve the capacity.
arXiv Detail & Related papers (2026-02-18T18:46:58Z) - Controlling What You Share: Assessing Language Model Adherence to Privacy Preferences [73.5779077857545]
We build a framework where a local model uses these instructions to rewrite queries, only hiding details deemed sensitive by the user, before sending them to an external model.<n>Experiments with lightweight local LLMs show that, after fine-tuning, they markedly exceed the performance of much larger zero-shot models.<n>At the same time, the system still faces challenges in fully adhering to user instructions, underscoring the need for models with a better understanding of user-defined privacy preferences.
arXiv Detail & Related papers (2025-07-07T18:22:55Z) - PGLP: Customizable and Rigorous Location Privacy through Policy Graph [68.3736286350014]
We propose a new location privacy notion called PGLP, which provides a rich interface to release private locations with customizable and rigorous privacy guarantee.
Specifically, we formalize a user's location privacy requirements using a textitlocation policy graph, which is expressive and customizable.
Third, we design a private location trace release framework that pipelines the detection of location exposure, policy graph repair, and private trajectory release with customizable and rigorous location privacy.
arXiv Detail & Related papers (2020-05-04T04:25:59Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.