Breaking the MDS-PIR Capacity Barrier via Joint Storage Coding

Chao Tian; Hua Sun

REVIEW 3 major objections 4 minor 29 references

Breaking the MDS-PIR Capacity Barrier via Joint Storage Coding

T0 review · 3 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 Jointly encoding messages into MDS-coded databases can push private retrieval rates above the separate-storage capacity barrier, and this paper gives two explicit code families that do it.

desk verdict Explicit joint-storage MDS codes that beat the published separate MDS-PIR capacity; the main caveat is a load-bearing baseline equality asserted without proof and a fixable field-size bound. read the letter →

arxiv 1908.07091 v1 pith:SBGR5PSC submitted 2019-08-19 cs.IT math.IT

Hua Sun , Chao Tian This is my paper · ORCID

classification cs.ITmath.IT MSC 94A1594B0568P20

keywords privateinformationretrievalMDScodesjointstoragecodingcapacitycirculantmatricesCauchySchwartz-Zippellemmadistributed

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

Private information retrieval (PIR) from MDS-coded databases has a known capacity formula, but that formula assumes each message is encoded and stored separately. This paper asks whether jointly encoding all messages into the same MDS storage code can beat that capacity, and answers yes for two parameter families. Explicit storage codes and PIR protocols achieve rate (N-1)/N when two messages are stored with MDS parameter (N,2), and rate 2/(K+1) when K messages are stored with parameter (K+1,K); both exceed the separate-storage capacity. A message-splitting expansion extends both constructions to (2,mN,2m) and (K,m(K+1),mK) for any integer m at least 1. The upshot is that the widely quoted MDS-PIR capacity is a barrier of the separate-storage architecture, not of coded PIR itself.

What carries the argument

The argument rests on three mechanisms. First, for (2,N,2), a cyclic-shift storage code: database 1 stores message a, database 2 stores b, and each later database stores a shifted version of a multiplied by a distinct power of a primitive field element plus b; the MDS property reduces to the full rank of a circulant matrix, certified by a no-common-root criterion for two associated polynomials. Second, for (K,K+1,K), a parity-sum storage code in which one database stores the coordinate-wise sum of all messages, so any K of the K+1 databases decode everything. Third, an expansion technique that multiplies the message length and the number of databases by m, using an m by mK Cauchy matrix (for the K+1 family) or random coefficient matrices validated by the Schwartz-Zippel lemma (for the two-message family) to keep the storage MDS while the PIR rate is unchanged.

What would settle it

For K=2 and m=3, the Section 5.1 storage code requires an m by mK = 3 by 6 Cauchy matrix, which needs 3(K+1)=9 distinct field elements, yet the paper sets q at least (m+1)K=8; checking whether such a code can be instantiated over the field of size 8 would show the stated field-size bound is insufficient as written.

Watch

Extended reading notes

Core claim

The central claim is that the joint-storage capacity C(K,N,T) strictly exceeds the separate-storage capacity C-perp(K,N,T) for two explicit families: (K,N,T) = (2,N,2) with N at least 3, and (K,N,T) = (K,K+1,K) with K at least 2. For the first family, a storage code with N databases each holding N-1 symbols achieves MDS recoverability from any two databases and a PIR rate of (N-1)/N, compared with N/(N+2) for separate encoding. For the second, a code where K databases hold one raw symbol of each of two versions of each message and one database holds their sum achieves MDS recoverability from any K databases and a PIR rate of 2/(K+1), compared with 1/(N(1-((N-1)/N)^N)). The same rates are shown to survive an m-fold expansion, yielding the (2,mN,2m) and (K,m(K+1),mK) families.

Load-bearing premise

The paper's expansion to (K,m(K+1),mK) assumes a field with at least (m+1)K elements, but the construction actually needs m(K+1) distinct field elements to build the Cauchy matrix, so the proof as written only covers m no larger than K.

Editorial extensions

If this is right

For any N at least 3, one message can be privately retrieved from a (2,N,2) joint-storage system at rate (N-1)/N, strictly above the separate-storage rate N/(N+2).
For any K at least 2, any one of K messages can be privately retrieved from a (K,K+1,K) joint-storage system at rate 2/(K+1), strictly above the separate-storage rate.
The gains are preserved under the m-expansion: the same rates hold for (2,mN,2m) and (K,m(K+1),mK) for every integer m at least 1.
Separate MDS-PIR capacity is therefore not the true capacity of MDS-coded PIR; determining the actual capacity C(K,N,T) with a converse is left open.

