pith. sign in

arxiv: 1906.11278 · v1 · pith:PAW2YGKKnew · submitted 2019-06-26 · 💻 cs.IT · math.IT

Private Information Retrieval with Private Coded Side Information: The Multi-Server Case

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

Pith reviewed 2026-05-25 14:54 UTC · model grok-4.3

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

The pith

In multi-server PIR with private coded side information the capacity equals the inverse of a partial geometric series in N when the demand is excluded from the side information.

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

The paper studies private retrieval of one message from N replicated servers when a user holds a random linear combination of M messages as side information whose indices and coefficients must also stay hidden. Servers are told only the integer M in advance. For the setting in which the demanded message lies outside the side-information combination the authors prove that the maximum download rate is exactly the reciprocal of the sum 1 + 1/N + … + 1/N to the power K-M-1. For the setting in which the demand participates in the side-information combination they establish a matching lower bound given by the reciprocal of the longer sum up to 1/N to the power K-M. The proofs combine linear coding ideas from the authors' earlier single-server work with query constructions previously used for multi-server private computation.

Core claim

For the multi-server PIR-PCSI problem in which servers know only M, the capacity equals (1 + 1/N + … + 1/N^{K-M-1})^{-1} when the demanded message is excluded from the user's linear-combination side information, and is lower-bounded by (1 + 1/N + … + 1/N^{K-M})^{-1} when the demand contributes to that combination.

What carries the argument

Linear-combination side information together with query strategies that hide both demand index and side-information support by leveraging single-server PIR-PCSI coding and multi-server private-computation techniques.

If this is right

  • The achievable rate increases as the number of servers N grows.
  • Increasing M reduces the number of unknown messages and therefore raises the capacity.
  • The same schemes simultaneously protect the identities of the M messages inside the side information.
  • The constructions remain valid when messages are independent and uniform over the finite field.

Where Pith is reading between the lines

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

  • The same capacity expressions may serve as outer bounds for variants that allow non-linear side information.
  • The two settings suggest a natural trade-off between the amount of side information and the privacy cost when the demand is allowed to participate in that information.
  • The multi-server gain over the single-server case can be quantified directly from the differing exponents in the geometric sums.

Load-bearing premise

The side information is a uniformly random linear combination over a finite field whose support size M is known to the servers but whose indices and coefficients are unknown to them.

What would settle it

An explicit scheme that achieves a download rate strictly larger than (1 + 1/N + … + 1/N^{K-M-1})^{-1} for finite K, M, N when the demand lies outside the side information would falsify the capacity claim.

read the original abstract

In this paper, we consider the multi-server setting of Private Information Retrieval with Private Coded Side Information (PIR-PCSI) problem. In this problem, there is a database of $K$ messages whose copies are replicated across $N$ servers, and there is a user who knows a random linear combination of a random subset of $M$ messages in the database as side information. The user wishes to download one message from the servers, while protecting the identities of both the demand message and the messages forming the side information. We assume that the servers know the number of messages forming the user's side information in advance, whereas the indices of these messages and their coefficients in the side information are not known to any of the servers a priori. Our goal is to characterize (or derive a lower bound on) the capacity, i.e., the maximum achievable download rate, for the following two settings. In the first setting, the set of messages forming the linear combination available to the user as side information, does not include the user's demanded message. For this setting, we show that the capacity is equal to $\left(1+{1}/{N}+\dots+{1}/{N^{K-M-1}}\right)^{-1}$. In the second setting, the demand message contributes to the linear combination available to the user as side information, i.e., the demand message is one of the messages that form the user's side information. For this setting, we show that the capacity is lower-bounded by $\left(1+{1}/{N}+\dots+{1}/{N^{K-M}}\right)^{-1}$. The proposed achievability schemes and proof techniques leverage ideas from both our recent methods proposed for the single-server PIR-PCSI problem as well as the techniques proposed by Sun and Jafar for multi-server private computation problem.

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 / 3 minor

Summary. The paper studies the multi-server Private Information Retrieval with Private Coded Side Information (PIR-PCSI) problem with N servers holding K messages. The user possesses a uniformly random linear combination of M messages as side information; servers know only the integer M. For the case where the demanded message is not among those forming the side information, the paper claims the exact capacity equals (1 + 1/N + … + 1/N^{K-M-1})^{-1}. For the case where the demand message contributes to the side information, it claims a lower bound of (1 + 1/N + … + 1/N^{K-M})^{-1}. Achievability and converse arguments combine techniques from the authors' prior single-server PIR-PCSI work with Sun-Jafar private computation methods.

Significance. If the stated capacity expressions hold, the work provides the first exact capacity result for a multi-server PIR-PCSI variant in the non-overlapping side-information case and a matching-style lower bound when overlap occurs. This extends the single-server PIR-PCSI results and Sun-Jafar private computation framework to a new setting with clearly articulated model assumptions (servers know only M; side information is a uniform random linear combination over a finite field). The explicit use of prior techniques for both achievability and converse is a strength that supports reproducibility of the rate derivations.

