{"id":"68231150-db05-4fd3-b878-552b5e3e3b42","arxiv_id":"1908.10854","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A cross-subspace alignment scheme with layered interference cancellation achieves rate 1-(Kc+X+T+2B-1)/(N-U) for X-secure T-private retrieval from MDS-coded storage with U unresponsive and B Byzantine servers, improving prior achievable rates and conjectured asymptotically optimal.","lead":"This paper designs a scheme for retrieving one file from many storage servers without revealing which file, even when some servers collude, fail, or lie, and when data is stored in coded form. It improves the best known efficiency for this private retrieval problem and shows the same technique also speeds up private, secure distributed matrix multiplication.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 5.2's XB=0 PSDMM range (eq. 88) is off by one: the condition L≥1 forces Kc≤N-XA-T, and the stated upper endpoint N+1-XA-T yields L=0 and an undefined download cost.","rationale":"After checking the main scheme, Theorem 1 appears correct for all parameter regimes where L≥1. The U=B=0 construction uses Lemma 1 correctly; the Byzantine generalization with L = (N-U)-(Kc+X+T+2B-1) yields a decoding matrix whose every N-U-2B rows form the same Cauchy-plus-Vandermonde form, hence generate an MDS(N-U,N-U-2B) code with distance 2B+1, sufficient for B errors. The compressed proof in Section 4.2 is a brevity issue, not a correctness gap. The real, verifiable error is the off-by-one in the PSDMM Kc range for XB=0: eq. (88) allows Kc = N+1-XA-T, where L=0 and the download cost is undefined. This does not affect the central PIR theorem, but it makes the stated PSDMM achievable region slightly too large. Thus the CONDITIONAL verdict stands, pending the range correction.","tokens_in":20432,"tokens_out":34519,"duration_ms":336486,"concrete_test":"Recompute the XB=0 PSDMM range from first principles: impose L = N - (XA + XB + T + Kc - 1) ≥ 1 with XB=0, yielding Kc ≤ N - XA - T. Then evaluate the claimed pair at Kc = N+1-XA-T: L=0 and D = N/(N-(Kc+XA+T-1)) has denominator N - (N+1-XA-T+XA+T-1) = 0, so the pair is undefined. Verify the corrected range Kc = 1,...,N-XA-T gives L≥1 and finite D; if so, the achievable region should be restated with the endpoint reduced by one.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The one concrete error I can verify is in the PSDMM application, Section 5.2. In the XB=0 case the authors set L = N - (XA + XB + T + Kc - 1) with XB=0, i.e. L = N - (XA + T + Kc - 1), and claim the lower convex hull of (U,D) = (N/Kc, N/(N - (Kc + XA + T - 1))) is achievable for Kc = 1,2,...,(N+1-XA-T) (eq. 88). But correctness requires L ≥ 1, which gives Kc ≤ N - XA - T. At the allowed endpoint Kc = N+1-XA-T, one has L = 0 and the download denominator N - (Kc + XA + T - 1) = 0, so the corresponding pair is undefined. The correct upper limit is N-XA-T, one less than stated. This is a localized error in a secondary result; it does not affect Theorem 1. The Byzantine extension (eq. 70) is terse but sound: any N-U-2B rows form exactly the matrix of Lemma 1 (with N' = N-U-2B and L' = L), giving an MDS(N-U,N-U-2B) code of minimum distance 2B+1, so up to B arbitrary errors are correctable.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":20715,"tokens_out":8639,"duration_ms":90862,"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":[{"comment":"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.","section":"Section 5.2, eq. (88)"},{"comment":"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.","section":"Section 4.2, eq. (70)"}],"minor_comments":[{"comment":"In the sentence preceding eq. (27), 'his second desired symbol, W11Qθ' should read 'W12Qθ'.","section":"Section 4.1, near eq. (24)-(27)"},{"comment":"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.","section":"Table 3"},{"comment":"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)'.","section":"Section 5.2, after eq. (94)"},{"comment":"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.","section":"Theorem 1 and Section 4"}],"recommendation":"major_revision","confidential_remarks":"The central PIR construction appears correct and is a genuine improvement over prior work. The off-by-one error in the PSDMM section is localized and easily fixable and does not threaten Theorem 1. The Byzantine proof, though correct, is too compressed for a central claim and should be expanded. The paper is likely suitable for publication after these revisions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a real advance for MDS-XSTPIR and its Byzantine/unresponsive generalizations, and the core construction is sound as far as I can tell. The one concrete error I found is in the secondary PSDMM section, not in the PIR theorem.\n\nThe new thing is the layered cross-subspace alignment scheme with successive decoding and interference cancellation. It achieves R = 1 - (Kc + X + T + 2B - 1)/(N - U), which strictly improves the previous best rate from Raviv-Karpuk by removing the Kc/(Kc+X) penalty, and it generalizes the MDS-TPIR rate. The proof of the main theorem is detailed: Lemma 1 is proved in place, the induction over Kc rounds is coherent, and the matrix invertibility arguments check out. The Byzantine extension is compressed but sound: any N-U-2B rows of the decoding matrix form an invertible matrix by Lemma 1, giving an MDS(N-U, N-U-2B) code that corrects up to B errors. Credit where it is due — this is a clean construction, not a repackaging.\n\nThe soft spots are proportionate. Most importantly, optimality is only conjectured; there is no converse, so the paper settles an achievable rate, not capacity. That is not a flaw given the state of MDS-TPIR, but readers should not mistake the conjecture for a proven optimum. Second, the PSDMM section has a concrete off-by-one. In the XB = 0 case, the stated range Kc = 1,...,N+1-XA-T in eq. (88) includes an endpoint where L = N - (XA + T + Kc - 1) becomes zero, making the download cost undefined. The correct upper endpoint is N - XA - T. This is localized and does not affect Theorem 1, but it should be fixed. Third, the download-cost formula relies on the rank lemma from the companion paper [19], valid as q → infinity with chi >= min(lambda, mu); that dependence is stated but worth flagging.\n\nWho is this for? Anyone working on PIR capacity, coded storage, or secure distributed matrix multiplication. It is a solid subfield advance, and the unified view of many PIR settings is genuinely useful. I would bring it to a reading group, and I would cite the main rate result. The off-by-one needs correcting, but the paper deserves a serious referee rather than a desk rejection.","headline":"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.","tokens_in":21322,"tokens_out":1612,"would_cite":true,"duration_ms":19975,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["private information retrieval","MDS coded storage","X-security","T-privacy","Byzantine servers","unresponsive servers","cross-subspace alignment","secure distributed matrix multiplication"],"falsifier":"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.","tokens_in":20199,"feed_emoji":"🔐","tokens_out":7966,"duration_ms":73023,"temperature":0.7,"pith_summary":"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.","feed_headline":"One scheme beats every prior secure-private retrieval rate","feed_subtitle":"Handles colluding, faulty, and unresponsive servers while beating the best known download cost.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces cross-subspace alignment, the method the present scheme builds on.","marker":"[25]"},{"why":"Supplies the MDS-TPIR achievable rate and the asymptotic optimality conjecture that Theorem 1 generalizes by setting $X=0$.","marker":"[26]"},{"why":"Gives the previous best rate for $U$-$B$-MDS-XSTPIR that this paper strictly improves.","marker":"[30]"},{"why":"Provides the rank lemma used to compute the download cost $H(AB_\\theta)=K_c L \\lambda \\mu$ in the PSDMM application.","marker":"[19]"},{"why":"Defines the PSDMM model and gives the upload/download convex hull baseline that the new scheme improves.","marker":"[20]"},{"why":"Establishes MDS-PIR capacity, whose coding structure the storage construction mirrors.","marker":"[24]"}],"fun_headline_variants":["New scheme beats prior secure-private retrieval download costs","Cross-subspace alignment yields better secure private retrieval rates","Conjectured optimal rate for robust MDS secure private retrieval","Coping with Byzantine and unresponsive servers in MDS private retrieval","One protocol improves all known secure private retrieval rates"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["New scheme beats prior secure-private retrieval download costs","Cross-subspace alignment yields better secure private retrieval rates","Conjectured optimal rate for robust MDS secure private retrieval","Coping with Byzantine and unresponsive servers in MDS private retrieval","One protocol improves all known secure private retrieval rates"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00119,"raw_usage":{"total_tokens":4938,"prompt_tokens":1003,"completion_tokens":3935,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":619,"completion_tokens_details":{"reasoning_tokens":3856}},"tokens_in":619,"tokens_out":3935,"duration_ms":29841,"temperature":1.0,"reasoning_tokens":3856,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:34:18.180282+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Cross subspace alignment and the asymptotic capacity of x -secure t -private information retrieval,","cited_arxiv_id":null,"evidence_quote":"Introduces cross-subspace alignment, the method the present scheme builds on."},{"cited_title":"Private Information Retrieval from Coded Databases with Colluding Servers,","cited_arxiv_id":null,"evidence_quote":"Supplies the MDS-TPIR achievable rate and the asymptotic optimality conjecture that Theorem 1 generalizes by setting $X=0$."},{"cited_title":"The Capacity of Private Information Retrieval from Coded Databases,","cited_arxiv_id":null,"evidence_quote":"Establishes MDS-PIR capacity, whose coding structure the storage construction mirrors."}],"review_version":1}