Reading between the lines

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

The expansion recipe suggests a general scaling law: any linear MDS-storage PIR scheme might be lifted to larger system sizes by replacing each symbol with an m-vector and choosing sufficiently generic coefficients, making the two base constructions instances of a broader phenomenon.
For m > K, the (K,m(K+1),mK) claim likely still holds over a larger field (one with at least m(K+1) elements), but the paper's proof does not establish it as written; a corrected field-size bound would close the gap.
The same joint-storage idea may apply where separate-encoding capacity barriers have been conjectured, such as colluding-server PIR or PIR from regenerating codes, though the MDS property there is more delicate to maintain.

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.

Desk Editor's Note

read the letter

Sun and Tian's paper is worth engaging. It gives two explicit families of joint MDS storage codes with matching PIR protocols that achieve rates strictly above the published separate MDS-PIR capacity: (N-1)/N for (2,N,2), N>=3, and 2/(K+1) for (K,K+1,K), K>=2. The m-expansion in Section 5 extends these to (2,mN,2m) and (K,m(K+1),mK). The constructions are genuinely new; the observation that joint coding might help goes back to [20] and [21], but the earlier works only gave an example and a footnote, not a family of codes.

The technical core is in good shape. The circulant matrix argument in Section 3.2.1 is sound, and the Schwartz-Zippel existence arguments in Section 5.2 correctly bound the product degree. I checked the degree counts and the MDS recovery arguments; they add up. The paper is honest about provenance, citing [20] and [21] in a footnote.

The soft spots are real but not fatal. First, Eq. (14) is load-bearing: the claim that the separate MDS-PIR capacity C_perp equals the uniform linear component-code capacity C_oplus is asserted with 'a close inspection' of the converse in [5]. Every rate comparison uses this baseline, so a referee should demand a self-contained argument or a precise pointer to the exact statement in [5]. The equality is very likely true, but the paper does not show the work.

Second, Section 5.1 requires an m x mK Cauchy matrix, which needs m(K+1) distinct field elements. The paper states q >= (m+1)K. For m>K this bound is too small (m=3, K=2 needs 9 field elements, their bound gives 8). The fix is simply q >= m(K+1), but as written the expanded construction is not instantiated for m>K.

There are also a few minor typos and places where the text says 'no fewer than' when Schwartz-Zippel requires strict inequality. None of these affect the base constructions.

Bottom line: this is a solid constructive result with a completeness gap at the baseline and a field-size bug. I would accept it for peer review and send it back for revision rather than reject. The authors should fix the field-size bound and add a real proof or exact citation for Eq. (14).

Referee Report

3 major / 4 minor

Summary. The paper studies private information retrieval (PIR) from N non-communicating databases that store K messages using an (N,T) MDS code. In contrast to the usual assumption that each message is encoded separately into the databases, the paper allows the messages to be encoded jointly into a single MDS storage code. The author's main claim is that joint storage coding can strictly beat the separate MDS-PIR capacity of Banawan and Ulukus [5]. Specifically, the paper proposes explicit joint storage codes and PIR protocols for (K,N,T)=(2,N,2) with N≥3, achieving rate (N-1)/N, and for (K,K+1,K) with K≥2, achieving rate 2/(K+1); both rates are shown to exceed the corresponding separate MDS-PIR capacity. A further 'expansion' technique is introduced to extend these constructions to (2,mN,2m) and (K,m(K+1),mK) for arbitrary integer m≥1, again with rates (N-1)/N and 2/(K+1). The base constructions in Sections 3 and 4 are explicit, with concrete privacy and correctness arguments; Section 5 uses Cauchy matrices and a Schwartz-Zippel existence argument for the expanded codes.

