Pith. sign in

REVIEW 4 major objections 4 minor 41 references

Improved Storage for Efficient Private Information Retrieval

T0 review · 4 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A hybrid storage scheme that combines MDS row coding with uncoded partial replication achieves a strictly better download-storage tradeoff for private information retrieval, adding O(N^2) achievable corner points.

desk verdict Genuinely new hybrid idea, but Theorem 1 overclaims: only one worked example is given, and the load-bearing 'without loss of generality' step is unsupported. read the letter →

arxiv 1908.11366 v1 pith:2ROORRA5 submitted 2019-08-29 cs.IT cs.CRcs.DBmath.IT

Karim Banawan , Batuhan Arasli , Sennur Ulukus This is my paper · ORCID
classification cs.ITcs.CRcs.DBmath.IT
keywords privateinformationretrievalstorage-constraineddatabasesMDScodinguncodedpartialreplicationdownloadcoststorage-downloadtradeoffhybridstorageschemeslowerconvexhull
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper studies private information retrieval (PIR) from N databases that each store only a fraction $\mu$ of the M-message library, and asks how little the user must download while keeping the desired message identity secret. It argues that a hybrid storage scheme—first coding each message row with a maximum-distance-separable (MDS) code, then placing row partitions into groups of t databases—achieves normalized download cost $1 + K/t + \dots + (K/t)^{M-1}$ at storage fraction $t/(KN)$ for every $t, K \in [N]$ with $t \ge K$, with memory sharing filling intermediate storage values. If correct, this beats both pure MDS-coded storage and pure uncoded partial replication at rational storage points, with on the order of $N^2$ achievable corner points instead of $N$. The result matters because the extra corner points sit on the benchmark curve $D = 1 + 1/(N\mu) + \dots + (1/(N\mu))^{M-1}$, so hybrid storage gets strictly closer to the fundamental limit at no extra storage.

What carries the argument

The load-bearing object is the pair $(t,K)$: an $(N,K)$ MDS row code fixes how many coded symbols are needed to reconstruct a row, and the t-subset row partition fixes which $t$ databases hold each row, giving storage fraction $t/(KN)$. The identity that carries the result is $D(t,K)=1+\frac{K}{t}+\cdots+\left(\frac{K}{t}\right)^{M-1}$, which is exactly the classical uncoded PIR download-cost expression with the effective number of databases replaced by $t/K$. The two-round query structure is the mechanism: round one decodes side-information rows from undesired messages, and round two folds them into desired-symbol downloads, so privacy is preserved by private row permutations while the needed download per database stays bounded.

What would settle it

Implement the natural generalization of the construction for a parameter triple outside the worked example, such as $N=7$, $M=3$, $t=6$, $K=3$ (so $\mu=2/7$ and the claimed download is $1+1/2+1/4=7/4$), and check whether the query table can be completed with every desired row appearing in $K$ databases and every database's queries equally likely under each message hypothesis. A single instance where the required side-information rows are unavailable, or where the query distributions for two messages differ, would falsify the claim that the example generalizes.

Watch

Extended reading notes

Core claim

The core discovery is an achievable storage-retrieval construction whose points lie on the curve $D(\mu)=1+\frac{1}{N\mu}+\cdots+\frac{1}{(N\mu)^{M-1}}$ at the rational storage values $\mu=\frac{t}{KN}$ with $t\ge K$. The storage phase codes each row of each message by an $(N,K)$ maximum-distance-separable (MDS) code and then applies the uncoded t-subset placement: the row indices are partitioned into $\binom{N}{t}$ groups, each group assigned to one set of $t$ databases, and database $n$ stores the coded symbols of every row whose assigned set contains $n$. The retrieval phase runs two rounds: the first downloads $K$ coded symbols of each row from $K$ databases that hold it, which is enough to decode rows by the MDS property; the second adds decoded undesired rows to desired symbols as side information, so each database's query distribution is identical for every message. The paper demonstrates the construction for $N=6, M=2, \mu=5/12$, achieving download $7/5$ against $17/12$ for both pure schemes, and argues that the same pattern generalizes without loss of generality to all parameters.

Load-bearing premise

The load-bearing premise is that the explicit row-partition and two-round query construction, shown only for $N=6$, $M=2$, $\mu=5/12$, extends without loss of generality to all $N$, $M$, $t$, $K$ with $t\ge K$; if that extension fails, Theorem 1's tradeoff points are not all achievable.

Editorial extensions

