arxiv: 2605.10872 · v1 · submitted 2026-05-11 · 💻 cs.IT · cs.CR· cs.NI· eess.SP· math.IT

Recognition: 2 theorem links

· Lean Theorem

Local Private Information Retrieval: A New Privacy Perspective for Graph-Based Replicated Systems

Shreya Meel , Mohamed Nomeir , Sennur Ulukus

Authors on Pith no claims yet

Pith reviewed 2026-05-12 03:52 UTC · model grok-4.3

classification 💻 cs.IT cs.CRcs.NIeess.SPmath.IT

keywords local PIRgraph replicationprivate information retrievalcapacitydisjoint unioncyclic graphpath graphedge-transitive graphs

0 comments

The pith

Redefining privacy to hide queries only from servers that store the message raises PIR capacity in graph-replicated systems.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper rethinks privacy in multi-server PIR systems where messages are stored according to a known graph. Under the new local user privacy rule, a user must conceal the desired message index only from the servers that actually hold it, not from every server in the system. This relaxation produces higher communication efficiency, measured by the local PIR capacity as the number of message symbols retrieved per downloaded symbol. For graphs that are disjoint unions of distinct smaller graphs, the capacity multiplies across the components, exceeding the rate obtained when the components are identical. The authors also supply new schemes that improve lower bounds for connected edge-transitive and bipartite graphs and derive exact capacities for cycle graphs and path graphs with an odd number of vertices.

Core claim

Local PIR capacity on a graph is the maximum retrieval rate under the constraint that privacy is enforced only at servers storing the desired index. For a disjoint union of distinct graphs, this capacity equals the product of the component capacities, a multiplicative gain over the identical-graph case. New achievable schemes give strictly higher lower bounds than the best known PIR capacities for edge-transitive and bipartite graphs. Exact capacity values are obtained for every cycle graph and every path graph with an odd number of vertices.

What carries the argument

Local user privacy, which requires that the user's query reveals nothing about the desired index to any server storing the corresponding message, as identified from the known graph replication structure.

If this is right

Local PIR capacity exceeds standard PIR capacity for many graph structures.
Multiplicative capacity gains arise when the graph is a disjoint union of distinct components.
Exact capacities are known for all cycle graphs and all odd-length path graphs.
Improved achievable rates hold for edge-transitive and bipartite graphs.
Communication efficiency improves in storage systems whose replication follows a graph model.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Heterogeneous replication across distinct graph components could become preferable to uniform replication for privacy-preserving queries.
The local-privacy lens may extend to other distributed-storage settings such as coded caching where topology is known.
Simulations on real network topologies could quantify the actual download savings under these rates.
Relaxing the known-graph assumption to partial or dynamic topology information would be a natural next step.

Load-bearing premise

The replication structure is known to the user as a fixed graph, so the user can determine exactly which servers store each message and enforce privacy only at those servers.

What would settle it

A scheme achieving a strictly higher rate than the derived local PIR capacity for the cycle graph, or a proof that the stated rate for the odd-vertex path graph is unachievable.

read the original abstract

We rethink the definition of privacy in multi-server, graph-replicated private information retrieval (PIR) systems, and introduce a novel setting where the user's privacy is governed by the servers' storage structure. In particular, while retrieving a message from a server, the user is concerned with hiding their desired message index from the server, only if the server stores the corresponding message. We coin this privacy requirement as local user privacy and the resulting PIR problem as local PIR on the graph. Our goal is to measure the gain in communication efficiency of local PIR, compared to that of canonical PIR, by establishing its capacity, i.e., the maximum number of message symbols retrieved, per downloaded symbol. To this end, we observe a remarkable gain in the local PIR capacity of graphs, that are disjoint union of distinct graphs, which is multiplicative, compared to the PIR capacity, when the individual graphs are identical. For connected graphs, we propose schemes to establish capacity lower bounds for edge-transitive and bipartite graphs, which are greater than the best-known PIR capacity bounds. Finally, we derive the exact local PIR capacity for the cyclic graph, and the path graph with an odd number of vertices.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper relaxes PIR privacy to only the storing servers on a known graph and gets multiplicative capacity gains on disjoint unions plus exact values for cycles and odd paths.