Significance. If the results are correct, this is a conceptually significant contribution: it shows that the standard MDS-PIR capacity, which is usually quoted as the capacity of MDS-coded PIR, is in fact the capacity only of the separate-coding architecture, and that joint encoding can strictly improve retrieval rates. The explicit constructions in Sections 3 and 4 are concrete and their privacy, MDS, and rate arguments are easy to verify; the expansion technique is novel and identifies two infinite families of parameter triples where the barrier is broken. The main weakness is that the numerical baseline for the comparison, Eq. (14), is asserted rather than proved, and one field-size condition in Section 5.1 is incorrect as stated; both are fixable but load-bearing.

major comments (3)

[Section 5.1, text following Eq. (59)] The construction requires an m×mK Cauchy matrix with entries 1/(α_i-β_j), which needs m distinct α_i's and mK distinct β_j's, i.e., m(K+1) distinct field elements in total. The paper states q ≥ (m+1)K, but for m>K this bound is strictly smaller than m(K+1); for example, m=K+1 gives (m+1)K = K(K+2) while m(K+1)=(K+1)^2, so the required distinct elements need not exist. The correct condition is q ≥ m(K+1). This must be fixed because the m-expansion is part of the advertised parameter range for all m≥1.
[Section 2.2, Eq. (14)] The equality C⊥(K,N,T)=C⊕(K,N,T) is asserted with only the remark 'a close inspection of the converse proof in [5] reveals' and no proof. This equality is the numerical baseline for every claimed improvement in the paper: the rates (N-1)/N and 2/(K+1) are compared against the values computed from Eq. (13), which is the uniform-linear capacity C⊕. If the converse in [5] relies on the uniform component-code assumption in an essential way, the true separate-coding capacity could be larger and the headline comparisons would not follow. Please provide a self-contained proof of Eq. (14), or a precise statement of where in [5] this identity is established; otherwise the theorems should be stated relative to C⊕ only.
[Section 3.2.1, Eqs. (48)-(55)] The proof of invertibility of the circulant matrix rules out common roots x0 only in the base field F_{p^m}. This is insufficient: f(x) and g(x)=x^{N-1}-1 could have a common irreducible factor over F_{p^m} with no root in F_{p^m}, in which case the contradiction at Eq. (50)-(55) would not be reached. The argument can be repaired by working in the algebraic closure of F_{p^m}: any common factor has a common root there, and the same power-raising step gives α^{(j-i)(N-1)}=1, contradicting the primitivity of α and the bound on (j-i)(N-1). As written, however, the proof is incomplete.

minor comments (4)

[Section 3.2, privacy discussion] The text says f-(n-2) should be interpreted modulo (N-2), but the storage code indices are modulo N-1; the modular reduction should be modulo N-1 for the privacy argument to be correct.
[Sections 3.2 and 5] The symbol m is used for the field exponent in Section 3.2 and for the expansion factor in Section 5; this overloading is confusing and should be resolved, for example by using r or s for one of them.
[Section 5.2.2, field-size condition] The Schwartz-Zippel argument requires a strict inequality q > degree for the product polynomial to have a nonzero evaluation point; the text says q is 'no fewer than' the displayed bound, which would allow q equal to the degree and does not guarantee existence. The example in Section 5.2.1 uses the correct strict inequality.
[Sections 4.1 and 4.2] The text refers to recovering 'both messages' in the (3,4,3) example and in the general (K,K+1,K) construction; this should read 'all K messages' (or 'all messages') to avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the joint-storage achievability proofs are self-contained against an externally established separate-coding benchmark.

full rationale

The paper's central claims are explicit achievability constructions: storage codes and PIR protocols that achieve rates (N-1)/N and 2/(K+1), compared to C⊥(K,N,T), the separate-MDS capacity taken from Banawan and Ulukus [5]. No parameter in the constructions is fitted to a data subset; the MDS recovery properties are proved via circulant-matrix rank arguments, Cauchy-matrix properties, and Schwartz-Zippel existence arguments, all within the paper. The equality C⊥=C⊕ in Eq. (14) is a load-bearing interpretation of an external converse, and is potentially contestable as a correctness matter, but it is not circular: it is not derived from the paper's own constructions, nor from the authors' prior work. Self-citations [21] and [22] appear only in a footnote attributing the observation that messages need not be stored separately; they do not carry the proof of the rates or capacity gap. The Section 5.1 field-size condition q ≥ (m+1)K may be insufficient for the m×mK Cauchy matrix (needing m(K+1) distinct field elements), but that is an instantiation/premise issue, not a circularity. Accordingly, no step reduces the claimed results to their inputs by definition or by fitted-parameter renaming.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The constructions use no fitted constants. The h,g coefficients in Section 5.2 are existential design variables whose existence is proven. The main external inputs are the separate MDS-PIR capacity from [5], Ingleton's circulant theorem, Cauchy matrix invertibility, and Schwartz-Zippel. No new physical or abstract entities are introduced.

