Local Private Information Retrieval: A New Privacy Perspective for Graph-Based Replicated Systems

• URL: http://arxiv.org/abs/2605.10872v1
• Date: Mon, 11 May 2026 17:25:10 GMT
• Title: Local Private Information Retrieval: A New Privacy Perspective for Graph-Based Replicated Systems
• Abstract summary: 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.
• Score: 39.20087907351314
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We rethink the definition of privacy in multi-server, graph-replicated private information retrieval (PIR) systems, and introduce a novel setting where the user's privacy is governed by the servers' storage structure. In particular, while retrieving a message from a server, the user is concerned with hiding their desired message index from the server, only if the server stores the corresponding message. We coin this privacy requirement as local user privacy and the resulting PIR problem as local PIR on the graph. Our goal is to measure the gain in communication efficiency of local PIR, compared to that of canonical PIR, by establishing its capacity, i.e., the maximum number of message symbols retrieved, per downloaded symbol. To this end, we observe a remarkable gain in the local PIR capacity of graphs, that are disjoint union of distinct graphs, which is multiplicative, compared to the PIR capacity, when the individual graphs are identical. For connected graphs, we propose schemes to establish capacity lower bounds for edge-transitive and bipartite graphs, which are greater than the best-known PIR capacity bounds. Finally, we derive the exact local PIR capacity for the cyclic graph, and the path graph with an odd number of vertices.

Related papers

• Private Information Retrieval With Arbitrary Privacy Requirements: Introduction and Capacity Results [39.20087907351314]
  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.
  arXiv  Detail & Related papers  (2026-09-14T17:03:36Z)
• 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)
• 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)
• Effect of Full Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems [43.914623898157856]
  We revisit the problem of symmetric private information retrieval in settings where the database replication is modeled by a simple graph.<n>We let all the servers share some common randomness, independent of the messages.<n>We quantify the improvement in SPIR capacity, i.e., the maximum ratio of the number of desired and downloaded symbols.
  arXiv  Detail & Related papers  (2025-10-29T17:40:40Z)
• Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems [43.914623898157856]
  symmetric private information retrieval on replicated databases modeled by a simple graph.<n>We consider the setting where the server-side common randomness necessary to accomplish SPIR is also replicated at the servers according to the graph.
  arXiv  Detail & Related papers  (2025-07-23T17:51:08Z)
• New Capacity Bounds for PIR on Graph and Multigraph-Based Replicated Storage [39.51026717015587]
  We study the problem of private information retrieval (PIR) in both graph-based and multigraph-based replication systems.<n>We derive upper bounds on the PIR capacity for such systems and construct PIR schemes that approach these bounds.
  arXiv  Detail & Related papers  (2025-04-29T16:05:42Z)
• Communication-Efficient Graph Neural Networks with Probabilistic Neighborhood Expansion Analysis and Caching [59.8522166385372]
  Training and inference with graph neural networks (GNNs) on massive graphs has been actively studied since the inception of GNNs. This paper is concerned with minibatch training and inference with GNNs that employ node-wise sampling in distributed settings. We present SALIENT++, which extends the prior state-of-the-art SALIENT system to work with partitioned feature data.
  arXiv  Detail & Related papers  (2023-05-04T21:04:01Z)
• Privatized Graph Federated Learning [57.14673504239551]
  We introduce graph federated learning, which consists of multiple units connected by a graph. We show how graph homomorphic perturbations can be used to ensure the algorithm is differentially private.
  arXiv  Detail & Related papers  (2022-03-14T13:48:23Z)

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.