Pith. sign in

REVIEW 2 major objections 4 minor 30 references

$X$-secure $T$-private Information Retrieval from MDS Coded Storage with Byzantine and Unresponsive Servers

T0 review · 2 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 This paper proves that a single cross-subspace-alignment scheme makes the rate $1-(K_c+X+T+2B-1)/(N-U)$ achievable for $X$-secure, $T$-private retrieval from MDS-coded storage with $U$ unresponsive and up to $B$ Byzantine servers…

desk verdict A genuine rate improvement for a broad PIR family, built on a new layered cross-subspace alignment scheme; the main theorem holds, with one localized off-by-one in the PSDMM section. read the letter →

arxiv 1908.10854 v1 pith:FIS334XE submitted 2019-08-28 cs.IT math.IT

Zhuqing Jia , Syed A. Jafar This is my paper · ORCID
classification cs.ITmath.IT
keywords privateinformationretrievalMDScodedstorageX-securityT-privacyByzantineserversunresponsivecross-subspacealignmentsecuredistributedmatrixmultiplication
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 MDS-coded storage when the stored data must be $X$-secure, the query must be $T$-private, up to $U$ servers may be unresponsive, and up to $B$ servers may be Byzantine. Its central result is that the rate $1-\frac{K_c+X+T+2B-1}{N-U}$ is achievable, for any number of messages $K$. This strictly improves the previous best achievable rate, which carried an extra factor $\frac{K_c}{K_c+X}$, and it contains many earlier PIR settings as special cases. The same construction is adapted to private secure distributed matrix multiplication, producing a new lower convex hull of upload/download pairs. A sympathetic reader should care because one coding scheme, built from cross-subspace alignment with successive interference cancellation, unifies and improves a family of known results.

What carries the argument

The load-bearing object is the matrix $M_{L,N}$ whose rows combine Cauchy-type entries $1/(l-\alpha_n)$ with Vandermonde entries $\alpha_n^t$, where $L=N-(K_c+X+T+2B-1)$. Lemma 1 shows $M_{L,N}$ is invertible whenever the $L+N$ evaluation points are distinct elements of the finite field $\mathbb{F}_q$. In each round of the scheme, the answers, after canceling already-decoded message symbols, are represented as $M_{L,N}$ (or its $(N-U)\times(N-U-2B)$ truncation) acting on a vector whose top entries are the desired $L$ symbols and whose remaining entries are interference; inverting the matrix extracts the desired symbols, and the MDS property of the truncation absorbs up to $B$ Byzantine errors. This is cross-subspace alignment in action: desired signals and interference occupy separate, algebraically invertible subspaces.

What would settle it

Compute the determinant of $M_{L,N}$ in (11) for a concrete allowed parameter set, e.g., $N=4$, $K_c=2$, $X=1$, $T=1$, $U=B=0$, over the smallest field with $q\ge 5$ and distinct evaluation points. If any valid choice makes the matrix singular, the successive-decoding step collapses and the claimed rate $1/4$ is not achieved. For the PSDMM application, the download-cost formula assumes $\mathrm{rank}(AB_\theta)=K_c L \lambda \mu$; a rank computation for random matrices with $\chi<\min(\lambda,\mu)$ would expose whether that cost formula has a hidden boundary.

Watch

Extended reading notes

Core claim

Theorem 1 asserts that the rate $R_{U\text{-}B\text{-}MDS\text{-}XSTPIR}(N,K_c,X,T,U,B,K)=1-\frac{K_c+X+T+2B-1}{N-U}$ is achievable for $X$-secure, $T$-private retrieval from $(N,K_c)$ MDS-coded storage with $U$ unresponsive and up to $B$ Byzantine servers. The proof layers multiple rounds of queries: each round exposes a fresh group of desired symbols along one set of directions while confining interference to a complementary subspace, and previously decoded symbols are canceled before the next round. With $U=B=0$ and $K\to\infty$, the authors conjecture the resulting rate $1-\frac{K_c+X+T-1}{N}$ is optimal, which would generalize the long-standing MDS-TPIR conjecture obtained by setting $X=0$. The scheme also strictly improves the previously best known rate for $U$-$B$-MDS-XSTPIR and yields a new lower convex hull for private secure distributed matrix multiplication.

