pith. sign in

arxiv: 1907.00598 · v1 · pith:DXQZOYOUnew · submitted 2019-07-01 · 💻 cs.IT · cs.CR· math.IT

On an Equivalence Between Single-Server PIR with Side Information and Locally Recoverable Codes

Swanand Kadhe , Anoosheh Heidarzadeh , Alex Sprintson , O. Ozan Koyluoglu This is my paper

Pith reviewed 2026-05-25 11:46 UTC · model grok-4.3

classification 💻 cs.IT cs.CRmath.IT
keywords private information retrievallocally recoverable codesside informationcooperative locally recoverable codesdownload rateequivalencelinear codesnonlinear codes
0
0 comments X

The pith

Single-server PIR with side information equates to locally recoverable codes.

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

The paper establishes that coding schemes for single-server private information retrieval with side information, when used to retrieve one message, are equivalent to classical locally recoverable codes. Schemes for retrieving multiple messages equate instead to cooperative locally recoverable codes. These mappings transfer known results in both directions: they recover upper bounds on the download rate achievable by PIR-SI schemes and produce a new upper bound on the rate of cooperative LRCs. The equivalences are shown to hold for both linear and nonlinear codes.

Core claim

PIR schemes designed for retrieving a single message are equivalent to classical LRCs, and PIR schemes for retrieving multiple messages are equivalent to cooperative LRCs. These equivalence results allow recovering upper bounds on the download rate for PIR-SI schemes, and obtaining a novel rate upper bound on cooperative LRCs, for both linear and non-linear codes.

What carries the argument

The direct, lossless mapping between coding schemes of single-server PIR with side information and those of classical or cooperative locally recoverable codes.

If this is right

  • Known upper bounds on LRC rates immediately give upper bounds on the download rate of single-message and multi-message PIR-SI schemes.
  • The PIR equivalence produces a new upper bound on the achievable rate of cooperative LRCs.
  • All of the above equivalences and bounds apply equally to linear and nonlinear codes.

Where Pith is reading between the lines

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

  • The mapping may allow existing LRC constructions to be repurposed directly as PIR-SI schemes.
  • Similar one-to-one correspondences could link other PIR variants to additional local-recovery properties.
  • Rate bounds obtained this way may extend to related settings such as private distributed storage or index coding.

Load-bearing premise

The standard single-server PIR-SI model and the standard definitions of classical and cooperative LRCs admit a direct, lossless mapping between their coding schemes.

What would settle it

A single-message PIR-SI scheme whose download rate strictly exceeds the corresponding LRC rate bound, or a cooperative LRC whose rate exceeds the new upper bound obtained from the PIR equivalence.

read the original abstract

Private Information Retrieval (PIR) problem has recently attracted a significant interest in the information-theory community. In this problem, a user wants to privately download one or more messages belonging to a database with copies stored on a single or multiple remote servers. In the single server scenario, the user must have prior side information, i.e., a subset of messages unknown to the server, to be able to privately retrieve the required messages in an efficient way. In the last decade, there has also been a significant interest in Locally Recoverable Codes (LRC), a class of storage codes in which each symbol can be recovered from a limited number of other symbols. More recently, there is an interest in 'cooperative' locally recoverable codes, i.e., codes in which multiple symbols can be recovered from a small set of other code symbols. In this paper, we establish a relationship between coding schemes for the single-server PIR problem and LRCs. In particular, we show the following results: (i) PIR schemes designed for retrieving a single message are equivalent to classical LRCs; and (ii) PIR schemes for retrieving multiple messages are equivalent to cooperative LRCs. These equivalence results allow us to recover upper bounds on the download rate for PIR-SI schemes, and to obtain a novel rate upper bound on cooperative LRCs. We show results for both linear and non-linear codes.

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 manuscript claims that single-server PIR schemes with side information for retrieving one message are equivalent to classical locally recoverable codes (LRCs), while schemes for retrieving multiple messages are equivalent to cooperative LRCs. These equivalences are asserted to hold for both linear and nonlinear codes via explicit mappings between the respective schemes, allowing transfer of upper bounds on download rate in both directions and yielding a novel rate upper bound for cooperative LRCs.

Significance. If the claimed bijective correspondences between valid PIR-SI query schemes and local recovery functions are rigorously established without loss of rate or privacy/locality properties, the work supplies a concrete bridge between PIR and coding theory. This enables bound transfer (including a new upper bound on cooperative LRC rate) and unifies results across linear and nonlinear settings, which is a substantive contribution when the mappings are shown to be lossless.

minor comments (3)
  1. §1 (Introduction): the statement that the mappings are 'equivalence results' should be accompanied by an explicit forward reference to the sections containing the constructions and the proof that they preserve both the PIR privacy condition and the LRC locality condition exactly.
  2. The rate definitions (download rate for PIR-SI versus code rate for LRCs) are used interchangeably after the equivalence is stated; a short table or paragraph clarifying the exact correspondence between the two rate expressions would improve readability.
  3. Notation for the side-information set size and the number of messages to retrieve is introduced without a consolidated parameter table; adding one early in the paper would help readers track the parameter regimes under which the bounds apply.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading and positive evaluation of the manuscript, including the recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central contribution is an explicit equivalence via bijective mappings between single-server PIR-SI query schemes (single- and multi-message) and the local recovery functions of classical/cooperative LRCs. These mappings are constructed directly from the definitions of the two problems and transfer rate bounds in both directions without loss. No step reduces a claimed result to a fitted parameter, self-citation chain, or definitional tautology; the derivations remain self-contained against the standard models of both PIR-SI and LRCs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based solely on the abstract, the paper relies on standard domain assumptions in information theory and coding theory. No free parameters, invented entities, or ad-hoc axioms are mentioned.