free parameters (1)

h_{n,j,i}, g_{n,j,i} coefficients = not instantiated (existential via Schwartz-Zippel)
In Section 5.2 the storage and PIR constructions depend on these coefficients. The paper proves existence over a sufficiently large field but does not give explicit values; they are design variables, not fitted to data.

assumptions (5)

domain assumption C⊥(K,N,T)=C⊕(K,N,T) as in Eq. (14)
Adopted from [5] by 'close inspection' of its converse proof; not re-derived here. It is the baseline against which the claimed improvement is measured.
standard math Ingleton's theorem: a circulant matrix has full rank iff f(x) and x^(N-1)-1 have no common root
Used in Section 3.2.1 to prove the MDS property of the first construction.
standard math Schwartz-Zippel lemma
Used in Section 5.2 to prove the existence of coefficients h,g for which the MDS and correctness determinants are all nonzero.
standard math Any square submatrix of a Cauchy matrix is invertible
Used in Section 5.1 to verify MDS recovery from arbitrary T databases in the m-expanded construction.
standard math Finite fields of the required sizes exist
Used throughout; the paper requires prime powers large enough for the circulant rank argument and the Schwartz-Zippel product polynomial bound.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Breaking the MDS-PIR Capacity Barrier via Joint Storage Coding." pith.science (2026). https://pith.science/paper/SBGR5PSC

@misc{pith2026190807091,
  author       = {Pith},
  title        = {Pith review of: Breaking the MDS-PIR Capacity Barrier via Joint Storage Coding},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SBGR5PSC}},
  note         = {Machine review of arXiv:1908.07091}
}

read the original abstract

The capacity of private information retrieval (PIR) from databases coded using maximum distance separable (MDS) codes has been previously characterized by Banawan and Ulukus, where it was assumed that the messages are encoded and stored separably into the databases. This assumption was also usually taken in other related works in the literature, and this capacity is usually referred to as the MDS-PIR capacity colloquially. In this work, we considered the question if and when this capacity barrier can be broken through joint encoding and storing of the messages. Our main results are two classes of novel code constructions which allow joint encoding as well as the corresponding PIR protocols, which indeed outperform the separate MDS-coded systems. Moreover, we show that a simple but novel expansion technique allows us to generalize these two classes of codes, resulting in a wider range of the cases where this capacity barrier can be broken.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 26 canonical work pages

[20]

Private informat ion retrieval for coded storage,

T. H. Chan, S.-W. Ho, and H. Yamamoto, “Private informat ion retrieval for coded storage,” in 2015 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2015, pp. 2842–2846

work page 2015
[21]

Multiround private information retrieval: Capacity and storage overhead,

H. Sun and S. A. Jafar, “Multiround private information retrieval: Capacity and storage overhead,” IEEE Transactions on Information Theory , vol. 64, no. 8, pp. 5743–5754, 2018

work page 2018
[5]

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, 2018

work page 1945
[1]

Pri vate Information Retrieval,

B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan, “Pri vate Information Retrieval,” Journal of the ACM (JACM) , vol. 45, no. 6, pp. 965–981, 1998

work page 1998
[2]

The capacity of private informati on retrieval,

H. Sun and S. A. Jafar, “The capacity of private informati on retrieval,” in Global Communi- cations Conference (GLOBECOM), 2016 IEEE . IEEE, 2016, pp. 1–6

work page 2016
[3]

One extra bit o f download ensures perfectly private information retrieval,

N. B. Shah, K. Rashmi, and K. Ramchandran, “One extra bit o f download ensures perfectly private information retrieval,” in Information Theory (ISIT), 2014 IEEE International Sym- posium on . IEEE, 2014, pp. 856–860

work page 2014
[4]

Private information re- trieval from coded databases with colluding servers,