Load-bearing premise

The scheme's Byzantine resilience rests on the assumption that, after the $U$ unresponsive servers are simply dropped, the remaining $N-U$ responses still form an MDS code able to correct $B$ arbitrary errors; this requires the evaluation points to stay distinct, the field to be large enough, and the user to be able to proceed as if the unresponsive servers' identities were known in advance.

Editorial extensions

If this is right

  • With $U=B=0$, the achievable rate becomes $1-\frac{K_c+X+T-1}{N}$, which the authors conjecture is asymptotically optimal as $K\to\infty$.
  • Setting $X=0$ recovers the MDS-TPIR achievable rate $1-\frac{T+K_c-1}{N}$, the subject of a known asymptotic-capacity conjecture.
  • Setting $K_c=1$ and $U=B=0$ reproduces the asymptotic capacity $1-\frac{X+T}{N}$ of XSTPIR with replicated storage.
  • The new rate is strictly larger than the previous $R=(1-\frac{K_c+X+T+2B-1}{N-U})\frac{K_c}{K_c+X}$ for $U$-$B$-MDS-XSTPIR, removing the multiplicative loss $\frac{K_c}{K_c+X}$.
  • For private secure distributed matrix multiplication, the scheme achieves upload/download pairs $(N/K_c,\,N/(N-(2K_c+X_A+X_B+T-2)))$ when $X_B\neq 0$, and $(N/K_c,\,N/(N-(K_c+X_A+T-1)))$ when $X_B=0$, improving previous convex hulls in asymptotic regimes.

Reading between the lines

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

  • This reader's inference: because the rate is achieved for every message count $K$ and needs only $q\ge N+L$, the scheme is not merely an asymptotic construction; small finite-field implementations should exhibit the same rate.
  • This reader's inference: the layered successive-decoding structure is generic enough that it may port to other coded secure-computation problems, such as private linear transformation or private federated learning, wherever interference can be confined to a low-dimensional subspace.
  • This reader's inference: the factor $2$ in front of $B$ suggests each Byzantine server costs the scheme two 'missing' dimensions; a converse showing that Byzantine errors cannot cost less than twice their count would make the formula tight and is a concrete open target.
  • This reader's inference: if the optimality conjecture is settled affirmatively, it would resolve the MDS-TPIR capacity problem as a special case by taking $X=0$, so a converse for MDS-XSTPIR may need new secrecy arguments rather than a simple extension of single-server-privacy bounds.
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

2 major / 4 minor

Summary. The manuscript studies U-B-MDS-XSTPIR, in which K independent messages are stored across N servers according to an MDS(N,Kc+X) code, with X-security, T-privacy, U unresponsive servers, and up to B Byzantine servers. The main result, Theorem 1, states that the rate 1 - ((Kc+X+T+2B-1)/(N-U)) is achievable. The proof presents an explicit scheme based on cross-subspace alignment with successive decoding and interference cancellation, supported by a matrix invertibility lemma (Lemma 1) that is proved in place. The scheme is then specialized to private and secure distributed matrix multiplication (PSDMM), where new lower convex hulls of (upload, download) pairs are claimed. The authors conjecture asymptotic optimality for MDS-XSTPIR when U=B=0.

Significance. If Theorem 1 is correct, the achievable rate strictly improves on the previous best-known rate from [30] and generalizes the MDS-TPIR asymptotic rate of Freij-Hollanti et al. The construction is explicit, with worked examples and a self-contained proof of Lemma 1, and it unifies several prior PIR settings as special cases. The PSDMM application is interesting and potentially useful, but it contains a concrete off-by-one error in the stated achievable range for the XB=0 case. The Byzantine/unresponsive extension is valid but presented too tersely for the central role it plays in Theorem 1. Overall, the main PIR result appears sound, while the PSDMM section needs correction and the Byzantine argument needs expansion.