read the letter

The main thing here is a redefinition of user privacy that only needs to hold against servers actually holding the desired message. With that change they report a multiplicative capacity lift when the replication graph is a disjoint union of distinct smaller graphs, and they close the capacity exactly for cycle graphs and for path graphs with an odd number of vertices. That is the concrete advance worth noting first. The work also supplies schemes that improve on the best known standard-PIR lower bounds for edge-transitive and bipartite graphs. The model is cleanly stated and the structural observation about heterogeneous disjoint unions is a clean result that does not appear in earlier PIR literature. The exact characterizations for cycles and odd paths are the strongest part of the contribution because they match lower and upper bounds. The paper is therefore useful for anyone who already works on information-theoretic PIR with structured replication. A reader can extract the new rates and the schemes without much extra effort. The main soft spot is that the upper-bound arguments for the exact capacities still need to be checked line by line; the abstract states the results but the derivations are not visible here. A secondary point is that the model presupposes the graph is public and that the user can identify which servers store which messages; that assumption is reasonable inside the paper but may restrict how far the rates apply when storage locations are hidden or dynamic. The literature comparison is adequate for the claims made but could be tightened against the most recent graph-PIR papers. Overall the thinking is coherent and the results are specific enough that the paper deserves a serious referee. I would send it to review rather than desk-reject.

Referee Report

2 major / 2 minor

Summary. The paper introduces a new 'local user privacy' definition for graph-replicated multi-server PIR, requiring the user to hide only the desired message index from servers that actually store that message (rather than globally). It establishes the capacity of this local PIR problem, demonstrating a multiplicative capacity gain for disjoint unions of distinct graphs relative to the standard PIR capacity on identical component graphs, provides achievable schemes yielding improved lower bounds for edge-transitive and bipartite graphs, and derives exact capacities for cycle graphs and odd-length path graphs.

Significance. If the capacity derivations hold, the work offers a principled relaxation of privacy that can yield strictly higher retrieval rates in replicated storage systems while still protecting against the relevant servers. The multiplicative gain for heterogeneous disjoint unions and the exact closed-form capacities for cycles and odd paths are concrete, falsifiable contributions that could guide practical system design. The graph-theoretic modeling and explicit comparison to canonical PIR capacity are strengths.

major comments (2)

[Abstract and §II] Abstract and §II (model): the local privacy definition presupposes that the user knows a priori which servers store the desired message in order to enforce privacy only locally; this knowledge assumption is load-bearing for all subsequent capacity claims and must be formalized (including how the user acquires it without violating privacy) or shown to be without loss of generality.
[Abstract and §IV] Abstract and §IV (disjoint unions): the claim of a 'remarkable' multiplicative gain relative to the PIR capacity on identical graphs requires an explicit side-by-side comparison of the two capacity expressions (including the baseline PIR capacity formula used); without this, it is impossible to verify the multiplicative factor or confirm it is not an artifact of the chosen normalization.

minor comments (2)

[Abstract] Abstract: replace the qualitative phrase 'remarkable gain' with a quantitative statement of the improvement factor once the exact expressions are derived.
[Throughout] Throughout: define or cite standard references for graph-theoretic terms (edge-transitive, bipartite, etc.) on first use to improve accessibility for the information-theory audience.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive feedback. We address each major comment below.

read point-by-point responses

Referee: [Abstract and §II] Abstract and §II (model): the local privacy definition presupposes that the user knows a priori which servers store the desired message in order to enforce privacy only locally; this knowledge assumption is load-bearing for all subsequent capacity claims and must be formalized (including how the user acquires it without violating privacy) or shown to be without loss of generality.