If this is right

  • At every corner point $(t,K)$, the scheme matches the benchmark curve $D=1+1/(N\mu)+\cdots+1/(N\mu)^{M-1}$, so hybrid storage reaches the same download cost as a hypothetical scheme that works at arbitrary storage ratio.
  • The achievable region has $O(N^2)$ corner points (all pairs $t\ge K$), compared with $O(N)$ for either pure ingredient; memory sharing between adjacent points gives the lower convex hull.
  • Setting $K=1$ recovers the uncoded partial-replication tradeoff, and setting $t=N$ recovers the MDS-coded tradeoff, so the hybrid scheme contains both prior schemes as special cases.
  • Whether the whole benchmark curve is achievable for all $\mu\in[1/N,1]$ remains open; Theorem 1 only shows the lower convex hull is achievable.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same hybrid idea could be tested against colluding or heterogeneous databases, since privacy is maintained by row permutations and side-information masking, not by the symmetry of identical databases.
  • If the construction generalizes, the set of achievable storage fractions $\{t/(KN): t\ge K\}$ becomes dense in $[1/N,1]$ as $N$ grows, suggesting the benchmark curve may itself be approachable; one could try to prove a matching converse for these rational points.
  • The two-round structure suggests an iterative PIR scheme: round two could itself generate deeper side information for a third round, potentially lowering download further at the same storage, along the lines of the classical recursive PIR construction.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper studies private information retrieval (PIR) from N storage-constrained databases, where each database can store a fraction mu of the entire M-message library. The authors propose a hybrid storage scheme that combines row-wise (N,K) MDS coding with uncoded partial replication in the style of Maddah-Ali-Niesen prefetching. The main result, Theorem 1, claims that for every t,K in [N] with t>=K, the storage-download point (mu = t/(KN), D(t,K) = 1 + K/t + ... + (K/t)^{M-1}) is achievable, and that the lower convex hull of these points upper-bounds the optimal normalized download cost D*(mu). The proof section, however, contains only one worked example with N=6, M=2, t=5, K=2, for which the query table is fully specified and the download cost 7/5 is verified. The paper asserts that this example is 'without loss of generality' and claims reductions to prior MDS-coded and uncoded-storage schemes as special cases.

Significance. If Theorem 1 were established, the contribution would be substantial: it unifies the two existing storage strategies, yields O(N^2) corner points via the Farey-sequence structure of t/(KN), and strictly improves the download cost at those points. The worked example is concrete, internally consistent, and machine-checkable from the query table. The reductions to the MDS-coded scheme [12] (t=N) and the uncoded scheme [26] (K=1) are correct sanity checks. However, the significance is entirely contingent on the general achievability proof, which is absent; the manuscript as written provides only a single data point and an unsupported extrapolation. The internal admission in Remark 3 that it is unclear whether the curve can be achieved for all mu further weakens the claim.

major comments (4)
  1. [Section V, first paragraph and Theorem 1] The proof of Theorem 1 consists solely of the N=6, M=2, t=5, K=2 example, with the sentence 'we illustrate our achievable scheme by an example without loss of generality.' No general construction is provided for arbitrary M (which would require an M-round scheme with recursively matched side-information counts), arbitrary t and K (which change the row-partition counts and the number of side-information equations available in each round), or arbitrary N. The combinatorial counts in the example (30 rows, 6 partitions of 5 rows, 12 undesired rows decoded in round 1, 6 side-information equations per database in round 2) are finely matched to the chosen parameters and do not visibly generalize. Since Theorem 1 is the central claim of the paper, this missing proof is a load-bearing omission.
  2. [Remark 3 and Section III] The paper itself states in Section III that 'It is unclear at this point if the entirety of this curve can be achieved by general schemes' and in Remark 3 that 'It is unclear if this curve can be achieved for all mu in [1/N,1].' These statements acknowledge that the general tradeoff is not settled. At minimum, the manuscript must clearly delimit what is proven (the example) from what is conjectured (the general curve), and Theorem 1 should not be stated as a theorem unless a complete proof for the claimed parameter range is supplied.
  3. [Section II and Theorem 1] The system model in Section II restricts storage functions to 'non-mixing MDS coding based [12] storage policies,' yet the abstract and Theorem 1 speak of 'the optimal tradeoff' D*(mu). The theorem only establishes an achievable download cost for a restricted class of storage policies; no converse is proven even for that restricted class, and the relationship to the unrestricted optimum is not addressed. This conflation of achievability with optimality should be corrected throughout, or the restricted setting should be stated explicitly in the theorem and abstract.
  4. [Section V, Subsection A.1] The example relies on a precise arithmetic alignment: the message length is 30 rows, the number of partitions is C(6,5)=6, each partition has 5 rows, and the round-2 side-information counts come out exactly. The paper does not state how to choose the message length L for general N, t, K, M so that the row count is divisible by C(N,t) and so that the side-information counts at every round match the claimed download cost D(t,K). Without such a specification, the domain of the construction is not even defined, let alone proven to achieve the points in Theorem 1.