major comments (2)
  1. [Section 5.2, eq. (88)] The stated range Kc = 1,2,...,(N+1-XA-T) for the XB=0 case is off by one. Since L = N-(XA+XB+T+Kc-1) and the construction requires L >= 1, the correct upper limit is Kc <= N-XA-T. At the stated endpoint Kc = N+1-XA-T one has L = 0, and the download denominator N-(Kc+XA+T-1) becomes zero, so the corresponding pair (U,D) is undefined. The achievable hull statement must be corrected accordingly.
  2. [Section 4.2, eq. (70)] The proof that the (N-U)x(N-U-2B) matrix is the generator matrix of an MDS(N-U,N-U-2B) code is compressed into a single sentence. Please expand it: the user first removes the U unresponsive servers, identifiable by their lack of response, and then applies error correction to the remaining N-U responses. Since any N-U-2B rows of the matrix are invertible by Lemma 1, the code has minimum distance 2B+1 and can correct up to B arbitrary errors. This is the entire correctness argument for the Byzantine and unresponsive extension and should be made self-contained.
minor comments (4)
  1. [Section 4.1, near eq. (24)-(27)] In the sentence preceding eq. (27), 'his second desired symbol, W11Qθ' should read 'W12Qθ'.
  2. [Table 3] Table 3 contains several typographical artifacts, such as 'WL′Kc', 'Z′Kc fL′ 1', and 'L′' used in place of L; please clean up the notation.
  3. [Section 5.2, after eq. (94)] The sentence 'coded according to MDS(N,T), MDS(XA,T), MDS(XB,T)' appears to have typographical errors; it should presumably say 'MDS(N,T), MDS(N,XA), MDS(N,XB)'.
  4. [Theorem 1 and Section 4] The theorem and construction should explicitly state the implicit feasibility condition L >= 1, i.e., N-U >= Kc+X+T+2B-1, since the rate formula and the scheme are only meaningful in that regime.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the MDS-XSTPIR rate is obtained from an explicit construction whose only quoted linear-algebra lemma is proved in the paper.

full rationale

The central claim, Theorem 1, is an achievability bound supported by an explicit storage/query/answer construction in Section 4. The rate R = L/(N-U) follows by counting downloaded and desired symbols, not by fitting or by assuming the target rate. The invertibility step used at every decoding round is Lemma 1, whose proof is included in the paper and does not depend on the theorem. Byzantine robustness follows from the same lemma by observing that every N-U-2B rows of the decoding matrix form an invertible square matrix, giving an MDS code with minimum distance 2B+1. T-privacy and X-security are argued from i.i.d. uniform noise coded as MDS; these are standard masking arguments rather than imported conclusions. The only notable self-citation is [19, Lemma 2] used to evaluate H(AB_theta) in the PSDMM application; it is a parameter-free rank/entropy lemma with stated asymptotic assumptions and does not contain the PIR target result, so it is independent support rather than circularity. The paper itself flags the achievable rates as conjecturally optimal, not as derived from a converse. The off-by-one range in eq. (88) for the XB=0 PSDMM case is a localized correctness issue, not a circularity: it does not smuggle the conclusion into an input.

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

The central scheme has no fitted parameters; it is a constructive coding scheme whose parameters are the problem parameters N, Kc, X, T, U, B. The main external axioms are standard finite-field and MDS facts, the PIR information model, and one rank lemma for random matrix products in the PSDMM application.