Authors: The replication graph is public knowledge in the system model, and the storage assignment for each message is deterministic given the graph and the message index. The user, who knows their desired index, can therefore compute exactly which servers store that message using only the public graph, without any private information or additional communication. This is consistent with standard models of replicated storage where placement is known a priori. We will add a formal clarification of this point in §II of the revised manuscript. revision: yes
Referee: [Abstract and §IV] Abstract and §IV (disjoint unions): the claim of a 'remarkable' multiplicative gain relative to the PIR capacity on identical graphs requires an explicit side-by-side comparison of the two capacity expressions (including the baseline PIR capacity formula used); without this, it is impossible to verify the multiplicative factor or confirm it is not an artifact of the chosen normalization.

Authors: We agree that an explicit comparison is needed for verification. In the revised version we will add, in §IV, a direct side-by-side display of the local PIR capacity expression for disjoint unions of distinct graphs against the standard PIR capacity on identical component graphs, using the canonical PIR capacity formula from the literature. This will make the multiplicative gain and the normalization explicit. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper introduces a new local privacy definition tied to the known graph replication structure, then derives concrete capacity lower bounds via explicit schemes for edge-transitive and bipartite graphs and exact capacities for cycles and odd-length paths. These results follow directly from the model without reducing to fitted parameters renamed as predictions, self-citation chains, or ansatzes imported from prior work by the same authors. The multiplicative gain for disjoint unions of distinct graphs is presented as an observation from the new definition rather than a tautology. No load-bearing step collapses to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim depends on the new definition of local privacy and standard assumptions from graph theory and information theory for capacity analysis. No free parameters are mentioned in the abstract.

axioms (1)

standard math Graph-theoretic properties such as edge-transitivity and bipartiteness are used to propose schemes and bounds.
Invoked for connected graphs to establish lower bounds.

invented entities (1)

Local user privacy no independent evidence
purpose: Redefines the privacy requirement to depend on whether the server stores the message.
This is a new concept introduced by the authors to model the graph-based replication.

pith-pipeline@v0.9.0 · 5523 in / 1321 out tokens · 161493 ms · 2026-05-12T03:52:06.461307+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We derive the exact local PIR capacity for the cyclic graph, and the path graph with an odd number of vertices.
IndisputableMonolith/Foundation/DimensionForcing.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

C(C_N)=1/2 ... C(P_N) = (N-1)/(2N-4) for odd N

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

[1]

B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan. Private information retrieval.Journal of the ACM, 45(6):965–981, November 1998

work page 1998
[2]

Sun and S

H. Sun and S. A. Jafar. The capacity of private information retrieval. IEEE Trans. Inf. Theory, 63(7):4075–4088, March 2017

work page 2017
[3]

Sun and S

H. Sun and S. A. Jafar. The capacity of symmetric private information retrieval.IEEE Trans. Inf. Theory, 65(1):322–329, June 2018

work page 2018
[4]

Wang and M

Q. Wang and M. Skoglund. Symmetric private information retrieval from MDS coded distributed storage with non-colluding and colluding servers.IEEE Trans. Inf. Theory, 65(8):5160–5175, March 2019

work page 2019
[5]

Wang and S

Z. Wang and S. Ulukus. Symmetric private information retrieval at the private information retrieval rate.IEEE J. Sel. Areas Inf. Theory, 3(2):350–361, October 2022

work page 2022
[6]

Sun and S

H. Sun and S. A. Jafar. The capacity of robust private information retrieval with colluding databases.IEEE Trans. Inf. Theory, 64(4):2361– 2370, April 2018

work page 2018
[7]

Wang and M

Q. Wang and M. Skoglund. On PIR and symmetric PIR from colluding databases with adversaries and eavesdroppers.IEEE Trans. Inf. Theory, 65(5):3183–3197, October 2019

work page 2019
[8]

Freij-Hollanti, O

