pith. sign in

arxiv: 1906.09259 · v1 · pith:4MJKV44Anew · submitted 2019-06-21 · 💻 cs.IT · math.IT

Multi-Server Private Information Retrieval with Coded Side Information

Fatemeh Kazemi , Esmaeil Karimi , Anoosheh Heidarzadeh , Alex Sprintson This is my paper

Pith reviewed 2026-05-25 18:20 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords private information retrievalcoded side informationmulti-servercapacityserver-symmetric schemeslinear combinationsprivacy
0
0 comments X

The pith

The server-symmetric capacity of multi-server private information retrieval with coded side information equals the inverse of a partial geometric series when side information is independent of the request, and equals 1 or N/(N+1) when it is

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

This paper determines the exact server-symmetric capacity of the multi-server PIR-CSI problem, in which a user retrieves one of K messages from N servers while holding a linear combination of M messages as side information. It separates the problem into the case where the side information is independent of the requested message and the case where it is a function of that message. The results supply closed-form expressions that apply for any valid M, K, and N. A reader would care because the expressions fix the best achievable download rate under the privacy constraint when symmetry across servers is imposed.

Core claim

When the side information is not a function of the user's requested message, the server-symmetric capacity is (1 + 1/N + … + 1/N^{⌈K/(M+1)⌉−1})^{-1} for any 1≤M≤K−1. When the side information is a function of the user's requested message, the capacity is 1 for M=2 and M=K, and N/(N+1) for any 3≤M≤K−1. The converses use new information-theoretic arguments; the schemes extend the single-server PIR-CSI construction and the Sun-Jafar multi-server PIR scheme.

What carries the argument

Server-symmetric PIR-CSI schemes, in which queries to and answers from every server have identical structure, whose rate is defined as the minimum download rate over all problem instances.

If this is right

  • Download cost is bounded below by the stated formula in the independent-side-information case.
  • Rate-1 retrieval is achievable when side information depends on the request and M equals 2 or K.
  • Rate N/(N+1) is the exact value for dependent side information when 3≤M≤K−1.
  • Both achievability and converse hold uniformly for every coefficient choice consistent with the dependence condition.

Where Pith is reading between the lines

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

  • Removing the server-symmetry restriction could raise the capacity above the reported values.
  • The dependence on ceil(K/(M+1)) suggests that increasing M yields stepwise rate gains until M reaches K.
  • The same linear-combination side-information model may apply directly to private retrieval in coded distributed storage.
  • Numerical verification for small K,N,M would confirm whether the formulas remain tight outside the symmetric class.

Load-bearing premise

All capacity statements are proved only inside the class of schemes that treat every server identically in query and answer structure.

What would settle it

For K=3, M=1, N=2, any explicit server-symmetric scheme whose minimum download rate exceeds 2/3, or any matching converse proof that the rate cannot reach 2/3, would refute the claimed capacity.

read the original abstract

In this paper, we study the multi-server setting of the \emph{Private Information Retrieval with Coded Side Information (PIR-CSI)} problem. In this problem, there are $K$ messages replicated across $N$ servers, and there is a user who wishes to download one message from the servers without revealing any information to any server about the identity of the requested message. The user has a side information which is a linear combination of a subset of $M$ messages in the database. The parameter $M$ is known to all servers in advance, whereas the indices and the coefficients of the messages in the user's side information are unknown to any server \emph{a priori}. We focus on a class of PIR-CSI schemes, referred to as \emph{server-symmetric schemes}, in which the queries/answers to/from different servers are symmetric in structure. We define the \emph{rate} of a PIR-CSI scheme as its minimum download rate among all problem instances, and define the \emph{server-symmetric capacity} of the PIR-CSI problem as the supremum of rates over all server-symmetric PIR-CSI schemes. Our main results are as follows: (i) when the side information is not a function of the user's requested message, the capacity is given by ${(1+{1}/{N}+\dots+{1}/{N^{\left\lceil \frac{K}{M+1}\right\rceil -1}})^{-1}}$ for any ${1\leq M\leq K-1}$; and (ii) when the side information is a function of the user's requested message, the capacity is equal to $1$ for $M=2$ and $M=K$, and it is equal to ${N}/{(N+1)}$ for any ${3 \leq M \leq K-1}$. The converse proofs rely on new information-theoretic arguments, and the achievability schemes are inspired by our recently proposed scheme for single-server PIR-CSI as well as the Sun-Jafar scheme for multi-server PIR.

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.

Referee Report

0 major / 1 minor

Summary. The paper studies the multi-server PIR-CSI problem with K messages across N servers and a user possessing a linear combination of M messages as side information (M known to servers but indices/coefficients unknown). It restricts attention to server-symmetric schemes (symmetric queries/answers across servers) and defines the server-symmetric capacity as the supremum rate over such schemes. The main results give closed-form expressions: when side information is not a function of the requested message the capacity is (1 + 1/N + … + 1/N^{⌈K/(M+1)⌉−1})^{-1} for 1 ≤ M ≤ K−1; when it is a function the capacity equals 1 for M=2 and M=K and N/(N+1) for 3 ≤ M ≤ K−1. Converse proofs use new information-theoretic arguments; achievability constructions are inspired by prior single-server PIR-CSI and Sun-Jafar multi-server PIR schemes.