minor comments (4)
  1. [Section V, first paragraph] The sentence 'The proof of Theorem 1 is given is Section V' contains a typo; it should read 'given in Section V.'
  2. [Table I] Table I does not visually distinguish round 1 queries from round 2 queries; marking the two rounds explicitly (for example with a horizontal rule or a column label) would substantially improve readability and verifiability.
  3. [Abstract and Introduction] The phrase 'characterize the optimal tradeoff curve' overstates the result, since the paper provides only an achievable bound for a restricted storage class; the wording should be softened to reflect the actual contribution.
  4. [Figure 2 caption and Remark 2] The connection between the O(N^2) corner points and Farey sequences is mentioned via reference [41] but never explained; a brief explanation of how the number of corner points scales with N^2 would help the reader parse Remark 2.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the new corner point is explicitly constructed and its download/storage counts follow directly from the protocol rather than from fitted inputs.

full rationale

The paper's central claim is an achievability upper bound: D*(mu) is no larger than the lower convex hull of the points (mu = t/(KN), D(t,K) = sum_{i=0}^{M-1} (K/t)^i). The new point in the representative example, (mu = 5/12, D = 7/5), is not obtained by fitting a parameter to the target formula. The storage ratio is computed directly from the explicit partition: each database stores coded symbols from 25 rows of each of 2 messages, so mu = (25*2)/(30*2) = 5/12. The download cost is computed by counting the explicit query table: 14 coded symbols per database, 6 databases, L = 60, so D = (14*6)/60 = 7/5 = 1 + K/t with K = 2, t = 5. Thus the claimed point is a counted consequence of a specific construction, not a renamed known result. The reductions to the prior uncoded scheme [26] when K = 1 and to the MDS-coded scheme [12] when t = N are sanity checks, not inputs to the new intermediate points; the new points are achieved by a genuinely hybrid storage and retrieval protocol. The paper does invoke the authors' own prior work [12] for MDS-coded storage, but the load-bearing mathematical fact in the example is the standard MDS property and the explicit query table, not [12]'s capacity theorem, so this self-citation is not load-bearing. The main weakness is not circularity but proof completeness: Section V states 'we illustrate our achievable scheme by an example without loss of generality,' yet no general construction or privacy proof is supplied for arbitrary N, M, t, K, and Remark 3 concedes 'It is unclear if this curve can be achieved for all mu'. That is an omitted proof / correctness risk, not a circular derivation. Therefore the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard MDS existence, a domain assumption about the PIR setting, and an unproven assertion that the example construction generalizes. No ad hoc constants or invented physical entities appear.

assumptions (4)
  • standard math Existence of (N,K) MDS codes over sufficiently large finite fields.
    Used in Section V to map each K-length row to N coded symbols; valid for q >= N.
  • domain assumption The user's private row permutations within each message partition are sufficient to guarantee privacy for any M, t, K.
    The privacy argument in Section V is illustrated only for M=2 and a single parameter pair; the paper assumes the same argument scales without proof.
  • domain assumption Non-colluding databases and no side information.
    System model in Section II assumes each database is queried independently and the user has no prior information about the messages.
  • ad hoc to paper Storage functions are restricted to non-mixing MDS coding based policies.
    The paper explicitly constrains itself to this class in Section II and does not claim optimality outside it.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved Storage for Efficient Private Information Retrieval." pith.science (2026). https://pith.science/paper/2ROORRA5

@misc{pith2026190811366,
  author       = {Pith},
  title        = {Pith review of: Improved Storage for Efficient Private Information Retrieval},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2ROORRA5}},
  note         = {Machine review of arXiv:1908.11366}
}
abstract

