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

Recognition: 2 theorem links

· Lean Theorem

Private Information Retrieval With Arbitrary Privacy Requirements for Graph-Based Storage

Mohamed Nomeir , Shreya Meel , Sennur Ulukus

Authors on Pith no claims yet

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

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

keywords private information retrievalPIR capacitygraph storageprivacy requirementspath graphcycle graphneighborhood privacy

0 comments

The pith

Flexible privacy requirement sets allow exact capacity or tight bounds in graph-replicated PIR on path and cycle graphs.

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

The paper redefines privacy in the private information retrieval problem so that each server has its own arbitrary privacy requirement set consisting of any subset of message indices that includes the messages stored at that server. It applies this definition to storage arranged on path graphs and cyclic graphs, considering multiple privacy configurations including those based on a neighborhood range around each server. For these specific cases the work derives bounds on the retrieval capacity or determines the exact capacity value. A sympathetic reader would care because the neighborhood parameter creates a continuous transition between limited local privacy and full standard privacy, allowing storage systems to tune protection levels without requiring every message to be hidden from every server.

Core claim

In graph-replicated private information retrieval, privacy is reformulated through per-server privacy requirement sets that are arbitrary subsets of message indices provided they contain the stored messages; for path and cyclic storage graphs under neighborhood-range privacy sets, the retrieval capacity is either bounded or found exactly, with the neighborhood size controlling the shift from local to global privacy.

What carries the argument

Per-server privacy requirement sets, each an arbitrary subset of message indices guaranteed to contain the indices of messages stored at that server.

If this is right

Exact capacity expressions become available for path graphs when privacy sets follow a fixed neighborhood size.
Cyclic graphs admit similar capacity results under matching neighborhood privacy.
Increasing the neighborhood range monotonically increases the required download rate toward the standard PIR capacity.
Local PIR emerges as the special case when the neighborhood range is restricted to a single server.

Where Pith is reading between the lines

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

The same privacy-set formalism could be tested on tree or grid storage graphs to see whether capacity formulas generalize.
Systems with heterogeneous server trust levels could assign different neighborhood sizes per server without redesigning the storage layout.
Capacity expressions derived here might serve as outer bounds for PIR over arbitrary graphs once the neighborhood concept is relaxed.

Load-bearing premise

Privacy requirement sets for servers can be chosen independently as any subsets that contain the stored messages, with no further consistency constraints required across servers.

What would settle it

For a path graph with four servers and a neighborhood range of two, compute the actual retrieval capacity by exhaustive enumeration of all possible query strategies and check whether it matches the derived bound.

read the original abstract

We reformulate the definition of privacy in the private information retrieval (PIR) problem to accommodate flexible privacy requirements. We focus on graph-replicated PIR, with a generalized privacy requirement, instead of requiring all messages to be private from all servers, during retrieval. Towards this, we define a privacy requirement set for each server, which can be an arbitrary subset of all message indices, as long as the stored message indices are in their privacy requirement set. Since both the storage and privacy requirement sets have many possibilities, we focus on two specific storage settings, namely the path and cyclic graphs. We consider several privacy settings for each of them, which are not necessarily the same, to give different examples for privacy sets. Of particular interest are the privacy sets that comprise the indices of messages stored at servers within a neighborhood range. The neighborhood range parameter allows a transition from the recently introduced local PIR [1] to the standard graph-replicated PIR. In these cases, we derive bounds on the capacity or find the exact capacity.

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

The paper relaxes PIR privacy to arbitrary per-server subsets (with the stored messages inside) on graph storage and gives capacity bounds or exact values for neighborhood-range cases on paths and cycles.

read the letter

