Source-linked AI summary
Local Private Information Retrieval for Graph-Based Replicated Systems
Shreya Meel, Mohamed Nomeir, Sennur Ulukus
TL;DR
Classical graph-replicated PIR imposes index privacy even at servers that do not store the requested message, motivating a storage-aware relaxation. The paper defines local PIR, develops schemes and capacity bounds for two-replicated simple graphs and multigraphs, and exactly characterizes several graph families. Local privacy improves communication efficiency over classical PIR, while capacities for many other graph and multigraph cases remain open.
Problem
Classical graph-replicated PIR requires uniform index privacy from every server, including servers that do not store the requested message.
Method
The paper studies two-replicated storage represented by simple graphs and r-multigraphs, deriving capacity bounds and two local PIR schemes for general graphs.
Results
Local privacy improves communication efficiency, with exact capacities established for star graphs, cyclic graphs, and odd-vertex path graphs.
Takeaways & Limitations
Local PIR capacity decays more slowly than standard PIR capacity as the number of servers increases, and cyclic and path graphs achieve O(N)-times improvement.
Takeaways & Limitations
Exact or approximate capacities remain uncharacterized for graphs beyond star, cyclic, and path families, and most multigraph capacity bounds remain open.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper introduces local user privacy for graph-replicated PIR, requiring index privacy only from servers storing the requested message. It develops capacity bounds and schemes for simple graphs and multigraphs, showing improvements over classical graph-based PIR.
- Problem setting: Local user privacy hides the requested index from a server only when that server stores the requested message.The relaxation follows the storage architecture while retaining perfect privacy against servers storing the desired message.
- Simple-graph results: Identical disjoint unions of m connected subgraphs improve local PIR capacity over standard PIR by at least a factor of m.The paper compares these local-PIR results with standard graph-based PIR capacity.
- Simple-graph results: The cyclic graph with N vertices has local PIR capacity 1/2, independent of the number of servers, versus PIR capacity 2/(N+1).The local capacity follows from a lower bound and matching converse.
- Schemes and extensions: For star graphs, a bipartite-graph scheme achieves local PIR capacity 1 and improves over PIR by a factor of N.The paper also derives general lower-bound schemes from complete graphs and a minimally subpacketized alternative.
- Multigraph extension: For r-multigraphs, the proposed schemes multiply their corresponding simple-graph local PIR rates by (2 − 2^(1−r))^−1.One scheme increases subpacketization by 2^(r−1), while the other keeps subpacketization at 1.
2 System Model and Preliminaries
The system models two-replicated message storage with graphs and defines local PIR by requiring privacy only from servers storing the requested message. It specifies achievable rates and capacity, then illustrates the formulation with cyclic, star, and complete-graph examples.
- Problem Setting: Simple Graphs: Messages are independent vectors of L uniformly random symbols over Fq, and queries are independent of message contents.Servers produce answers deterministically from their received queries and stored symbols, while the desired message must be decoded exactly.
- Problem Setting: Simple Graphs: Each vertex is a server and each edge is a message replicated at its two incident servers.A simple graph with N vertices and K edges therefore represents N servers and K twice-replicated messages.
- Problem Setting: Simple Graphs: Local PIR hides the requested index from servers storing that message, unlike classical graph-based PIR, which requires privacy from every server.The relaxation is tied to the storage structure and is the main distinction between the two formulations.
- Definitions: The local PIR rate is retrieved message symbols divided by downloaded symbols, and capacity is the supremum of this rate over achievable schemes.The paper denotes local capacity by C(G) and classical PIR capacity for the same graph by C_PIR(G).
- Motivating Examples: Relaxed privacy guarantees C(G) ≥ C_PIR(G) for every graph, while cyclic and complete-graph examples demonstrate concrete rate improvements.For C4, the scheme downloads one symbol from each database; for K4, it retrieves 4 symbols using 10 downloads, giving rate 0.4 versus a classical upper bound of 0.3529.
- Definitions: The framework covers graph families including disjoint unions and bipartite graphs, whose structural definitions support subsequent capacity results and schemes.A disjoint union connects local PIR rates to component graphs, while bipartite structure supplies vertex covers and independent sets used in scheme design.
3 Main Results for Simple Graphs
For simple graphs, the paper develops local PIR bounds and schemes, showing gains over standard PIR and exact capacities for several graph families. It also treats disconnected and connected graphs, including bipartite, cyclic, star, and odd-length path graphs.
- Disjoint unions: Identical disjoint components preserve local PIR capacity while providing a multiplicative gain over standard PIR capacity.For m identical components, the local capacity equals the capacity of one component, whereas the corresponding standard PIR capacity is reduced by the number of components.
- Connected graphs: Edge-transitive graphs admit general local PIR capacity lower bounds, recovering rates for cyclic and complete graphs.The construction uses the common subgraph associated with each replicated message and extends a scheme from complete graphs to connected graph subgraphs.
- Bipartite graphs: Bipartite graphs have a local PIR lower bound that uses the two independent vertex-cover parts and supports minimal subpacketization.For star graphs, this bound identifies local PIR capacity as 1; for odd path graphs, it improves the earlier lower bound.
- Graph-family comparisons: Table 5 reports achievable local PIR rates that exceed the corresponding standard PIR capacities for all listed common graph families.The comparison covers exact or approximate PIR capacities, with unavailable results marked by a hyphen.
- Exact capacities: Local PIR capacities are exactly characterized for cyclic graphs and for path graphs with odd numbers of vertices.The cyclic-graph result follows from matching bounds, while the odd-path result matches the achievable rate and equals N−1 over 2N−4.
- Asymptotic behavior: For paths, cycles, and stars, local PIR capacity remains strictly above zero as N grows, unlike standard PIR capacity, which vanishes asymptotically.For graphs whose every vertex has degree at least two, a general upper bound of 1/2 also applies.
4 Proofs of Capacity Lower Bounds
The paper constructs achievable local PIR schemes for graph families by querying structured sums and downloading interference symbols. These schemes preserve local privacy and optimize rates over graph-specific parameters.
- General graph schemes: The schemes communicate only with servers associated with the desired message and query sums over stored-message index sets.Interference symbols are downloaded from remaining servers to support decoding.
- Rate optimization: The achievable rate is maximized over the allowable choices of the scheme parameters at the two servers storing the desired message.For edge-transitive graphs, the same construction applies across equivalent desired-message positions.
- Privacy: Private independent symbol permutations hide the queried symbol indices while maintaining identical query structures for possible desired messages.This establishes local privacy at servers storing the desired message.
- Example: K2,3: For K2,3, the construction with ti = 2 and tj = 1 uses L = 3 and achieves rate 3.The example instantiates the sets used for desired and interference queries.
5 Proofs of Capacity Upper Bounds
The upper-bound proofs combine decodability, local-privacy entropy identities, and graph-specific interference inequalities. For cyclic and path structures, cyclic indexing and degree assumptions enable summing bounds across messages.
- General upper-bound framework: The proofs lower-bound total download by separating desired-message recovery from interference terms in the servers’ answers.The resulting bounds sum download costs over all desired-message indices.
- Privacy inequalities: Local privacy makes answer entropies conditionally invariant across message indices stored at the same server.This is formalized through entropy relations for arbitrary subsets of messages.
- Pairwise bounds: For adjacent servers sharing a message, decodability bounds the interference carried by paired answers.The argument applies the corresponding two-server lemma to answer pairs with the same message index.
- Cyclic graphs: For cyclic graphs, modulo-N indexing relates neighboring answer terms and permits summing interference inequalities over all desired indices.The storage convention assigns each server its two neighboring messages.
- Degree-based argument: For the general degree-based argument, assuming every vertex has degree at least 2 ensures distinct neighboring message indices needed to propagate the entropy bounds.Simplicity guarantees the two newly identified indices differ.
6 Generalizing to Multigraphs
The paper extends local PIR from simple graphs to r-multigraphs by replacing each edge with r parallel message replicas. It derives transferable lower bounds, graph-family bounds, and explicit subpacketization trade-offs.
- Problem setting: An r-multigraph replaces each simple-graph edge with r parallel edges and stores r messages at the same pair of servers.The desired index becomes a tuple identifying an edge and one of its r replicas.
- Scheme extension: A simple-graph scheme satisfying symmetric retrieval can be adapted to the corresponding multigraph, yielding a capacity lower bound.The construction privately permutes message symbols and partitions each server’s index set into r subsets.
- Subpacketization trade-off: The transferred construction increases subpacketization by a factor of 2^r−1, which may be impractical for smaller messages.A separate construction targets minimal subpacketization L = 1.
- Capacity behavior: Local PIR capacity cannot increase with r because larger replication imposes stricter local privacy constraints, making the simple-graph capacity an upper bound.The paper also reports positive lower bounds from schemes that extend beyond the direct bipartite construction.
7 Conclusion
The paper argues that local privacy is a reasonable alternative for graph-replicated PIR because it avoids the capacity degradation caused by imposing privacy against servers that do not store the retrieved message. This relaxation improves communication efficiency and yields capacity gains over standard PIR, while several graph and multigraph cases remain unresolved.
- Privacy formulation: Local privacy hides retrieval from a server if and only if that server stores the retrieved message, avoiding the broader privacy requirement of classical graph-replicated PIR.The paper presents this storage-dependent definition as a compromise between full replication costs and the conservative privacy requirement of standard graph-based PIR.
- Capacity improvements: The relaxation of privacy improves PIR communication efficiency and produces more encouraging results than the original graph-replicated PIR treatment.
- Capacity improvements: As the number of servers N increases, local PIR capacity decays more slowly than standard PIR capacity.
- Capacity improvements: For simple graphs, the proposed capacity lower bounds are at least O(N) times superior to standard PIR rates, while cyclic and path graphs achieve O(N) times capacity improvement.
- Multigraphs: For multigraphs, the achieved rates equal the corresponding simple-graph rates multiplied by (2 −21−r)−1.
- Open problems: Exact or approximate capacities remain to be characterized for graphs beyond star, cyclic, and path graphs, and capacity bounds remain open for most multigraphs.