We consider the problem of private information retrieval from $N$ \emph{storage-constrained} databases. In this problem, a user wishes to retrieve a single message out of $M$ messages (of size $L$) without revealing any information about the identity of the message to individual databases. Each database stores $\mu ML$ symbols, i.e., a $\mu$ fraction of the entire library, where $\frac{1}{N} \leq \mu \leq 1$. Our goal is to characterize the optimal tradeoff curve for the storage cost (captured by $\mu$) and the normalized download cost ($D/L$). We show that the download cost can be reduced by employing a hybrid storage scheme that combines \emph{MDS coding} ideas with \emph{uncoded partial replication} ideas. When there is no coding, our scheme reduces to Attia-Kumar-Tandon storage scheme, which was initially introduced by Maddah-Ali-Niesen in the context of the caching problem, and when there is no uncoded partial replication, our scheme reduces to Banawan-Ulukus storage scheme; in general, our scheme outperforms both.

Figures

Figures reproduced from arXiv: 1908.11366 by the authors.

Figure 1
Figure 1. System model: A data center stores the message set in [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Optimal tradeoff for uncoded storage [26] and direct [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 37 canonical work pages

  1. [12]

    Banawan and S

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

    work page 1945

  2. [26]

    M. A. Attia, D. Kumar, and R. Tandon. The capacity of priv ate infor- mation retrieval from uncoded storage constrained databas es. Available at arXiv:1805.04104v2

    work page Pith review arXiv

  3. [1]

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

    1998

  4. [2]

    W. Gasarch. A survey on private information retrieval. I n Bulletin of the EATCS , volume 82, pages 72–107, 2004

    work page 2004

  5. [3]

    Cachin, S

    C. Cachin, S. Micali, and M. Stadler. Computationally pr ivate infor- mation retrieval with polylogarithmic communication. In International Conference on the Theory and Applications of Cryptographic Tech- niques. Springer, 1999

    work page 1999

  6. [4]

    N. B. Shah, K. V . Rashmi, and K. Ramchandran. One extra bit of download ensures perfectly private information retrieval . In IEEE ISIT , June 2014

    2014

  7. [5]

    T. Chan, S. Ho, and H. Y amamoto. Private information retr ieval for coded storage. In IEEE ISIT , June 2015

    work page 2015

  8. [6]

    Fazeli, A

    A. Fazeli, A. V ardy, and E. Y aakobi. PIR with low storage o verhead: coding instead of replication. 2015. Available at arXiv:15 05.06241

    work page 2015

Show all 41 references
  1. [7]

    Tajeddine and S

    R. Tajeddine and S. El Rouayheb. Private information ret rieval from MDS coded data in distributed storage systems. In IEEE ISIT , July 2016

    2016

  2. [8]

    Sun and S

    H. Sun and S. A. Jafar. Blind interference alignment for p rivate information retrieval. In IEEE ISIT , July 2016. TABLE I QUERY TABLE FOR M = 2 , N = 6 , µ = 5 12 DB1 DB2 DB3 DB4 DB5 DB6 hT 1 x[1] 1 hT 2 x[1] 1 hT 3 x[1] 2 hT 4 x[1] 2 hT 5 x[1] 3 hT 6 x[1] 3 hT 1 x[1] 4 hT 2 ...

    2016

  3. [9]

    Sun and S

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

    2017

  4. [10]

    Sun and S

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

    2018

  5. [11]

    Sun and S

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

    2019

  6. [13]

    Wang and M

    Q. Wang and M. Skoglund. Symmetric private information retrieval for MDS coded distributed storage. In IEEE ICC , May 2017

    2017

  7. [14]

    Freij-Hollanti, O

    R. Freij-Hollanti, O. Gnilke, C. Hollanti, and D. Karpu k. Private information retrieval from coded databases with colluding servers. SIAM Journal on Applied Algebra and Geometry , 1(1):647–664, 2017

    2017

  8. [15]

    Banawan and S

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

    2018

  9. [16]

    Banawan and S

    K. Banawan and S. Ulukus. The capacity of private inform ation retrieval from byzantine and colluding databases. IEEE Trans. on Info. Theory , 65(2):1206–1219, February 2019

    2019

  10. [17]

    Y .-P . Wei, K. Banawan, and S. Ulukus. Fundamental limit s of cache- aided private information retrieval with unknown and uncod ed prefetch- ing. IEEE Trans. on Info. Theory , 65(5):3215–3232, May 2019

    2019

  11. [18]

    Kadhe, B

    S. Kadhe, B. Garcia, A. Heidarzadeh, S. El Rouayheb, and A. Sprintson. Private information retrieval with side information. Avai lable at arXiv:1709.00112

    arXiv

  12. [19]

    Z. Chen, Z. Wang, and S. Jafar. The capacity of private in formation retrieval with private side information. Available at arXi v:1709.03022

    arXiv

  13. [20]

    Y .-P . Wei, K. Banawan, and S. Ulukus. The capacity of pri vate information retrieval with partially known private side in formation. IEEE Trans. on Info. Theory . Submitted November 2017. Also available at arXiv:1710.00809

    2017 arXiv

  14. [21]

    Y .-P . Wei, K. Banawan, and S. Ulukus. Cache-aided priva te information retrieval with partially known uncoded prefetching: Funda mental limits. IEEE JSAC , 36(6):1126–1139, June 2018

    2018

  15. [22]

    Wei and S

    Y .-P . Wei and S. Ulukus. The capacity of private informa tion re- trieval with private side information under storage constr aints. IEEE Trans. on Info. Theory . Submitted November 2018. Also available at arXiv:1806.01253

    2018 arXiv

  16. [23]

    Li and M

    S. Li and M. Gastpar. Single-server multi-message priv ate information retrieval with side information. Available at arXiv:1808. 05797

  17. [24]

    Mirmohseni and M

    M. Mirmohseni and M. A. Maddah-Ali. Private function re trieval. Available at arXiv:1711.04677

    arXiv

  18. [25]

    Z. Chen, Z. Wang, and S. Jafar. The asymptotic capacity o f private search. In IEEE ISIT , June 2018

    2018

  19. [27]

    Banawan and S

    K. Banawan and S. Ulukus. Asymmetry hurts: Private info rmation retrieval under asymmetric-traffic constraints. IEEE Trans. on Info. Theory. Submitted January 2018. Also available at arXiv:1801.030 79

    2018

  20. [28]

    Banawan and S

    K. Banawan and S. Ulukus. Private information retrieva l through wiretap channel II: Privacy meets security. IEEE Trans. on Info. Theory . Submitted January 2018. Also available at arXiv:1801.0617 1

    2018

  21. [29]

    Banawan and S

    K. Banawan and S. Ulukus. Noisy private information ret rieval: Separability of channel coding and information retrieval. IEEE Trans. on Info. Theory. Submitted July 2018. Also available at arXiv: 1807.05997

    2018 arXiv

  22. [30]

    Z. Jia, H. Sun, and S. Jafar. Cross subspace alignment an d the asymptotic capacity of X-secure T -private information retrieval. Available at arXiv:1808.07457

    arXiv

  23. [31]

    C. Tian, H. Sun, and J. Chen. Capacity-achieving privat e information retrieval codes with optimal message size and upload cost. A vailable at arXiv:1808.07536

    arXiv

  24. [32]

    Bitar and S

    R. Bitar and S. El Rouayheb. Staircase-PIR: Universall y robust private information retrieval. Available at arXiv:1806.08825

    arXiv

  25. [33]

    Kumar, A

    S. Kumar, A. G. i Amat, E. Rosnes, and L. Senigagliesi. Pr ivate information retrieval from a cellular network with caching at the edge. Available at arXiv:1809.00872

    arXiv

  26. [34]

    Kumar, H.-Y

    S. Kumar, H.-Y . Lin, E. Rosnes, and A. G. i Amat. Achievin g maximum distance separable private information retrieval capacit y with linear codes. Available at arXiv:1712.03898

    arXiv

  27. [35]

    Y .-P . Wei, B. Arasli, K. Banawan, and S. Ulukus. The capa city of private information retrieval from decentralized uncoded caching databases. IEEE Trans. on Info. Theory . Submitted November 2018. Also available at arXiv:1811.11160

    2018 arXiv

  28. [36]

    Raviv and I

    N. Raviv and I. Tamo. Private information retrieval in g raph based replication systems. In IEEE ISIT , June 2018

    2018

  29. [37]

    Banawan and S

    K. Banawan and S. Ulukus. Private information retrieva l from non- replicated databases. Available at arXiv:1901.00004

    1901 arXiv

  30. [38]

    Raviv, I

    N. Raviv, I. Tamo, and E. Y aakobi. Private information r etrieval in graph based replication systems. Available at arXiv:1812.01566

    arXiv

  31. [39]

    M. A. Maddah-Ali and U. Niesen. Fundamental limits of ca ching. IEEE Trans. on Info. Theory , 60(5):2856–2867, May 2014

    2014

  32. [40]

    Banawan, B

    K. Banawan, B. Arasli, Y .-P . Wei, and S. Ulukus. The capa city of private information retrieval from heterogeneous uncoded caching databases. IEEE Trans. on Info. Theory . Submitted February 2019. Also available at arXiv:1902.09512

    2019 arXiv

  33. [41]

    Weisstein

    E. Weisstein. Farey sequence. 2006

    2006

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.