Significance. If the derivations hold, the work supplies the first explicit characterization of server-symmetric capacity for multi-server PIR-CSI, extending single-server PIR-CSI results to the multi-server regime under symmetry. The closed-form expressions quantify the precise rate impact of coded side information and supply falsifiable predictions for the symmetric class; the new converse technique is a methodological contribution.

minor comments (1)
  1. The title does not mention the server-symmetric restriction that is central to all stated results; a clarifying subtitle or parenthetical would prevent scope misreading.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of our work, including the accurate summary of the server-symmetric capacity results for multi-server PIR-CSI. We appreciate the recommendation for minor revision.

Circularity Check

0 steps flagged

No circularity; results self-contained within explicitly restricted class

full rationale

The paper explicitly defines and restricts attention to server-symmetric schemes and the corresponding server-symmetric capacity (supremum over symmetric schemes only). Capacity expressions are derived via new information-theoretic converse arguments plus achievability constructions; neither reduces by construction to fitted inputs, self-definitions, or load-bearing self-citations. The mention of inspiration from the authors' prior single-server work is non-load-bearing for the central claims. The derivation chain is therefore independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review; the central results rest on the modeling choice to restrict attention to server-symmetric schemes and on standard information-theoretic definitions of capacity and rate.

axioms (1)
  • domain assumption Capacity is computed only over server-symmetric schemes
    Explicitly stated when defining server-symmetric capacity in the abstract.

pith-pipeline@v0.9.0 · 5921 in / 1319 out tokens · 31770 ms · 2026-05-25T18:20:19.139557+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages · 3 internal anchors

  1. [1]

    The capacity of private informati on retrieval,

    H. Sun and S. A. Jafar, “The capacity of private informati on retrieval,” IEEE Trans. on Info. Theory , vol. 63, no. 7, pp. 4075–4088, 2017

    work page 2017

  2. [2]

    The capacity of private inform ation retrieval from coded databases,

    K. Banawan and S. Ulukus, “The capacity of private inform ation retrieval from coded databases,” IEEE Trans. on Info. Theory , vol. 64, no. 3, pp. 1945–1956, 2018

    work page 1945

  3. [3]

    Private information retrieval with side info rmation: The single server case,

    S. Kadhe, B. Garcia, A. Heidarzadeh, S. El Rouayheb, and A . Sprintson, “Private information retrieval with side info rmation: The single server case,” in 55th Annual Allerton Conference on Commun., Control, and Co mputing (Allerton) , 2017, pp. 1099–1106

    work page 2017

  4. [4]

    On the capacity of single-server multi-messa ge private information retrieval with side information,

    A. Heidarzadeh, B. Garcia, S. Kadhe, S. El Rouayheb, and A . Sprintson, “On the capacity of single-server multi-messa ge private information retrieval with side information,” in Proc. 56th Annual Allerton Conference on Commun., Control, and Computing, Oct 2018, pp. 180–187

    work page 2018

  5. [5]

    Single-server multi-message priv ate information retrieval with side information,

    S. Li and M. Gastpar, “Single-server multi-message priv ate information retrieval with side information,” in 56th Annual Allerton Conference on Commun., Control, and Computing (Allerton) , 2018, pp. 173–179

    work page 2018

  6. [6]

    Capacity o f single-server single-message private information retri eval with coded side information,

    A. Heidarzadeh, F. Kazemi, and A. Sprintson, “Capacity o f single-server single-message private information retri eval with coded side information,” in Proc. IEEE Info. Theory W orkshop (ITW’18) , Nov 2018

    work page 2018

  7. [7]

    Capacity of Single-Server Single-Message Private Information Retrieval with Private Coded Side Information

    ——, “Capacity of single-server single-message private information retrieval with private coded side information ,” Jan 2019. [Online]. Available: arXiv:1901.09248

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  8. [8]

    The capacity of cache aided private informat ion retrieval,

    R. Tandon, “The capacity of cache aided private informat ion retrieval,” in 55th Annual Allerton Conference on Commun., Control, and Computing, Oct 2017, pp. 1078–1082

    work page 2017

  9. [9]

    Fundamental limit s of cache-aided private information retrieval with unknow n and uncoded prefetching,

    Y .-P . Wei, K. Banawan, and S. Ulukus, “Fundamental limit s of cache-aided private information retrieval with unknow n and uncoded prefetching,” IEEE Trans. on Info. Theory , 2018. 15

    work page 2018

  10. [10]

    Converse for multi-server single -message pir with side information,

    S. Li and M. Gastpar, “Converse for multi-server single -message pir with side information,” arXiv preprint arXiv:1809.09861 , 2018

    work page arXiv 2018

  11. [11]

    The Capacity of $T$-Private Information Retrieval with Private Side Information

    Z. Chen, Z. Wang, and S. Jafar, “The capacity of private i nformation retrieval with private side information,” arXiv preprint arXiv:1709.03022, 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  12. [12]

    Multi-message private information retrieval with pr ivate side information,

    S. P . Shariatpanahi, M. J. Siavoshani, and M. A. Maddah- Ali, “Multi-message private information retrieval with pr ivate side information,” in Proc. IEEE Info. Theory W orkshop (ITW) , Nov 2018

    work page 2018

  13. [13]

    Single-Server Single-Message Online Private Information Retrieval with Side Information

    F. Kazemi, E. Karimi, A. Heidarzadeh, and A. Sprintson, “Single-server single-message online private informatio n retrieval with side information,” arXiv preprint arXiv:1901.07748 , 2019. 16

    work page internal anchor Pith review Pith/arXiv arXiv 1901