assumptions (5)
  • standard math The finite field F_q contains L+N distinct elements 1,...,L, alpha_1,...,alpha_N, i.e., q >= L+N.
    Used to build the MDS storage and query codes and to apply Lemma 1; this is a standard finite-field existence condition, not a fitted parameter.
  • domain assumption Messages W_k are i.i.d. uniform and independent of the user's desired index theta and of all noise variables.
    Assumed in the problem statement, equations (1)-(2), (6), and (17); this is the standard PIR information model.
  • domain assumption Storage uses an MDS(N,Kc+X) code per message and queries use MDS(N,T) noise, so any X servers see only noise and any T servers see only noise.
    Invoked in the security and privacy proofs in Section 4.1.2; relies on Vandermonde/MDS properties of the evaluation maps.
  • standard math The decoding matrix M_{(N-U)x(N-U-2B)} is the generator of an MDS(N-U,N-U-2B) code, i.e., any N-U-2B rows are linearly independent.
    Follows from Lemma 1 for distinct evaluation points; used to correct B Byzantine errors in Section 4.2.
  • domain assumption For PSDMM, H(AB_theta) = Kc*L*lambda*mu when q goes to infinity and chi >= min(lambda, mu), taken from Lemma 2 of [19].
    This rank-fullness assumption underlies the download cost formulas (105) and (110); it is cited from the authors' companion paper and not re-proved here.

how reviews work

0 comments
Cite this review

Pith. "Pith review of $X$-secure $T$-private Information Retrieval from MDS Coded Storage with Byzantine and Unresponsive Servers." pith.science (2026). https://pith.science/paper/FIS334XE

@misc{pith2026190810854,
  author       = {Pith},
  title        = {Pith review of: $X$-secure $T$-private Information Retrieval from MDS Coded Storage with Byzantine and Unresponsive Servers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FIS334XE}},
  note         = {Machine review of arXiv:1908.10854}
}
abstract

The problem of $X$-secure $T$-private information retrieval from MDS coded storage is studied in this paper, where the user wishes to privately retrieve one out of $K$ independent messages that are distributed over $N$ servers according to an MDS code. It is guaranteed that any group of up to $X$ colluding servers learn nothing about the messages and that any group of up to $T$ colluding servers learn nothing about the identity of desired message. A lower bound of achievable rates is proved by presenting a novel scheme based on \emph{cross-subspace alignment} and a successive decoding with interference cancellation strategy. For large number of messages $(K\rightarrow\infty)$ the achieved rate, which we conjecture to be optimal, improves upon the best known rates previously reported in the literature by Raviv and Karpuk, and generalizes an achievable rate for MDS-TPIR previously found by Freij-Hollanti et al. that is also conjectured to be asymptotically optimal. The setting is then expanded to allow unresponsive and Byzantine servers. Finally, the scheme is applied to find a new lower convex hull of (download, upload) pairs of secure and private distributed matrix multiplication that generalizes, and in certain asymptotic settings strictly improves upon the best known previous results.

Figures

Figures reproduced from arXiv: 1908.10854 by the authors.