R. Freij-Hollanti, O. W. Gnilke, C. Hollanti, and D. A. Karpuk. Private information retrieval from coded databases with colluding servers.SIAM J. Appl. Algebra and Geometry, 1(1):647–664, 2017

work page 2017
[9]

X. Yao, N. Liu, and W. Kang. The capacity of private information retrieval under arbitrary collusion patterns for replicated databases.IEEE Trans. Inf. Theory, 67(10):6841–6855, July 2021

work page 2021
[10]

Z. Jia, H. Sun, and S. A. Jafar. Cross subspace alignment and the asymptotic capacity ofX-secureT-private information retrieval.IEEE Trans. Inf. Theory, 65(9):5783–5798, May 2019

work page 2019
[11]

Nomeir, S

M. Nomeir, S. Vithana, and S. Ulukus. AsymmetricX-secureT-private information retrieval: More databases is not always better. InCISS, March 2024

work page 2024
[12]

Nomeir, A

M. Nomeir, A. Aytekin, and S. Ulukus. The capacity of semantic private information retrieval with colluding servers. InIEEE GLOBECOM, December 2025

work page 2025
[14]

Cheng, N

J. Cheng, N. Liu, W. Kang, and Y . Li. The capacity of symmetric private information retrieval under arbitrary collusion and eavesdropping patterns.IEEE Trans. Inf. Forensics Security, 17:3037–3050, August 2022

work page 2022
[15]

Q. Wang, H. Sun, and M. Skoglund. The capacity of private information retrieval with eavesdroppers.IEEE Trans. Inf. Theory, 65(5):3198–3214, December 2018

work page 2018
[16]

Banawan and S

K. Banawan and S. Ulukus. The capacity of private information retrieval from Byzantine and colluding databases.IEEE Trans. Inf. Theory, 65(2):1206–1219, September 2018

work page 2018
[17]

Nomeir, A

M. Nomeir, A. Aytekin, and S. Ulukus. The asymptotic capacity of Byzantine symmetric private information retrieval and its consequences. InIEEE ISIT, June 2025

work page 2025
[18]

Raviv, I

N. Raviv, I. Tamo, and E. Yaakobi. Private information retrieval in graph- based replication systems.IEEE Trans. Inf. Theory, 66(6):3590–3602, November 2019

work page 2019
[19]

Banawan and S

K. Banawan and S. Ulukus. Private information retrieval from non- replicated databases. InIEEE ISIT, July 2019

work page 2019
[20]

Sadeh, Y

B. Sadeh, Y . Gu, and I. Tamo. Bounds on the capacity of private information retrieval over graphs.IEEE Trans. Inf. Forensics Security, 18:261–273, November 2023

work page 2023
[21]

Yao and S

Y . Yao and S. A. Jafar. The capacity of 4-star-graph PIR. InIEEE ISIT, June 2023

work page 2023
[22]

X. Kong, S. Meel, T. J. Maranzatto, I. Tamo, and S. Ulukus. New capacity bounds for PIR on graph and multigraph-based replicated storage.IEEE Trans. Inf. Theory, 72(1):691–709, January 2026

work page 2026
[23]

Shanbhag and P

V . Shanbhag and P. Krishnan. Private information retrieval for graph- based replication with minimal subpacketization, 2026. Available online at arXiv:2601.09957

work page arXiv 2026
[24]

G. Ge, H. Wang, Z. Xu, and Y . Zhang. Private information retrieval over graphs, 2025. Available online at arXiv:2509.26512

work page arXiv 2025
[25]

S. Meel, X. Kong, T. J. Maranzatto, I. Tamo, and S. Ulukus. Private information retrieval on multigraph-based replicated storage. InIEEE ISIT, June 2025. APPENDIX A. Proof of Remark 2 The expression that we minimize is λ(ti, tj) d ti +t i −1 + (1−λ(t i, tj)) d tj +t j −1 , (53) where λ(ti, tj) = d−1 ti−1 d−1 ti−1 + d−1 tj −1 ∈(0,1).(54) Assume without los...

work page 2025