R. Freij-Hollanti, O. W. Gnilke, C. Hollanti, and D. A. Ka rpuk, “Private information re- trieval from coded databases with colluding servers,” SIAM Journal on Applied Algebra and Geometry, vol. 1, no. 1, pp. 647–664, 2017

work page 2017
[6]

Private Information Retrieval from MDS Coded Data in Distributed Storage Systems

R. Tajeddine and S. E. Rouayheb, “Private Information Re trieval from MDS Coded Data in Distributed Storage Systems,” arXiv preprint arXiv:1602.01458 , 2016

work page Pith review arXiv 2016

Show all 29 references

[7]

On sub-packetization and access numb er of capacity-achieving PIR schemes for MDS coded non-colluding databases,

J. Xu and Z. Zhang, “On sub-packetization and access numb er of capacity-achieving PIR schemes for MDS coded non-colluding databases,” SCIENCE CHINA Information Sciences , vol. 61, no. 7, pp. 100 306:1–100 306:16, 2018. 17

2018
[8]

Achievin g maximum distance separable private information retrieval capacity with linear codes,

S. Kumar, H.-Y. Lin, E. Rosnes, and A. G. i Amat, “Achievin g maximum distance separable private information retrieval capacity with linear codes, ” IEEE Transactions on Information Theory, 2019

2019
[9]

The capacity of priv ate information retrieval from uncoded storage constrained databases,

M. A. Attia, D. Kumar, and R. Tandon, “The capacity of priv ate information retrieval from uncoded storage constrained databases,” arXiv preprint arXiv:1805.04104 , 2018

2018 arXiv
[10]

An optimal iterative placement algorithm for pir from heterogeneous storage-constrained databases,

N. Woolsey, R.-R. Chen, and M. Ji, “An optimal iterative placement algorithm for pir from heterogeneous storage-constrained databases,” arXiv preprint arXiv:1904.02131 , 2019

1904 arXiv
[11]

The cap acity of private information retrieval from heterogeneous uncoded caching databases,

K. Banawan, B. Arasli, Y.-P. Wei, and S. Ulukus, “The cap acity of private information retrieval from heterogeneous uncoded caching databases,” arXiv preprint arXiv:1902.09512 , 2019

1902 arXiv
[12]

Private information retrieval i n graph based replication systems,

N. Raviv and I. Tamot, “Private information retrieval i n graph based replication systems,” in 2018 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2018, pp. 1739–1743

2018
[13]

On the fu ndamental limit of private information retrieval for coded distributed storage,

H.-Y. Lin, S. Kumar, E. Rosnes, and A. G. i Amat, “On the fu ndamental limit of private information retrieval for coded distributed storage,” arXiv preprint arXiv:1808.09018 , 2018

2018 arXiv
[14]

Codes for distribu ted PIR with low storage overhead,

A. Fazeli, A. Vardy, and E. Yaakobi, “Codes for distribu ted PIR with low storage overhead,” in Proceedings of IEEE International Symposium on Information The ory (ISIT) , 2015, pp. 2852–2856

2015
[15]

Lower Bound on the Redundancy of PIR Codes,

S. Rao and A. Vardy, “Lower Bound on the Redundancy of PIR Codes,” arXiv preprint arXiv:1605.01869, 2016

2016 arXiv
[16]

Pir array codes with opti mal virtual server rate,

S. R. Blackburn and T. Etzion, “Pir array codes with opti mal virtual server rate,” IEEE Transactions on Information Theory , 2019

2019
[17]

On private informat ion retrieval array codes,

Y. Zhang, X. Wang, H. Wei, and G. Ge, “On private informat ion retrieval array codes,” IEEE Transactions on Information Theory , 2019

2019
[18]

Batch and pir codes and their connections t o locally repairable codes,

V. Skachek, “Batch and pir codes and their connections t o locally repairable codes,” in Network Coding and Subspace Designs . Springer, 2018, pp. 427–442

2018
[19]

Binary, shorten ed projective reed muller codes for coded private information retrieval,

M. Vajha, V. Ramkumar, and P. V. Kumar, “Binary, shorten ed projective reed muller codes for coded private information retrieval,” in 2017 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2017, pp. 2648–2652

2017
[22]