axioms (2)
  • domain assumption Standard single-server PIR model with side information unknown to the server
    The equivalence is built on this model.
  • domain assumption Standard definitions of classical LRCs and cooperative LRCs in coding theory
    Equivalence and bound transfer rest on these definitions.

pith-pipeline@v0.9.0 · 5804 in / 1157 out tokens · 45508 ms · 2026-05-25T11:46:13.911734+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

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

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

20 extracted references · 20 canonical work pages · 5 internal anchors

  1. [1]

    Pri vate informa- tion retrieval,

    B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan, “Pri vate informa- tion retrieval,” Journal of the ACM , vol. 45, no. 6, pp. 965–981, 1998

    work page 1998

  2. [2]

    Private information retrieval,

    S. Y ekhanin, “Private information retrieval,” Communications of the ACM, vol. 53, no. 4, pp. 68–73, 2010

    work page 2010

  3. [3]

    The Capacity of Private Information Retrieval

    H. Sun and S. A. Jafar, “The capacity of private informati on retrieval,” CoRR, vol. abs/1602.09134, 2016. [Online]. Available: http://arxiv.org/abs/1602.09134

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  4. [4]

    The capacity of robust private information retriev al with collud- ing databases,

    ——, “The capacity of robust private information retriev al with collud- ing databases,” IEEE Trans. on Info. Theory , vol. 64, no. 4, pp. 2361– 2370, April 2018

    work page 2018

  5. [5]

    Robust private informa tion retrieval on coded data,

    R. Tajeddine and S. El Rouayheb, “Robust private informa tion retrieval on coded data,” in 2017 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2017

    work page 2017

  6. [6]

    Multi-Message Private Information Retrieval: Capacity Results and Near-Optimal Schemes

    K. Banawan and S. Ulukus, “Multi-message private infor- mation retrieval: Capacity results and near-optimal schem es,” CoRR, vol. abs/1702.01739, 2017. [Online]. Available: http://arxiv.org/abs/1702.01739

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  7. [7]

    The capacity of private information retrieval from coded databases,

    ——, “The capacity of private information retrieval from coded databases,” IEEE Trans. on Info. Theory , vol. 64, no. 3, pp. 1945–1956, March 2018

    work page 1945

  8. [8]

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

    S. Kadhe, B. Garcia, A. Heidarzadeh, S. E. Rouayheb, and A . Sprintson, “Private information retrieval with side information: The single server case,” in 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton) , Oct 2017, pp. 1099–1106

    work page 2017

  9. [9]

    Private Information Retrieval with Side Information

    ——, “Private information retrieval with side informa- tion,” CoRR, vol. abs/1709.00112, 2017. [Online]. Available: http://arxiv.org/abs/1709.00112

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  10. [10]

    On the capacity of single-server multi-message private in formation retrieval with side information,

    A. Heidarzadeh, B. Garcia, S. Kadhe, S. E. Rouayheb, and A. Sprintson, “On the capacity of single-server multi-message private in formation retrieval with side information,” in 2018 56th Annual Allerton Conf. on Commun., Control, and Computing , Oct 2018

    work page 2018

  11. [11]

    Single-server multi-message pri vate information retrieval with side information,

    S. Li and M. Gastpar, “Single-server multi-message pri vate information retrieval with side information,” in 2018 56th Annual Allerton Conf. on Commun., Control, and Computing , Oct 2018

    work page 2018

  12. [12]

    Locally decodable codes,

    S. Y ekhanin, “Locally decodable codes,” in Computer Science–Theory and Applications . Springer, 2011, pp. 289–290

    work page 2011

  13. [13]

    On th e locality of codeword symbols,

    P . Gopalan, C. Huang, H. Simitci, and S. Y ekhanin, “On th e locality of codeword symbols,” Information Theory, IEEE Transactions on , vol. 58, no. 11, pp. 6925–6934, Nov 2012

    work page 2012

  14. [14]

    On coopera tive local repair in distributed storage,

    A. S. Rawat, A. Mazumdar, and S. Vishwanath, “On coopera tive local repair in distributed storage,” in 2014 48th Annual Conference on Information Sciences and Systems (CISS) , March 2014, pp. 1–5

    work page 2014

  15. [15]

    Cooperative local repair in distributed storage,

    ——, “Cooperative local repair in distributed storage, ” Journal on Advances in Signal Processing , vol. 2015, no. 1, p. 107, Dec 2015

    work page 2015

  16. [16]

    On the Capacity of Single-Server Multi-Message Private Information Retrieval with Side Information

    A. Heidarzadeh, B. Garcia, S. Kadhe, S. E. Rouayheb, and A. Sprintson, “On the capacity of single-server multi-message private in formation retrieval with side information,” CoRR, vol. abs/1807.09908, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  17. [17]

    Bounds on the size of loca lly recoverable codes,

    V . R. Cadambe and A. Mazumdar, “Bounds on the size of loca lly recoverable codes,” IEEE Transactions on Information Theory , vol. 61, no. 11, pp. 5787–5794, Nov 2015

    work page 2015

  18. [18]

    A family of optimal locally recover able codes,

    I. Tamo and A. Barg, “A family of optimal locally recover able codes,” Information Theory, IEEE Transactions on , vol. 60, no. 8, pp. 4661– 4676, Aug 2014

    work page 2014

  19. [19]

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

    S. Li and M. Gastpar, “Single-server multi-message pri vate information retrieval with side information,” CoRR, vol. abs/1808.05797, 2018. [Online]. Available: http://arxiv.org/abs/1808.05797

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  20. [20]

    Storage capacity of repairable networks ,

    A. Mazumdar, “Storage capacity of repairable networks ,” IEEE Trans. on Info. Theory , vol. 61, no. 11, pp. 5810–5821, Nov 2015

    work page 2015