Local Private Information Retrieval for Graph-Based Replicated Systems

• URL: http://arxiv.org/abs/2608.31150v1
• Date: Mon, 31 Aug 2026 17:50:47 GMT
• Title: Local Private Information Retrieval for Graph-Based Replicated Systems
• Abstract summary: 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.
• 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, by introducing a novel setting where the user's privacy is governed by the servers' storage structure. In classical graph-replicated PIR, the user retrieves a single message stored at the servers, while hiding the message index from each server. In our proposed privacy setting, the user is concerned with hiding the message index from a particular server, only if that server stores the message being retrieved, and privacy is not imposed otherwise. We coin this relaxed privacy requirement as local user privacy and the resulting PIR problem as local PIR on the graph. Our focus is on two-replicated PIR systems, where every message is replicated twice and stored on two distinct servers. Specifically, we study local PIR systems where the storage is represented by simple graphs, i.e., every pair of vertices is associated with at most one edge, and by their multigraph extension, i.e., $r$ parallel edges replace every edge. For these settings, we establish bounds on the local PIR capacity, defined as the maximum number of message symbols retrieved, per downloaded symbol. The local privacy requirement yields significant capacity gain over the classical PIR capacity under the same storage structure. For instance, in settings where the graph is a disjoint union of multiple identical sub-graphs, the gain in the local PIR capacity over classical PIR capacity is multiplicative in the number of sub-graphs. Further, for connected graphs, we derive capacity lower bounds for edge-transitive and bipartite graphs, which are greater than the best-known PIR capacity bounds. From these and by establishing matching upper bounds, we exactly characterize the capacity for star graphs, cyclic graphs, and path graphs with odd number of vertices. We introduce two local PIR schemes for general graphs.

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: 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)
• 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)
• Align-GRAG: Reasoning-Guided Dual Alignment for Graph Retrieval-Augmented Generation [79.75818239774952]
  Large language models (LLMs) have demonstrated remarkable capabilities, but still struggle with issues like hallucinations and outdated information.<n>Retrieval-augmented generation (RAG) addresses these issues by grounding LLM outputs in external knowledge with an Information Retrieval (IR) system.<n>We propose Align-GRAG, a novel reasoning-guided dual alignment framework in post-retrieval phrase.
  arXiv  Detail & Related papers  (2025-05-22T05:15:27Z)
• Private Information Retrieval on Multigraph-Based Replicated Storage [39.51026717015587]
  We consider the private information retrieval problem for a multigraph-based replication system.<n>Our goal is to establish upper and lower bounds on the PIR capacity of the $r$-multigraph.
  arXiv  Detail & Related papers  (2025-01-29T18:48:22Z)
• 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.