{"id":"fb9f93ae-4f4a-4fdd-8a0f-e8a69663e75e","arxiv_id":"1908.10821","paper_version":3,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper claims two private coded caching schemes, but the virtual-user scheme leaks demand information while the MDS-based scheme appears to satisfy the privacy constraint.","lead":"This paper defines a caching model in which each user's file requests must remain secret from the other users, and it proposes two delivery schemes intended to keep that secrecy while still saving bandwidth. One scheme, based on replacing each file by coded pieces, appears to work; the other, based on adding virtual users, has a privacy leak in the messages it broadcasts.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The virtual-user scheme fails its own privacy constraint: multicast messages reveal each real user's demand vector through subfile labels, so Theorem 2 and the virtual-user-dependent order-optimality results do not hold as stated.","rationale":"The reader's weakest assumption pinpoints exactly the false step: the virtual-user scheme's privacy proof assumes that uniform multiplicity of demand sets over effective users makes the whole transcript independent of D\\{k}, even though each message's subfile labels carry the file indices and contributor identities. Inspection of Eq. (22) and the decodability argument in Section IV-A shows user k must know the composition of X_S, including the demanded file indices of other effective users in S, so the required conditional independence fails. The minimal L=1, K=2, N=3 example is a direct counterexample to privacy constraint (11). This is an internal correctness failure, not a disagreement with the community's converse bounds, so it warrants rejection of the virtual-user scheme's claims. The MDS-based scheme appears substantially better supported, with formal privacy proofs in Appendices C and D, so the paper is not wholly without value; but the central advertised result Theorem 2 and the virtual-user order-optimality theorems are invalid as written. Because the reader already reached REJECT and identified the same assumption, no verdict change is needed.","tokens_in":25219,"tokens_out":6966,"duration_ms":74127,"concrete_test":"Instantiate the virtual-user scheme of Section IV-A for L=1, K=2, N=3, U=6, t=1 and enumerate all demand pairs (d_1,d_2) in {1,2,3}^2. For each pair, write down the full transcript X including metadata, together with cache Z_1. Compute the posterior Pr[D_2=b | X, Z_1, d_1] for b=1,2,3; privacy holds only if this posterior equals the prior for every d_1 and every transcript. Direct inspection of X_{1,2} shows the posterior places mass 1 on the observed d_2, so I(D\\{1};X|Z_1,d_1)=log 2 > 0. If the authors instead propose stripping file indices from the metadata, the test should exhibit a concrete decodability procedure for user 1 from X_{1,2} that does not use the file index of the other user's subfile.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is the Privacy paragraph of Section IV-A, which asserts that because each L-subset is demanded by K effective users and placement permutations are hidden, the composition of X is equivalent for all demand matrices from each user's viewpoint. This is false. In X_S (Eq. 22), each effective user k_j contributes subfiles f_{d_{k_j,1},S\\{k_j\\}},...,f_{d_{k_j,L},S\\{k_j\\}}; the labels contain both the file indices of that user's demand vector and the identity S\\{k_j\\} of the contributor. Real users are the first K effective users and identities are public, so a real user k sharing a set S with another real user j can read d_j directly from the metadata/composition of X_S. Example: L=1, K=2, N=3, t=1, message X_{1,2} = f_{d_1,{2}} XOR f_{d_2,{1}}; user 1 must know f_{d_2,{1}} is present to cancel it, and thereby learns d_2. This violates I(D\\{1};X|Z_1,d_1)=0 in (11). Symmetry over whole-library file counts concerns marginal multiplicities, not conditional independence of D\\{k} given the actual transcript, so it does not remove the leak. Theorem 2 and the virtual-user parts of Theorems 3 and 5 are therefore unsupported; the MDS-based scheme may remain correct, but the paper's central virtual-user claim fails.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies an information-theoretic shared-link coded caching model in which each of K users requests L files and the demand of every user must be kept private from the other users, formalized as zero mutual information in Eq. (11). The paper proposes two schemes: a virtual-user scheme that runs MAN delivery over C(N,L)K effective users so that each demand vector is requested by exactly K users, and an MDS-based scheme with a randomized placement and multicast messages that contain one symbol from every file. For these schemes it claims the memory-load tradeoffs of Theorems 2 and 4, and order optimality within constant factors relative to known non-private converse bounds (Theorems 3, 5, and 6).","tokens_in":25490,"tokens_out":21231,"duration_ms":223052,"significance":"If the privacy proofs were correct, the paper would establish a substantial and non-obvious result: information-theoretic demand privacy among users is achievable in the shared-link caching model with only a constant-factor load increase over non-private MAN caching in most regimes, and with sub-packetization comparable to MAN for the MDS-based scheme. The problem formulation is clean, and the MDS placement construction together with the decodability analysis (e.g., Lemma 1) are genuine technical contributions. However, the privacy arguments are not correct: both schemes leak demand information through the public metadata that identifies the subfiles in each multicast message. Since the privacy guarantee is the paper's central claim, the main theorems are not established as stated.","major_comments":[{"comment":"The virtual-user scheme does not satisfy the privacy constraint (11). In each MAN message X_S generated in Eq. (22), the subfile labels f_{d_{kj,l},S\\{k_j}} include the file indices of the demand vector of every effective user k_j in S. Because the real users are the first K effective users and the placement rule (user k caches f_{i,W} iff k is in W) is public, a real user k observing the metadata M(P) can read the demand vector of any other real user j from the labels in messages with j in S. For example, with L=1, K=2, N=3, and t=1, the message X_{1,2}=f_{d_1,{2}} XOR f_{d_2,{1}} tells user 1 the value of d_2 before decoding, so I(D\\{1};X|Z_1,d_1)>0. The symmetry argument in the Privacy paragraph concerns marginal multiplicities over the whole library and does not establish conditional independence of D\\{k} given the observed labeled transcript. Consequently Theorem 2 and the virtual-user-based parts of Theorems 3 and 5 are unsupported.","section":"Section IV-A, Eq. (22) and Privacy paragraph"},{"comment":"The MDS-based scheme has the same label-leakage problem, and the proof in Appendix C does not address it. The transmitted packet X includes the metadata M(P) as part of X (Section II-A), and the decodability argument in Section IV-B requires each user to know the subfile labels in each X_S in order to cancel the terms it has cached. These labels are of the form f_{i,S∪Q_i\\(S∩Q_i)} and therefore reveal to user k which users in S do or do not request a file i that user k itself demands. In the K=2, N=3, L=1 example of Section I-C, the label of the F_1 term in X_{1,2} is {2} when D=(1,2) and ∅ when D=(1,1); user 1 can distinguish these two cases from the metadata, so (11) is violated. Appendix C computes the probability of the MDS symbol values in Eq. (53) but does not condition on the observed label pattern or on the fact that the labels themselves are deterministic functions of D; the probability of the full observation (labels plus values) is D-dependent. Thus the privacy claim for the MDS scheme in Theorem 4, and the MDS-based parts of Theorems 5 and 6, are not established.","section":"Appendix C and Eq. (42)"}],"minor_comments":[{"comment":"The displayed derivation in Eq. (46) is typeset in a confusing way; the factor (N choose L) appears outside the fraction, and the justification of the inequality would be clearer if written as (N choose L)/((N choose L)t'+1) ≤ 2/(t'+1).","section":"Appendix A-A, Eq. (46)"},{"comment":"The dimensions in Eq. (22) use G_{L×L(t+1)} to produce L linear combinations, but the decodability paragraph says 'any L columns are linearly independent'; this is consistent, yet the notation would benefit from an explicit statement that the matrix is applied to the stacked vector of L(t+1) subfiles.","section":"Section IV-A, Eq. (22)"}],"recommendation":"reject","confidential_remarks":"The reader's assessment is correct, and the issue is broader than the reader's report indicates: the MDS-based scheme also leaks through the public subfile labels, so the formal privacy proofs in Appendices C and D are invalid for the same reason. As written, the paper does not contain a correct private scheme among its two proposals, and the flaw is not a local presentation issue but a failure of the central privacy guarantee."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read the paper. Bottom line: the problem formulation and the MDS-based scheme are real contributions, but the virtual-user scheme is not private as written, and since Theorem 2 and the virtual-user parts of Theorems 3 and 5 lean on it, those results don't stand. I side with the stress-test note here; the leak is not subtle.\n\nWhat is genuinely new: the model is different from wiretap secret caching and PIR, and it is a sensible question. The private placement precoding (random permutation over MDS symbols per file) is a neat trick. The MDS-based scheme in Section IV-B has an actual formal privacy proof in Appendices C and D, and it looks sound: each multicast message contains one symbol from every file, and the permutation makes cached vs uncached symbols exchangeable from any user's viewpoint. Its O(2^K) subpacketization is a real improvement over the virtual-user construction.\n\nThe soft spot is exactly where the reader put it. In the virtual-user scheme, each multicast message X_S contains subfiles f_{d_j,S without j}. The labels include the file index d_j and the subset S without j, and user j is a real user whose identity is public. So user k in S sees the file index of user j's demand directly in the metadata it needs to decode. The Privacy paragraph claims symmetry of the whole set of messages over the library, but that is a marginal symmetry over demand counts, not conditional independence of D without k given the actual transcript. The L=1, K=2 example is exactly right: user 1 must see f_{d_2,{1}} in X_{1,2} to cancel it, and therefore learns d_2. No hidden placement permutation removes that, because the metadata has to identify the subfile.\n\nSo Theorem 2 is unproven and false as stated. Theorem 3's virtual-user order-optimality results inherit the problem. The MDS-based scheme may still be correct, but the paper's advertised central claim about the virtual-user scheme fails. Citation pattern is unremarkable: the self-cited converse bounds are external published results, not circular.\n\nWho is this for: people working on private caching or content-delivery privacy might read it for the problem formulation and the MDS-based scheme, not for the virtual-user story. It deserves a serious referee because the good half is solid and the flaw is instructive, but I would not cite the virtual-user scheme. Recommendation: send to peer review, with a clear expectation that Theorem 2 and the virtual-user order-optimality claims need major repair or removal.","headline":"The MDS-based scheme and the problem setup are worth attention, but the virtual-user scheme leaks other users' demands in its multicast metadata, so the paper's central load claims do not hold as stated.","tokens_in":26019,"tokens_out":6589,"would_cite":false,"duration_ms":63760,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that coded caching can hide each user's demands from other users with only a constant-factor load penalty, and supports this with two symmetric-multicast schemes.","keywords":["coded caching","demand privacy","information-theoretic privacy","virtual users","MDS code","shared-link model","order optimality","multicast messages"],"falsifier":"Run the virtual-user scheme with $K=2$, $N=3$, $L=1$, and $t=1$: fix user 1's demand and cache, and compute the conditional distribution of the transmitted message set $X$ when user 2 demands file 1 versus file 2; the message $X_{\\{1,2\\}}$ contains a subfile whose name includes the other user's demand, so the two conditional distributions differ and $I(D_{\\setminus\\{1\\}};X|Z_1,d_1)>0$, contradicting the claimed privacy constraint.","tokens_in":24983,"feed_emoji":"🔒","tokens_out":9393,"duration_ms":91989,"temperature":0.7,"pith_summary":"This paper asks whether a shared-link coded caching system can hide each user's requested files from the other users while retaining the load savings of coded caching. It answers yes in most parameter regimes, proposing two schemes whose transmitted multicast messages are symmetric over the file library from each user's viewpoint. The virtual-user scheme pads the system with virtual users so that every possible demand set is requested equally often, then runs the MAN delivery scheme; the MDS-based scheme uses random permutations and MDS-coded subfiles so that each multicast message looks the same over all files. The paper proves constant-factor order optimality against existing non-private converse bounds in the main regimes, with an open gap when $N<LK$ and $M<N/K$.","feed_headline":"Two schemes make coded caching demand-private at constant-factor cost","feed_subtitle":"Virtual-user and MDS multicast hide each user's requests from the others while staying order-optimal in most regimes.","key_machinery":"The load-bearing machinery is a combination of three pieces. First, private placement precoding: each file is split into pieces or MDS-coded symbols, and a random permutation assigns them to subfile positions indexed by user subsets, so that from any user's viewpoint all cached, respectively uncached, symbols of a file are interchangeable and reveal nothing about who else caches them. Second, symmetric multicast generation: in the MDS-based scheme each message $X_S = G_{L\\times N}[f_{1,S\\cup Q_1\\setminus(S\\cap Q_1)};\\dots;f_{N,S\\cup Q_N\\setminus(S\\cap Q_N)}]$ contains exactly one coded symbol from each file, with $G_{L\\times N}$ an MDS parity-check matrix whose any $L$ columns are linearly independent, and Lemma 1 guarantees no subfile appears in two messages, making the whole set of messages symmetric over files. Third, virtual-user padding: in the virtual-user scheme, $\\binom{N}{L}K-K$ virtual users are created so each possible $L$-subset is demanded by exactly $K$ effective users, after which MAN multicast messages over the $\\binom{N}{L}K$ effective users give the claimed load. The MDS scheme's sub-packetization is $O(2^K)$, exponentially smaller than the virtual-user scheme's sub-packetization.","core_discovery":"The paper's central claim is that information-theoretic demand privacy (for every user $k$, the mutual information between the other users' demand vectors $D_{\\setminus\\{k\\}}$ and the broadcast $X$ given user $k$'s cache $Z_k$ and demand $d_k$ is zero) is compatible with a nontrivial coded caching gain. On the paper's own terms, the key is to generate a set of multicast messages that is symmetric over the whole file library from each user's viewpoint, so that the transmission's composition does not depend on which files the other users requested. The virtual-user scheme achieves this by adding virtual users until every $L$-subset of files is demanded by exactly $K$ effective users and then applying the MAN delivery scheme to the enlarged user set; the MDS-based scheme achieves it message-by-message, by private placement precoding plus one MDS-coded symbol per file in every multicast message. The claimed consequence is that the achieved load is within a constant factor of the best known non-private coded caching load whenever $N\\le LK$, or $N>LK$ and $M\\ge N/K$, and within a factor of 2 when $M\\ge N/2$; at sufficiently large memory the MDS scheme matches the non-private converse exactly, achieving $R=L(1-M/N)$.","pith_inferences":["The symmetry principle is portable: any multicast delivery scheme whose message set is file-symmetric from each user's view should satisfy the same privacy definition, so the virtual-user padding or per-file MDS balancing could be applied to device-to-device or multi-server caching with the same privacy guarantee.","A testable repair for the virtual-user scheme is to randomize the mapping from real users to effective-user indices and to re-label message compositions so that subfile names carry no demand identity; whether this restores zero mutual information without changing the load is open.","A dedicated converse for the privacy-constrained problem, rather than borrowing non-private bounds, would show whether the constant-factor claims are tight in the open regime $N<LK,\\ M<N/K$; if the privacy constraint strictly increases the minimum load there, the open gap is not an artifact of the construction.","The private placement precoding idea might combine with decentralized placement, where caches are filled independently, to yield private caching without a central coordinator; the random-permutation step already gives each user the interchangeability property needed for the privacy argument."],"forward_implications":["If the schemes are correct, a caching server can offer demand privacy to its users as a default service with at most a constant-factor load increase over ordinary coded caching in the covered regimes.","At memory sizes $M\\ge \\min\\{(2^K-1)/2^K,\\ (2^K-1)/(2^{K-1}+1)\\}\\cdot N$, the MDS-based scheme achieves exactly $L(1-M/N)$, the same load as the non-private lower bound, so privacy costs nothing at high cache sizes.","The MDS-based scheme's $O(2^K)$ sub-packetization makes it implementable for realistic parameter sizes, unlike the virtual-user scheme whose sub-packetization grows like $2^{\\binom{N}{L}K}$.","In the regime $N<LK$ and $M<N/K$, neither scheme is shown order-optimal, so a deployment there cannot yet claim a constant-factor privacy cost.","Because the privacy constraint forces equal load for every demand matrix, these schemes also guarantee that the transmission length itself cannot be used as a side channel about the demands."],"supporting_citations":[{"why":"Supplies the MAN coded caching scheme that both proposed private schemes build on.","marker":"[2]"},{"why":"Introduces the virtual-user idea that the virtual-user scheme adapts to information-theoretic privacy.","marker":"[22]"},{"why":"Provides the factor-2 converse bound used in Theorem 3 for $N>K$, $M\\ge N/K$.","marker":"[4]"},{"why":"Provides the factor-4 converse bound used in Theorem 3 for $N\\le K$.","marker":"[5]"},{"why":"Provides the factor-11 converse bound for multiple requests used in Theorem 3 when $L>1$.","marker":"[8]"},{"why":"Gives the converse $R\\ge L(1-M/N)$ used for Theorem 5 and Theorem 6.","marker":"[33]"},{"why":"Supplies the MDS parity-check matrices whose any $L$ columns are linearly independent, used in the delivery phases.","marker":"[34]"}],"fun_headline_variants":["Private coded caching: hide demands at constant-factor cost","Virtual and MDS caches make demands private, nearly free","Order-optimal private caching via symmetric multicast","Coded caching with zero information leak on user requests","Two schemes for demand-private caching with small overhead"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The virtual-user scheme's privacy proof assumes that equalizing how often each file subset is demanded makes the whole transmission look the same to each user no matter what the others request, an assumption that fails in the smallest nontrivial example, where a multicast message name reveals the other user's file.","fun_headline_variants_meta":{"raw":{"variants":["Private coded caching: hide demands at constant-factor cost","Virtual and MDS caches make demands private, nearly free","Order-optimal private caching via symmetric multicast","Coded caching with zero information leak on user requests","Two schemes for demand-private caching with small overhead"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000762,"raw_usage":{"total_tokens":3492,"prompt_tokens":1166,"completion_tokens":2326,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":782,"completion_tokens_details":{"reasoning_tokens":2251}},"tokens_in":782,"tokens_out":2326,"duration_ms":17376,"temperature":1.0,"reasoning_tokens":2251,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:37:36.330689+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the virtual-user scheme with $K=2$, $N=3$, $L=1$, and $t=1$: fix user 1's demand and cache, and compute the conditional distribution of the transmitted message set $X$ when user 2 demands file 1 versus file 2; the message $X_{\\{1,2\\}}$ contains a subfile whose name includes the other user's demand, so the two conditional distributions differ and $I(D_{\\setminus\\{1\\}};X|Z_1,d_1)>0$, contradicting the claimed privacy constraint.","supporting_citations":[{"cited_title":"Fundamental limits of caching,","cited_arxiv_id":null,"evidence_quote":"Supplies the MAN coded caching scheme that both proposed private schemes build on."},{"cited_title":"A content-delivery protocol, exploiting the privacy benefits of coded caching,","cited_arxiv_id":null,"evidence_quote":"Introduces the virtual-user idea that the virtual-user scheme adapts to information-theoretic privacy."},{"cited_title":"Characterizing the rate-memory tradeoff in cache networks within a factor of 2,","cited_arxiv_id":null,"evidence_quote":"Provides the factor-2 converse bound used in Theorem 3 for $N>K$, $M\\ge N/K$."},{"cited_title":"Improved lower bounds for coded caching,","cited_arxiv_id":null,"evidence_quote":"Provides the factor-4 converse bound used in Theorem 3 for $N\\le K$."},{"cited_title":"Improved approximation of storage-rate tradeoff for caching with multiple demands,","cited_arxiv_id":null,"evidence_quote":"Provides the factor-11 converse bound for multiple requests used in Theorem 3 when $L>1$."},{"cited_title":"On the Fundamental Limits of Fog-RAN Cache-aided Networks with Downlink and Sidelink Communications","cited_arxiv_id":"1811.05498","evidence_quote":"Gives the converse $R\\ge L(1-M/N)$ used for Theorem 5 and Theorem 6."},{"cited_title":"On caching with more users than files,","cited_arxiv_id":null,"evidence_quote":"Supplies the MDS parity-check matrices whose any $L$ columns are linearly independent, used in the delivery phases."}],"review_version":1}