CS Paper Radar

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

Mohamed Nomeir, Shreya Meel, Sennur Ulukus

cs.IT cs.CRcs.NIeess.SP ·submitted 2026-09-14 17:03 UTC · v1

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.

Comment
Abstract is trimmed for space limitations

Closest papers

Nearest neighbours by meaning across the whole index.

Local Private Information Retrieval for Graph-Based Replicated Systems

cs.IT cs.CRcs.DBcs.NI+1 ·2026-08-31 ·Shreya Meel, Mohamed Nomeir, Sennur Ulukus
similarity 0.89
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.

0.49

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

cs.IT ·2026-10-14 ·Jayesh Seshadri, Prasad Krishnan
theory similarity 0.84
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

Doubly-Efficient Private Information Retrieval from Modular Forms

cs.CR math.NT ·2026-11-09 ·Alexandra Henzinger, Seyoon Ragavan
similarity 0.70
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.70
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

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.70
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

ObliGraph: Graph Pattern Query Processing with Full and Differential Obliviousness

cs.DS ·2026-11-19 ·Lyu Xu, Xinyi Zhang, Qichen Wang
similarity 0.67
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

Private Online Release of Adaptive Linear Queries

cs.DS ·2026-11-03 ·Aleksandar Nikolov, Haohua Tang
theory similarity 0.66
Abstract

In this paper we study answering counting and other linear queries online under differential privacy constraints. Recent work by Nikolov, Tang, and Ullman [STOC 2026] gave the first online algorithm that answers \emph{obliviously chosen} online linear queries privately, and achieves poly-logarithmic competitiveness against an optimal offline factorization mechanism. This also implied poly-logarithmic competitiveness against arbitrary private offline mechanisms when the private dataset is large enough. The error guarantees of their algorithm, however, can fail when the queries are adaptive. We give a new algorithm that also achieves poly-logarithmic competitiveness, while being able to handle \emph{adaptively chosen} queries. This implies that there is no large separation between the optimal error bounds for privately answering, respectively, offline linear queries, obliviously chosen online linear queries, and adaptively chosen online linear queries. Our algorithm combines the online factorization approach from prior work with a novel layered Euclidean iterative database construction, presenting a new way to use factorization in private algorithms. We also give a lower bound that shows that some poly-logarithmic factor in the competitive ratio is unavoidable. Our lower bound first shows that any interactive private mechanism implies a deterministic online factorization algorithm, and then gives a new lower bound for the competitive ratio of any deterministic online factorization algorithm.

0.06

Privacy-Constrained Function Computation in Distributed Databases

cs.IT ·2026-10-29 ·Vamoua Yachongka, Rémi A. Chou
published similarity 0.66
Abstract · A preliminary version of this paper was presented at IEEE ISIT 2025

Consider distributed databases that contain both sensitive (private) and non-sensitive (public) attributes. A user seeks to compute a function of public attributes and side information by interacting with the databases and downloading their responses. In this paper, we study the trade-offs among download cost, information leakage about the private attributes, and distortion between the computed function and its reconstruction, referred to as the capacity region. Our main contributions are as follows. For a single database, we provide a complete characterization of the capacity region for general discrete sources and characterize the capacity region of two different setups for Gaussian sources when the computed function is defined as the sum of the public attribute and side information. For distributed databases, we establish inner and outer bounds on the capacity region of discrete sources and we characterize the capacity region when the databases and the side information are mutually independent. As a special instance, we study lossless function computation, and results analogous to the lossy case are obtained.

0.34