This paper relaxes the usual all-messages-private-from-all-servers rule in graph-replicated PIR. Instead each server gets its own privacy requirement set—an arbitrary collection of message indices that must contain the messages it actually stores. They then specialize to path and cycle graphs and focus on neighborhood-range sets, where the range parameter lets the scheme slide continuously from local PIR at one end to ordinary graph PIR at the other. For those concrete settings they derive capacity bounds or exact expressions. That parameterization and the per-server flexibility are the actual new pieces; the rest recovers the known extremes as special cases. The model is stated cleanly and the restriction to two simple graphs keeps the derivations manageable. The abstract claims the bounds are tight in the cases they treat, and the stress-test note finds no internal contradictions in the setup. The main limitation is scope: everything is worked out only for paths and cycles, so it is not yet clear how the same privacy sets behave on arbitrary graphs or whether the neighborhood idea extends without losing the clean capacity formulas. The proofs themselves are not visible in the abstract, so a referee will need to check whether the bounds are achieved by explicit schemes or rest on loose outer bounds. This is squarely for the small group already working on information-theoretic PIR with replicated storage. Someone in that niche can pull the neighborhood parameterization into their own models and test the capacity numbers against their constructions. It is too narrow to interest the wider coding or privacy community, but the incremental step is honest and the model is a natural one. I would send it to peer review; the contribution is well-defined and the technical claims are scoped tightly enough that referees can evaluate them directly.

Referee Report

0 major / 3 minor