minor comments (3)
  1. [Abstract] Abstract: the capacity expressions employ ellipsis notation (1 + 1/N + … + 1/N^{K-M-1}); replace with explicit summation form such as (∑_{i=0}^{K-M-1} N^{-i})^{-1} for precision and to avoid ambiguity in the exponent range.
  2. The abstract states that the second setting yields only a lower bound while the first yields equality; the introduction or Section II should explicitly motivate why a matching converse is not obtained in the overlapping case, citing the specific technical obstacle (e.g., the linear dependence introduced by the demand message).
  3. Notation: the symbols K, M, N are introduced in the abstract but their roles (total messages, side-information size, number of servers) should be restated at the beginning of the problem formulation section for readers who skip the abstract.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful summary of our work, the positive assessment of its significance, and the recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper derives the stated capacity (exact for non-overlapping SI) and lower bound (for overlapping SI) via explicit achievability constructions that combine new multi-server schemes with prior single-server PIR-PCSI methods and Sun-Jafar private computation techniques. These are presented as independent derivations under explicitly stated problem assumptions (servers know only M; SI is uniform random linear combination; messages independent and uniform), with no reduction of the target expressions to fitted parameters, self-definitions, or load-bearing self-citations. The single-server citation supplies reusable ideas but does not substitute for the multi-server analysis or force the capacity formulas by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard information-theoretic modeling assumptions for messages, side information, and server knowledge; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption Messages are independent and uniformly distributed over a finite field; side information is a random linear combination of M messages.
    Standard modeling choice in PIR literature invoked to define the problem setting.
  • domain assumption Servers know only the integer M but not the indices or coefficients of the side-information messages.
    Explicitly stated in the abstract as part of the problem definition.

pith-pipeline@v0.9.0 · 5884 in / 1299 out tokens · 25442 ms · 2026-05-25T14:54:01.662614+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

19 extracted references · 19 canonical work pages · 4 internal anchors

  1. [1]

    Pri vate information retrieval,

    B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, “Pri vate information retrieval,” in Proc. IEEE 36th Annual F oundations of Computer Science , 1995, pp. 41–50

    work page 1995

  2. [2]

    The capacity of private informati on retrieval,

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

    work page 2017

  3. [3]

    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 Transactions on Information Theory, vol. 64, no. 3, pp. 1945–1956, March 2018. 10

    work page 1945

  4. [4]

    The capacity of robust private inf ormation retrieval with colluding databases,

    H. Sun and S. A. Jafar, “The capacity of robust private inf ormation retrieval with colluding databases,” IEEE Transactions on Information Theory , vol. 64, no. 4, pp. 2361–2370, April 2018

    work page 2018

  5. [5]

    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 2017 55th Annual Allerton Conference on Communication, Con trol, and Computing , Oct 2017, pp. 1099–1106

    work page 2017

  6. [6]

    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 2018 56th Annual Allerton Conference on Communication, Con trol, and Computing , Oct 2018, pp. 180–187

    work page 2018

  7. [7]

    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 2018 56th Annual Allerton Conference on Communication, Control, and Computing , Oct 2018, pp. 173–179

    work page 2018

  8. [8]

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

    Z. Chen, Z. Wang, and S. Jafar, “The capacity of private in formation retrieval with private side information,” Sep 20 17. [Online]. Available: http://arxiv.org/abs/1709.03022

    work page internal anchor Pith review Pith/arXiv arXiv

  9. [9]

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

    S. Li and M. Gastpar, “Converse for symmetric multi-serv er single-message pir with side information,” Jun 2019. [On line]. Available: http://arxiv.org/abs/1809.09861

    work page arXiv 2019

  10. [10]

    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 2018 IEEE Information Theory W orkshop (ITW) , Nov 2018, pp. 1–5

    work page 2018

  11. [11]

    Capacity of single-server single-message private information retr ieval with coded side information,

    A. Heidarzadeh, F. Kazemi, and A. Sprintson, “Capacity of single-server single-message private information retr ieval with coded side information,” in 2018 IEEE Information Theory W orkshop (ITW) , Nov 2018, pp. 1–5

    work page 2018

  12. [12]

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

    ——, “Capacity of single-server single-message privat e information retrieval with private coded side informatio n,” Jan 2019. [Online]. Available: http://arxiv.org/abs/1901.09248

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  13. [13]

    Multi-server private information retrieval with coded si de information,

    F. Kazemi, E. Karimi, A. Heidarzadeh, and A. Sprintson, “Multi-server private information retrieval with coded si de information,” Jun 2019. [Online]. Available: http://arxiv.org/abs/190 6.09259

    work page 2019

  14. [14]

    The capacity of cache aided private informa tion retrieval,

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

    work page 2017

  15. [15]

    Cache-aided priv ate information retrieval with partially known uncoded pre fetching: Fundamental limits,

    Y .-P . Wei, K. Banawan, and S. Ulukus, “Cache-aided priv ate information retrieval with partially known uncoded pre fetching: Fundamental limits,” IEEE Journal on Selected Areas in Communications , vol. 36, no. 6, pp. 1126–1139, Jun 2018

    work page 2018

  16. [16]

    Fundamental limits of cache-aided private inform ation retrieval with unknown and uncoded prefetching,

    ——, “Fundamental limits of cache-aided private inform ation retrieval with unknown and uncoded prefetching,” IEEE Transactions on Information Theory , Nov 2018

    work page 2018

  17. [17]

    Single-Server Multi-Message Individually-Private Information Retrieval with Side Information

    A. Heidarzadeh, S. Kadhe, S. E. Rouayheb, and A. Sprints on, “Single-server multi-message individually-private i nformation retrieval with side information,” Feb 2019. [Online]. Available: htt p://arxiv.org/abs/1901.07509

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  18. [18]

    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,” Jan 2019. [Online]. Available: http:// arxiv.org/abs/1901.07748

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  19. [19]

    The capacity of private computat ion,

    H. Sun and S. A. Jafar, “The capacity of private computat ion,” IEEE Transactions on Information Theory , vol. 65, no. 6, pp. 3880–3897, Jun 2019. 11

    work page 2019