Figure 1
Figure 1. The U-B-MDS-XSTPIR setting studied in this work generalizes previously studied settings of PIR [2], TPIR [21], MDS-PIR [24], MDS-TPIR [26, 27], XSTPIR [25], U-TPIR [21], B-TPIR [22], and U-B-MDS-TPIR [23] as shown, and finds application beyond PIR in the context of Private Secure Distributed Matrix Multiplication (PSDMM). The capacity of PIR with K messages, N servers, and replicated storage was characterized in [2]… view at source ↗
Figure 2
Figure 2. Model for private secure distributed matrix multiplication (PSDMM). A matrices are XA secure, while B matrices are XB secure. The uploads to be optimized are the Ae terms and the downloads to be optimized are the Y θ terms. The independence between the securely coded matrices is specified as follows. I(A, A˜ [N] ; B[M] , B˜ [N] ) = 0. (73) Matrices must be recoverable from their secret shares. H(A | A˜ [N] ) = 0, (7… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 21 canonical work pages

  1. [19]

    On the capacity of secure distributed matrix multiplication,

    Z. Jia and S. Jafar, “On the capacity of secure distributed matrix multiplication,” arXiv preprint arXiv:1908.06957, 2019

    arXiv 1908

  2. [30]

    Private polynomial computation from lagrange encod- ing,

    N. Raviv and D. A. Karpuk, “Private polynomial computation from lagrange encod- ing,” IEEE Transactions on Information Forensics and Security , pp. 1–1, 2019, doi: 10.1109/TIFS.2019.2925723. 24

    arXiv 2019

  3. [1]

    Private information retrieval,

    B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, “Private information retrieval,” in Proceedings of the 36th Annual Symposium on Foundations of Computer Science , 1995, pp. 41–50

    work page 1995

  4. [2]

    The Capacity of Private Information Retrieval,

    H. Sun and S. A. Jafar, “The Capacity of Private Information Retrieval,” IEEE Transactions on Information Theory , vol. 63, no. 7, pp. 4075–4088, July 2017

    work page 2017

  5. [3]

    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

    work page 2018

  6. [4]

    On the efficiency of local decoding procedures for error-correcting codes,

    J. Katz and L. Trevisan, “On the efficiency of local decoding procedures for error-correcting codes,” in Proceedings of the thirty-second annual ACM symposium on Theory of computing . ACM, 2000, pp. 80–86

    work page 2000

  7. [5]

    Locally Decodable Codes and Private Information Retrieval Schemes,

    S. Yekhanin, “Locally Decodable Codes and Private Information Retrieval Schemes,” Ph.D. dissertation, Massachusetts Institute of Technology, 2007

    work page 2007

  8. [6]

    On the Locality of Codeword Symbols,

    P. Gopalan, C.Huang, H. Simitci, and S. Yekhanin, “On the Locality of Codeword Symbols,” IEEE Transactions on Information Theory , vol. 58, no. 11, pp. 6925–6934, Nov. 2012

    work page 2012

Show all 30 references
  1. [7]

    Batch codes and their applications,

    Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai, “Batch codes and their applications,” in Proceedings of the thirty-sixth annual ACM symposium on Theory of computing . ACM, 2004, pp. 262–271

    2004

  2. [8]

    How to exchange secrets with oblivious transfer

    M. O. Rabin, “How to exchange secrets with oblivious transfer.” 1981

    1981

  3. [9]

    Protecting data privacy in private information retrieval schemes,

    Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin, “Protecting data privacy in private information retrieval schemes,” in Proceedings of the thirtieth annual ACM symposium on Theory of computing. ACM, 1998, pp. 151–160

    1998

  4. [10]

    On hiding information from an oracle,

    M. Abadi, J. Feigenbaum, and J. Kilian, “On hiding information from an oracle,” inProceedings of the nineteenth annual ACM symposium on Theory of computing . ACM, 1987, pp. 195–203

    1987

  5. [11]

    How to share a secret,

    A. Shamir, “How to share a secret,” Communications of the ACM , vol. 22, pp. 612–613, 1979

    1979

  6. [12]

    Blind Interference Alignment,

    S. A. Jafar, “Blind Interference Alignment,” IEEE Journal of Selected Topics in Signal Pro- cessing, vol. 6, no. 3, pp. 216–227, June 2012

    2012

  7. [13]

    Blind interference alignment for private information retrieval,

    H. Sun and S. A. Jafar, “Blind interference alignment for private information retrieval,” 2016 IEEE International Symposium on Information Theory (ISIT) , pp. 560–564, 2016. 22

    2016

  8. [14]

    Protocols for secure computations,

    A. C. Yao, “Protocols for secure computations,” in Foundations of Computer Science, 1982. SFCS’08. 23rd Annual Symposium on . IEEE, 1982, pp. 160–164

    1982

  9. [15]

    On the capacity of secure distributed matrix multiplication,

    W.-T. Chang and R. Tandon, “On the capacity of secure distributed matrix multiplication,” arXiv preprint arXiv:1806.00469 , 2018

    2018 arXiv

  10. [16]

    Gasp codes for secure distributed matrix multiplication,

    R. G. D’Oliveira, S. E. Rouayheb, and D. Karpuk, “Gasp codes for secure distributed matrix multiplication,” arXiv preprint arXiv:1812.09962 , 2018

    2018 arXiv

  11. [17]

    Rate-efficiency and straggler-robustness through par- tition in distributed two-sided secure matrix computation,

    J. Kakar, S. Ebadifar, and A. Sezgin, “Rate-efficiency and straggler-robustness through par- tition in distributed two-sided secure matrix computation,” arXiv preprint arXiv:1810.13006 , 2018

    2018 arXiv

  12. [18]

    Distributed and private coded matrix computation with flexible communication load,

    M. Aliasgari, O. Simeone, and J. Kliewer, “Distributed and private coded matrix computation with flexible communication load,” arXiv preprint arXiv:1901.07705 , 2019

    1901 arXiv

  13. [20]

    On the upload versus download cost for secure and private matrix multiplication,

    W. Chang and R. Tandon, “On the upload versus download cost for secure and private matrix multiplication,” arXiv preprint arXiv:1906.10684 , 2019

    1906 arXiv

  14. [21]

    The Capacity of Robust Private Information Retrieval with Colluding Databases,

    H. Sun and S. A. Jafar, “The Capacity of Robust Private Information Retrieval with Colluding Databases,” IEEE Transactions on Information Theory , vol. 64, no. 4, pp. 2361–2370, April 2018

    2018

  15. [22]

    The capacity of private information retrieval from byzantine and colluding databases,

    K. Banawan and S. Ulukus, “The capacity of private information retrieval from byzantine and colluding databases,” IEEE Transactions on Information Theory, vol. 65, no. 2, pp. 1206–1219, Feb 2019

    2019

  16. [23]

    Private informa- tion retrieval from coded storage systems with colluding, byzantine, and unresponsive servers,

    R. Tajeddine, O. W. Gnilke, D. Karpuk, R. Freij-Hollanti, and C. Hollanti, “Private informa- tion retrieval from coded storage systems with colluding, byzantine, and unresponsive servers,” IEEE Transactions on Information Theory , vol. 65, no. 6, pp. 3898–3906, June 2019

    2019

  17. [24]

    The Capacity of Private Information Retrieval from Coded Databases,

    K. Banawan and S. Ulukus, “The Capacity of Private Information Retrieval from Coded Databases,” IEEE Transactions on Information Theory , vol. 64, no. 3, pp. 1945–1956, 2018

    1945

  18. [25]

    Cross subspace alignment and the asymptotic capacity of x -secure t -private information retrieval,

    Z. Jia, H. Sun, and S. A. Jafar, “Cross subspace alignment and the asymptotic capacity of x -secure t -private information retrieval,” IEEE Transactions on Information Theory , vol. 65, no. 9, pp. 5783–5798, Sep. 2019

    2019

  19. [26]

    Private Information Retrieval from Coded Databases with Colluding Servers,

    R. Freij-Hollanti, O. Gnilke, C. Hollanti, and D. Karpuk, “Private Information Retrieval from Coded Databases with Colluding Servers,” SIAM Journal on Applied Algebra and Geometry , vol. 1, no. 1, pp. 647–664, 2017

    2017

  20. [27]

    Private Information Retrieval from MDS Coded Data with Colluding Servers: Settling a Conjecture by Freij-Hollanti et al

    H. Sun and S. A. Jafar, “Private Information Retrieval from 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, February 2018

    2018

  21. [28]

    Private secure coded computation,

    M. Kim and J. Lee, “Private secure coded computation,” IEEE Communications Letters, pp. 1–1, 2019, doi: 10.1109/LCOMM.2019.2934436. 23

    2019

  22. [29]

    One Extra Bit of Download Ensures Perfectly Pri- vate Information Retrieval,

    N. Shah, K. Rashmi, and K. Ramchandran, “One Extra Bit of Download Ensures Perfectly Pri- vate Information Retrieval,” in Proceedings of IEEE International Symposium on Information Theory (ISIT), 2014, pp. 856–860

    2014

Pith tools

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