Summary. The manuscript reformulates the privacy definition in private information retrieval (PIR) to accommodate arbitrary privacy requirement sets at each server (any subset containing the server's stored messages) within graph-replicated storage. It specializes to path and cyclic graphs, examines multiple privacy configurations with emphasis on neighborhood-range sets that interpolate between local PIR and standard graph-replicated PIR, and derives bounds or exact capacity expressions for these cases.

Significance. If the capacity derivations hold, the work meaningfully generalizes PIR privacy models beyond uniform all-messages-private requirements, providing a parameterized framework that bridges local and global privacy via the neighborhood-range construction. The explicit focus on path and cycle topologies yields concrete, falsifiable capacity results that extend prior graph-replicated PIR literature; the information-theoretic arguments and transition between special cases constitute a clear technical contribution.

minor comments (3)

[Abstract] Abstract: the phrase 'several privacy settings for each of them' is vague; a short enumeration of the specific neighborhood ranges and graph instances for which exact capacities versus bounds are obtained would improve readability without lengthening the abstract.
The transition from local PIR to standard graph-replicated PIR is described qualitatively; adding a brief sentence or small table in the introduction that maps neighborhood-range values to the corresponding privacy sets would make the interpolation explicit.
Ensure the reference to local PIR [1] appears in the bibliography with full bibliographic details.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary and recommendation of minor revision. The assessment correctly identifies the core contribution as a parameterized privacy model that interpolates between local PIR and standard graph-replicated PIR via neighborhood-range sets, together with concrete capacity results on path and cycle graphs.

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper reformulates the PIR privacy definition to allow arbitrary privacy requirement sets per server (any subset containing the stored messages) and restricts attention to path and cyclic graph storages with explicit neighborhood-range privacy parameterizations that interpolate between local PIR and standard graph-replicated PIR. Capacity bounds or exact values are derived for these concrete families. No equations reduce a claimed prediction or capacity expression to a fitted input or self-referential definition by construction; the neighborhood-range parameterization is introduced explicitly as a modeling choice rather than smuggled via self-citation. The single reference to prior local-PIR work is invoked only as a boundary case and does not bear the load of the new derivations. The overall argument is therefore self-contained against external information-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the new definition of per-server privacy requirement sets and the standard information-theoretic definition of capacity; no free parameters, invented entities, or non-standard axioms are introduced in the abstract.

axioms (1)

domain assumption Standard information-theoretic definition of PIR capacity as the supremum of achievable rates under the stated privacy constraints.
Invoked when the paper states it derives bounds or exact capacity.

pith-pipeline@v0.9.0 · 5488 in / 1121 out tokens · 46960 ms · 2026-05-12T03:43:18.908355+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 define a privacy requirement set for each server, which can be an arbitrary subset of all message indices, as long as the stored message indices are in their privacy requirement set... neighborhood range parameter allows a transition from the recently introduced local PIR to the standard graph-replicated PIR. In these cases, we derive bounds on the capacity or find the exact capacity.
IndisputableMonolith/Foundation/DimensionForcing.lean reality_from_one_distinction unclear

?

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

For the path graph... capacity is C = (N-1)/(2N-3). ... For the cyclic graph... C = 1/(h+2).

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

29 extracted references · 29 canonical work pages

[1]

S. Meel, M. Nomeir, and S. Ulukus. Local private information retrieval: A new privacy perspective for graph-based replicated systems. 2026. Available online at arXiv

work page 2026
[2]

Sun and S

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

work page 2017
[3]

Sun and S

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

work page 2018
[4]

Vithana, K

S. Vithana, K. Banawan, and S. Ulukus. Semantic private information retrieval.IEEE Trans. Info. Theory, 68(4):2635–2652, December 2021

work page 2021
[5]

Banawan and S

K. Banawan and S. Ulukus. The capacity of private information retrieval from coded databases.IEEE Trans. Info. Theory, 64(3):1945–1956, January 2018

work page 1945
[6]

Banawan and S

K. Banawan and S. Ulukus. Multi-message private information retrieval: Capacity results and near-optimal schemes.IEEE Trans. Info. Theory, 64(10):6842–6862, April 2018

work page 2018
[7]

Banawan and S

K. Banawan and S. Ulukus. Private information retrieval through wiretap channel II: Privacy meets security.IEEE Trans. Info. Theory, 66(7):4129–4149, February 2020

work page 2020
[8]

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
[9]

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
[10]

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
[11]

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
[12]

Banawan and S

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

work page 2019
[13]

Jia and S

Z. Jia and S. Jafar. On the asymptotic capacity ofX-SecureT-Private information retrieval with graph-based replicated storage.IEEE Trans. Inf. Theory, 66(10):6280–6296, July 2020

work page 2020
[14]

Yao and S

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

work page 2023
[15]

S. Meel, X. Kong, T. Maranzatto, I. Tamo, and S. Ulukus. Private information retrieval on multigraph-based replicated storage. InIEEE ISIT, June 2025

work page 2025
[16]

Meel and S

S. Meel and S. Ulukus. Effect of full common randomness replication in symmetric PIR on graph-based replicated systems. InIEEE ICC, May 2026

work page 2026
[17]

X. Kong, S. Meel, T. 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. APPENDIX A. Proof of Theorem 3 For better exposition, we explain the schemes with reference to the GPIR scheme on path graph given in [17]. First, we demonstrate the sch...

work page 2026
[18]

Download one symbol corresponding to the PIR scheme on path graph consisting ofN k and serverh+k+ 2, whenθ=k

Ifk∈[h+ 1], thenN k = [1 :h+k+ 1]. Download one symbol corresponding to the PIR scheme on path graph consisting ofN k and serverh+k+ 2, whenθ=k

work page
[19]

Download one symbol corresponding to the PIR scheme on path graph consisting ofN k, serverk−h−1and serverh+k+ 2, whenθ=k

Ifk∈[h+2 :N−h−2], thenN k = [k−h:h+k+1]. Download one symbol corresponding to the PIR scheme on path graph consisting ofN k, serverk−h−1and serverh+k+ 2, whenθ=k

work page
[20]

Download one symbol corresponding to the PIR scheme on path graph consisting ofN k and serverk−h−1, whenθ=k

Ifk∈[N−h−1 :N−1], thenN k = [k−h:N]. Download one symbol corresponding to the PIR scheme on path graph consisting ofN k and serverk−h−1, whenθ=k. LetM k =|N k|+ 1,c 1,k =h+k+ 2,c 2,k = 2h+ 4and c3,k =N−k+h+ 2, then, R= 2(N−1) Ph+1 k=1 Mk +PN−h−2 k=h+2 (Mk + 1) +PN−1 k=N−h−1 Mk (50) = 2(N−1) Ph+1 k=1 c1,k +PN−h−2 k=h+2 c2,k +PN−1 k=N−h−1 c3,k (51) = N−1 Ph...

work page
[21]

Download one symbol corresponding to the PIR scheme on path graph consisting ofN k and serverh+k+ 2, whenθ=k

Ifk∈[1 :N−h−2], thenN k = [1 :h+k+ 1]. Download one symbol corresponding to the PIR scheme on path graph consisting ofN k and serverh+k+ 2, whenθ=k

work page
[22]

Download one symbol corresponding to the PIR scheme on path graphP N , whenθ=k

Ifk∈[N−h−1 :h+ 1], thenN k = [N]. Download one symbol corresponding to the PIR scheme on path graphP N , whenθ=k

work page
[23]

Download one symbol corresponding to the PIR scheme on path graph consisting ofN k and serverk−h−1, whenθ=k

Ifk∈[h+2 :N−1], thenN k = [k−h:N]. Download one symbol corresponding to the PIR scheme on path graph consisting ofN k and serverk−h−1, whenθ=k. R= 2(N−1) PN−h−2 k=1 Mk +Ph+1 k=N−h−1 N+ PN−1 k=h+2 Mk (54) = 2(N−1) PN−h−2 k=1 c1,k +Ph+1 k=N−h−1 N+ PN−1 k=h+2 c3,k (55) = 2(N−1) 2PN−h−2 k=1 (h+k+ 2) + (2h+ 3−N)N (56) = 2(N−1) (h+ 2)(2N−h−3) .(57) The rate for...

work page
[24]

Download one symbol corresponding to the PIR scheme on path graph consisting ofN ′ k and serverh+k+ 2, whenθ=k

Ifk∈[h+ 2], thenN ′ k = [1 :h+k+ 1]. Download one symbol corresponding to the PIR scheme on path graph consisting ofN ′ k and serverh+k+ 2, whenθ=k

work page
[25]

Download one symbol corresponding to the PIR scheme on path graph consisting ofN ′ k, serverk−h−1and serverh+k+ 2, whenθ=k

Ifk∈[h+3 :N−h−3], thenN ′ k = [k−h:h+k+1]. Download one symbol corresponding to the PIR scheme on path graph consisting ofN ′ k, serverk−h−1and serverh+k+ 2, whenθ=k

work page
[26]

Download one symbol corresponding to the PIR scheme on path graph consisting ofN ′ k and serverk−h−1, whenθ=k

Ifk∈[N−h−2 :N−1], thenN ′ k = [k−h:N]. Download one symbol corresponding to the PIR scheme on path graph consisting ofN ′ k and serverk−h−1, whenθ=k. This gives the same rate as shown below, since, R= 2(N−1) 2Ph+1 k=1 M ′ k +PN−h−3 k=h+3 2M ′ k + 1 +PN−1 k=N−h−1 M ′ k (59) = 2(N−1) Ph+1 k=1 Mk +PN−h−2 k=h+2 Mk + 1 +PN−1 k=N−h−1 Mk (60) = 2(N−1) (h+ 2)(2N−...

work page
[27]

Download one symbol corresponding to the PIR scheme on path graph consisting ofN k and serverh+k+ 2, whenθ=k

Ifk∈[1 :N−h−3], thenN ′ k = [1 :h+k+ 1]. Download one symbol corresponding to the PIR scheme on path graph consisting ofN k and serverh+k+ 2, whenθ=k

work page
[28]

Download one symbol corresponding to the PIR scheme on path graphP N , whenθ=k

Ifk∈[N−h−2 :h+ 2], thenN ′ k = [N]. Download one symbol corresponding to the PIR scheme on path graphP N , whenθ=k

work page
[29]

Download one symbol corresponding to the PIR scheme on path graph consisting ofN k and serverk−h−1, whenθ=k

Ifk∈[h+3 :N−1], thenN ′ k = [k−h:N]. Download one symbol corresponding to the PIR scheme on path graph consisting ofN k and serverk−h−1, whenθ=k. R= 2(N−1) PN−h−3 k=1 M ′ k +Ph+2 k=N−h−2 N+ PN−1 k=h+3 M ′ k (62) = 2(N−1) PN−h−3 k=1 c1,k +Ph+2 k=N−h−2 N+ PN−1 k=h+3 c3,k (63) = 2(N−1) (h+ 2)(2N−h−3) .(64) B. Proof of Theorem 5 To find the lower bound, we pr...

work page