{"id":"e1b36de2-6489-4e86-9bb5-9f4cc904078e","arxiv_id":"1908.07091","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Joint encoding of messages in MDS-coded storage can strictly increase private information retrieval rates beyond the separate-coding capacity for two parametric families of systems.","lead":"Private information retrieval lets a user download one file from several databases without revealing which file. This paper shows that storing the files together in a cleverly coded form can lower the download cost below a previously accepted limit.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The comparative claim depends on Eq. (14) equating separate and uniform-linear MDS-PIR capacity, which is asserted without proof.","rationale":"The main existence proofs are explicit and mostly verifiable: the (2,N,2) construction with circulant matrices is concrete, the (K,K+1,K) construction is simple and checked through the rate inequality, and the expansion in Section 5.2 uses Schwartz-Zippel with explicit bounds. Machine-checkable or fully independent support is not provided, but the constructions are given in enough detail that the MDS and PIR properties are checkable. The remaining weak points are fixable rather than fatal: the field-size bound q ≥ (m+1)K in Section 5.1 is indeed insufficient for an m×mK Cauchy matrix (requires m(K+1) distinct field elements), and the proof of Eq. (14) equating the three capacities is missing. Since the whole paper is built on the claim that the separate-coding capacity is exactly the Banawan-Ulukus value, that unproved equality is the most load-bearing concern. A conditional accept is appropriate.","tokens_in":16606,"tokens_out":1191,"duration_ms":11589,"concrete_test":"Independently re-derive the converse in [5] (Banawan-Ulukus) without assuming that each message is encoded separately with identical uniform component codes; alternatively, state and prove a lemma showing that every separate MDS-PIR scheme can be symmetrized to a uniform linear component-code scheme without changing capacity. The test passes for the paper if the derivation yields C⊥ = (1 + T/N + ... + (T/N)^{K-1})^{-1} in the general separate-coding model; if it requires the uniform-component assumption, the baseline value used to claim a barrier is broken is unsupported.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim is that joint storage strictly beats separate MDS-PIR capacity. That requires the baseline value C⊥(K,N,T) used in all comparisons to be correct. The authors assert in Eq. (14) that C⊥(K,N,T) = C⊕(K,N,T), citing only 'a close inspection of the converse proof in [5]'. The reader did flag this as the weakest assumption, and it is the single most load-bearing step because both rate comparisons and the expansion claims depend on the numerical baseline. If the proof in [5] only applies to the uniform linear component-code model, then the rate N/(N+2) and 2/(K+1) may exceed a different, larger separate-coding capacity. The factual substance of the paper's constructions can be verified independently, but the headline achievement 'breaking the capacity barrier' depends on this equality.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":16658,"tokens_out":15505,"duration_ms":167880,"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":[{"comment":"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":"Section 5.1, text following Eq. (59)"},{"comment":"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":"Section 2.2, Eq. (14)"},{"comment":"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.","section":"Section 3.2.1, Eqs. (48)-(55)"}],"minor_comments":[{"comment":"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.","section":"Section 3.2, privacy discussion"},{"comment":"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":"Sections 3.2 and 5"},{"comment":"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.","section":"Section 5.2.2, field-size condition"},{"comment":"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.","section":"Sections 4.1 and 4.2"}],"recommendation":"major_revision","confidential_remarks":"The paper's central contribution is interesting and the base constructions are largely sound, but the identity in Eq. (14) is the mathematical foundation of the 'capacity barrier' claim and is asserted without proof. If the authors cannot supply a proof or a precise citation, the paper should be reframed as showing improvement over the uniform-linear MDS-PIR capacity rather than over the separate-coding capacity. The other issues identified are routine fixes, but Eq. (14) and the Cauchy-matrix field-size condition should be checked carefully in the revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nSecond, 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.\n\nThere 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.\n\nBottom 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).","headline":"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.","tokens_in":17270,"tokens_out":9528,"would_cite":true,"duration_ms":85991,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","94B05","68P20"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["private information retrieval","MDS codes","joint storage coding","capacity","circulant matrices","Cauchy matrices","Schwartz-Zippel lemma","distributed storage"],"falsifier":"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.","tokens_in":16290,"feed_emoji":"🔐","tokens_out":7584,"duration_ms":68312,"temperature":0.7,"pith_summary":"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.","feed_headline":"Joint coding beats MDS-PIR capacity for two code families","feed_subtitle":"Messages stored together retrieve privately at rates (N-1)/N and 2/(K+1), past the separate-storage limit","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the separate MDS-PIR capacity formula and the converse that C-perp equals C-plus; this is the capacity barrier the paper breaks.","marker":"[5]"},{"why":"Provides the rank criterion for circulant matrices used to prove the MDS property of the (2,N,2) storage code.","marker":"[27]"},{"why":"Supplies the finite-field facts about primitive elements and field sizes used in both base constructions and the expansion.","marker":"[28]"}],"fun_headline_variants":["Joint storage coding beats MDS-PIR for two families","Two code families exceed separate-storage PIR capacity","New joint-storage codes push PIR beyond MDS barrier","Breaking MDS-PIR barrier with joint encoding schemes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Joint storage coding beats MDS-PIR for two families","Two code families exceed separate-storage PIR capacity","New joint-storage codes push PIR beyond MDS barrier","Breaking MDS-PIR barrier with joint encoding schemes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000239,"raw_usage":{"total_tokens":1502,"prompt_tokens":922,"completion_tokens":580,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":538,"completion_tokens_details":{"reasoning_tokens":514}},"tokens_in":538,"tokens_out":580,"duration_ms":6239,"temperature":1.0,"reasoning_tokens":514,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:30:06.188342+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"The capacity of private inform ation retrieval from coded databases,","cited_arxiv_id":null,"evidence_quote":"Supplies the separate MDS-PIR capacity formula and the converse that C-perp equals C-plus; this is the capacity barrier the paper breaks."},{"cited_title":"The rank of circulant matrices,","cited_arxiv_id":null,"evidence_quote":"Provides the rank criterion for circulant matrices used to prove the MDS property of the (2,N,2) storage code."},{"cited_title":"Lidl and H","cited_arxiv_id":null,"evidence_quote":"Supplies the finite-field facts about primitive elements and field sizes used in both base constructions and the expansion."}],"review_version":1}