A Shannon-Theoretic appro ach to the storage-retrieval tradeoﬀ in pir systems,

C. Tian, H. Sun, and J. Chen, “A Shannon-Theoretic appro ach to the storage-retrieval tradeoﬀ in pir systems,” in 2018 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2018, pp. 1904–1908. 18

2018
[23]

Private information retrieval from mds coded data in distributed storage systems,

R. Tajeddine, O. W. Gnilke, and S. El Rouayheb, “Private information retrieval from mds coded data in distributed storage systems,” IEEE Transactions on Information Theory , 2018

2018
[24]

Private information retrieval f rom MDS coded data with colluding servers: Settling a conjecture by Freij-Hollanti et al

H. Sun and S. A. Jafar, “Private information retrieval f rom MDS coded data with colluding servers: Settling a conjecture by Freij-Hollanti et al.” IEEE Transactions on Information Theory, vol. 64, no. 2, pp. 1000–1022, Feb. 2018

2018
[25]

Symmetric private informatio n retrieval for mds coded distributed storage,

Q. Wang and M. Skoglund, “Symmetric private informatio n retrieval for mds coded distributed storage,” in Communications (ICC), 2017 IEEE International Conference on . IEEE, 2017, pp. 1–6

2017
[26]

Capacity-achieving priva te information retrieval codes from MDS-coded databases with minimum message size,

R. Zhou, C. Tian, and H. Sun, “Capacity-achieving priva te information retrieval codes from MDS-coded databases with minimum message size,” in 2019 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2019, pp. 370–374

2019
[27]

The rank of circulant matrices,

A. W. Ingleton, “The rank of circulant matrices,” Journal of the London Mathematical Society , vol. 1, no. 4, pp. 445–460, 1956

1956
[28]

Lidl and H

R. Lidl and H. Niederreiter, Introduction to ﬁnite ﬁelds and their applications . Cambridge university press, 1994

1994
[29]

Exact results for deterministic c ellular automata with additive rules,

P.-h. Guan and Y. He, “Exact results for deterministic c ellular automata with additive rules,” Journal of Statistical Physics , vol. 43, no. 3-4, pp. 463–478, 1986. 19

1986

Pith tools

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

[1] [20]

Private informat ion retrieval for coded storage,

T. H. Chan, S.-W. Ho, and H. Yamamoto, “Private informat ion retrieval for coded storage,” in 2015 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2015, pp. 2842–2846

work page 2015

[2] [21]

Multiround private information retrieval: Capacity and storage overhead,

H. Sun and S. A. Jafar, “Multiround private information retrieval: Capacity and storage overhead,” IEEE Transactions on Information Theory , vol. 64, no. 8, pp. 5743–5754, 2018

work page 2018

[3] [5]

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, 2018

work page 1945

[4] [1]

Pri vate Information Retrieval,

B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan, “Pri vate Information Retrieval,” Journal of the ACM (JACM) , vol. 45, no. 6, pp. 965–981, 1998

work page 1998

[5] [2]

The capacity of private informati on retrieval,

H. Sun and S. A. Jafar, “The capacity of private informati on retrieval,” in Global Communi- cations Conference (GLOBECOM), 2016 IEEE . IEEE, 2016, pp. 1–6

work page 2016

[6] [3]

One extra bit o f download ensures perfectly private information retrieval,

N. B. Shah, K. Rashmi, and K. Ramchandran, “One extra bit o f download ensures perfectly private information retrieval,” in Information Theory (ISIT), 2014 IEEE International Sym- posium on . IEEE, 2014, pp. 856–860

work page 2014

[7] [4]

Private information re- trieval from coded databases with colluding servers,

R. Freij-Hollanti, O. W. Gnilke, C. Hollanti, and D. A. Ka rpuk, “Private information re- trieval from coded databases with colluding servers,” SIAM Journal on Applied Algebra and Geometry, vol. 1, no. 1, pp. 647–664, 2017

work page 2017

[8] [6]

Private Information Retrieval from MDS Coded Data in Distributed Storage Systems

R. Tajeddine and S. E. Rouayheb, “Private Information Re trieval from MDS Coded Data in Distributed Storage Systems,” arXiv preprint arXiv:1602.01458 , 2016

work page Pith review arXiv 2016