CS Paper Radar

Local Private Information Retrieval for Graph-Based Replicated Systems

Shreya Meel, Mohamed Nomeir, Sennur Ulukus

cs.IT cs.CRcs.DBcs.NIeess.SP ·submitted 2026-08-31 17:50 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Private Information Retrieval With Arbitrary Privacy Requirements: Introduction and Capacity Results

cs.IT cs.CRcs.NIeess.SP ·2026-09-14 ·Mohamed Nomeir, Shreya Meel, Sennur Ulukus
similarity 0.89
Abstract · Abstract is trimmed for space limitations

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.

0.23

Weak Private Information Retrieval for Graph-based Storage under $ε$-privacy

cs.IT ·2026-10-14 ·Jayesh Seshadri, Prasad Krishnan
theory similarity 0.83
Abstract

The problem of Private Information Retrieval (PIR) across graph-based replicated systems has seen a surge of interest in recent literature. In such systems, servers are modeled as the vertices of a graph, and each file is represented by an edge connecting the pair of servers that store it. While previous research on Graph-PIR (G-PIR) has focused mostly on perfect information-theoretic privacy, relaxing this constraint has the potential for significantly higher retrieval rates. In this work, we consider the setting of Graph-based Weak Private Information Retrieval (G-WPIR), under an $ε$-privacy metric. We adapt an existing G-WPIR scheme for arbitrary graphs to analyze its performance under the $ε$-privacy metric. Additionally, we establish a lower bound on the expected download cost for arbitrary graphs under the $ε$-privacy metric and derive from it an explicit rate upper bound for complete graphs. Finally, we show the achievable rate-privacy trade-offs for two specific graph classes---complete graphs and complete bipartite graphs.

0.11

Amora: Communication-Efficient Private Approximate Nearest Neighbors Search

cs.DB cs.CR ·2026-10-15 ·Qiuhao Wang, Zuowei Chen, Xu Yang, Saiyu Qi, Yong Qi
top venue similarity 0.71
Abstract · Accepted at SIGMOD 2027

