Effect of Full Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems

• URL: http://arxiv.org/abs/2510.25736v1
• Date: Wed, 29 Oct 2025 17:40:40 GMT
• Title: Effect of Full Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems
• Authors: Shreya Meel, Sennur Ulukus,
• Abstract summary: 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.
• Score: 43.914623898157856
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the problem of symmetric private information retrieval (SPIR) in settings where the database replication is modeled by a simple graph. Here, each vertex corresponds to a server, and a message is replicated on two servers if and only if there is an edge between them. To satisfy the requirement of database privacy, we let all the servers share some common randomness, independent of the messages. We aim to quantify the improvement in SPIR capacity, i.e., the maximum ratio of the number of desired and downloaded symbols, compared to the setting with graph-replicated common randomness. Towards this, we develop an algorithm to convert a class of PIR schemes into the corresponding SPIR schemes, thereby establishing a capacity lower bound on graphs for which such schemes exist. This includes the class of path and cyclic graphs for which we derive capacity upper bounds that are tighter than the trivial bounds given by the respective PIR capacities. For the special case of path graph with three vertices, we identify the SPIR capacity to be $\frac{1}{2}$.

Related papers

• 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)
• Private Information Retrieval for Graph-based Replication with Minimal Subpacketization [3.795745240553126]
  We design new minimal-subpacketization schemes for information-theoretic private information retrieval on graph-based replicated databases.<n>In graph-based replication, the system consists of $K$ files replicated across $N$ servers according to a graph with $N$ vertices and $K$ edges.<n>The client wants to retrieve one desired file, while keeping the index of the desired file private from each server via a query-response protocol.
  arXiv  Detail & Related papers  (2026-01-15T00:34:27Z)
• 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)
• 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)
• Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks [53.10674067060148]
  Shapley Interactions (SIs) quantify node contributions and interactions among multiple nodes.<n>By exploiting the GNN architecture, we show that the structure of interactions in node embeddings are preserved for graph prediction.<n>We introduce GraphSHAP-IQ, an efficient approach to compute any-order SIs exactly.
  arXiv  Detail & Related papers  (2025-01-28T13:37:44Z)
• Partition and Code: learning how to compress graphs [50.29024357495154]
  "Partition and Code" framework entails three steps: first, a partitioning algorithm decomposes the graph into elementary structures, then these are mapped to the elements of a small dictionary on which we learn a probability distribution, and finally, an entropy encoder translates the representation into bits. Our algorithms are quantitatively evaluated on diverse real-world networks obtaining significant performance improvements with respect to different families of non-parametric and parametric graph compressor.
  arXiv  Detail & Related papers  (2021-07-05T11:41:16Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

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.