Approximate nearest neighbors search (ANNS) over cloud-hosted vector databases raises a critical privacy concern: the query vector, which often encodes sensitive user intent, is exposed to the server. Private ANNS (PANNS) allows a client to retrieve nearest neighbors without revealing its query. The state-of-the-art single-server scheme, Pacmann (ICLR'25), achieves high accuracy via graph-based search with private information retrieval (PIR), but incurs substantial communication overhead because each PIR query retrieves only a single vertex. We present Amora, a communication-efficient PANNS system that applies SimplePIR to a partitioned graph index so that one PIR query is amortized over many vertices. To retrieve as much of the distance and neighbor information the search needs under a limited communication budget, Amora adopts a dual-PIR split layout with two heterogeneous PIR matrices that stay balanced in dimension: VecPIR retrieves inner products for an entire partition of vertices as their distance at once, while NbrPIR retrieves necessary neighbor lists at subgroup granularity for graph traversal. This layout shifts the cost model of PIR query from per-vertex to per-partition, which significantly reduces the communication overhead. To further improve efficiency by reducing the number of scans and query rounds in the PIR database, Amora introduces batch PIR to pack multiple queries into one matrix multiplication, centroid-based pruning to filter unpromising partitions, and TopCand exploration that seeds jump-style graph navigation with the closest vertices from each retrieved partition. We evaluate Amora on five datasets spanning 96 to 1024 dimensions and up to 10 million vectors. Compared to Pacmann, Amora reduces online communication by 93--99% while achieving higher search accuracy.

0.37

Doubly-Efficient Private Information Retrieval from Modular Forms

cs.CR math.NT ·2026-11-09 ·Alexandra Henzinger, Seyoon Ragavan
similarity 0.68
Abstract

We present new information-theoretic protocols for $s$-server, doubly-efficient private information retrieval (PIR) in sublinear server time and one extra bit of space on the servers, for every constant $s \geq 2$. On an $n$-bit database, each of the $s$ PIR servers first builds and stores a preprocessing data structure consisting of $n+1$ bits (which is unique to each server, and after which the server may discard the original database). Then, each server answers a PIR query in time $T_s(n)$, by reading at most $T_s$ bits of its data structure and sending them to the user. In the two server setting ($s=2$), our PIR protocols achieve $T_2 = n^{0.82}$, matching the server time of the state-of-the-art schemes of Henzinger and Ragavan (EUROCRYPT 2026) while shrinking their storage from $O(n\sqrt{\log n})$ to $n+1$ bits. With $s \geq 3$ servers, our PIR protocols retain the $n+1$ bits of storage and additionally improve on the server time of all prior information-theoretic $s$-server schemes with $n^{1+o(1)}$ storage: for example, achieving $T_3 = n^{0.74}$ and $T_{10} = n^{0.61}$ (previously $n^{0.79}$ and $n^{0.75}$). Asymptotically, as the server count $s$ grows, we shrink the number of servers required to achieve a given server-work exponent from $s^{3.9}$ to $s$. Our results draw inspiration from matching-vector techniques (Efremenko, STOC 2009), which we generalize to handle degree-two computations in the exponent. Using this generalization, we build doubly-efficient PIR from the new intermediate abstraction of Fourier-sparse cone-delta functions. Then, we construct such Fourier-sparse cone-delta functions via a connection to modular forms and complex analysis: if a Fourier-sparse cone-delta function does not exist, then there exists a modular form which has too many roots, contradicting the valence formula.

0.24

Sequential Random Sampling PIR with Multiple Colluding Servers in DNA-Based Data Storage

cs.IT ·2026-10-07 ·Chen Wang, Natalia Silberstein, Eitan Yaakobi
similarity 0.68
Abstract

As DNA-based data storage evolves, protecting user privacy during data retrieval has become increasingly important. We study sequential random sampling DNA private information retrieval (SRS DNA PIR) with multiple colluding random sampling servers, where the database is partitioned into servers of equal size. We investigate the tradeoff between the download cost, defined as the expected number of queries, and the privacy leakage, measured by mutual information. We derive lower bounds on this tradeoff, including a bound given by an optimization problem. This bound is tight when each server stores two files, and we construct schemes that attain it. For servers of any size, we construct schemes that apply a single-server scheme to a randomly selected subset of servers.

0.16

Quantum Private Information Retrieval on Forests

cs.IT cs.CRcs.NIeess.SP+1 ·2026-11-02 ·Mohamed Nomeir, Sennur Ulukus
theory similarity 0.64
Abstract

We consider the problem of graph private information retrieval (PIR) in the quantum setting. We focus on a specific type of graphs, namely the forest graphs. A forest graph is a union of disjoint trees. We consider the quantum setting where all the servers share an entangled state. Each server is allowed to send only one qudit per retrieval round. We design a scheme for the forest graphs that achieves the rate of $\frac{3}{N}$. The scheme uses a GHZ state as the initial entangled state between the servers prior to the scheme initiation. We compare our scheme with the only work done in the literature that considered the quantum setting of graph PIR. We show that our scheme is more efficient in this setting. We derive the quantum capacity for the case of $G=3K_2$, which is equal to $4/6$. $G=3K_2$ is a special case of the forest graph. We design a scheme that is specialized for this graph, achieving a rate equal to $4/6$ and provide the corresponding matching upper bound, establishing it as the capacity.

0.23

Communication and Privacy Trade-Offs in Distributed Storage With Shared Secret Keys

cs.IT ·2026-10-29 ·Maryam Keshvari, Remi A. Chou
published similarity 0.63
Abstract · A preliminary version of this work was presented at the 2023 Allerton Conference on Communication, Control, and Computing

We study distributed storage over public communication channels where privacy is realized using shared secret keys. Specifically, a user wishes to store a file across $L$ servers such that any subset of at least $t$ servers can reconstruct the file, while any subset of at most $z$ colluding servers learns no more than a fraction $α$ of the file. Unlike classical secret-sharing models that assume secure communication channels between the user and each server, we consider a setting where all transmissions occur over a public channel and the user shares an individual secret key of length $n$ bits with each server. For a fixed key length $n$, we characterize the trade-off between the privacy leakage parameter $α$ and the maximum file size that can be securely stored. Additionally, we determine the minimum local randomness, public communication, and storage required to achieve this optimal trade-off.

0.27

ObliGraph: Graph Pattern Query Processing with Full and Differential Obliviousness

cs.DS ·2026-11-19 ·Lyu Xu, Xinyi Zhang, Qichen Wang
similarity 0.61
Abstract

Graph pattern query is a fundamental primitive in graph databases for retrieving data graphs that match a query graph under various structural constraints. As graph data is increasingly outsourced to third-party cloud servers for scalable query processing, however, both the query graph and the data graphs may leak sensitive structural information through server-side access patterns. In this paper, we study privacy-preserving graph pattern query processing in the outsourced setting, aiming to protect the structures of both the query and data graphs from access-pattern leakage. To this end, we propose $\mathsf{ObliGraph}$, the first oblivious graph search framework that supports multiple classes of graph pattern queries under two privacy modes: $\mathsf{FOS}$ achieves full obliviousness by uniformly evaluating candidate mappings, making the server-side access pattern independent of the structures of the query and data graphs; $\mathsf{DOS}$ further improves query efficiency through pruning while retaining a provable privacy guarantee of differential obliviousness. This design enables a smooth trade-off between stronger privacy and higher efficiency within a single framework. Experiments on real and synthetic datasets demonstrate that $\mathsf{ObliGraph}$ efficiently supports a range of graph pattern queries, achieving substantial improvements while preserving strong privacy guarantees.

0.33