REVIEW 2 major objections 2 minor 34 references
On Coded Caching with Private Demands
T0 review · 2 major / 2 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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)$.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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).
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 (2)
- [Section IV-A, Eq. (22) and Privacy paragraph] 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.
- [Appendix C and Eq. (42)] 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.
minor comments (2)
- [Appendix A-A, Eq. (46)] 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 IV-A, Eq. (22)] 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.
Circularity Check
No significant circularity found: the constructions are self-contained and the order-optimality comparisons use external non-private converse bounds.
full rationale
The paper's central derivations are not circular. The virtual-user scheme (Theorem 2) is an explicit construction: it defines U = binom(N,L) K effective users, assigns each demand vector to exactly K effective users, and then runs a MAN-style delivery over these U users. The load expression follows directly from counting multicast messages, and the privacy claim rests on a symmetry argument about the composition of the transmitted messages. Whether that symmetry argument is correct is a separate correctness question, not a circularity issue: the privacy constraint (11) is not inserted into the construction as an assumption; it is asserted as a consequence of the construction. Similarly, the MDS-based scheme (Theorem 4) is built from an explicit placement and a specified multicast-message formula; the load is again obtained by counting. The order-optimality results (Theorems 3, 5, and 6) are proven by comparing the achievable loads against existing converse bounds for the shared-link caching model without privacy, namely [4], [5], [8], and [33]. One of these, [33], is by the same authors, but it is a lower bound for a different model (no privacy constraint), so it does not restate the paper's target result and is not a fitted parameter or a definitional restatement of the private-demand tradeoff. No parameter is fitted to data and later called a prediction, and no uniqueness theorem from the authors' prior work is invoked to force the chosen scheme. The only notable vulnerability in the paper is a possible flaw in the virtual-user privacy argument, where multicast message metadata may reveal demand information to real users; that is a correctness concern, not a form of circular derivation, and it does not make the paper's claims equivalent to its inputs by construction.
Assumptions & free parameters
assumptions (4)
- domain assumption Placement metadata M(Ck) of each user's cache is known only to that user, and random permutations p_i assigning file pieces to cache labels are unknown to other users.
- domain assumption Files, demands, cache metadata, and transmission types are mutually independent, as assumed in equation (6).
- standard math An MDS code over a sufficiently large finite field exists such that any L columns of the matrix G are linearly independent, and file length B is large enough for the required sub-packetization.
- domain assumption The non-private converse bounds in [4], [5], [8], and [33] are valid lower bounds for the private problem.
invented entities (1)
-
Virtual effective users
Cite this review
Pith. "Pith review of On Coded Caching with Private Demands." pith.science (2026). https://pith.science/paper/KZ4RMTTO
@misc{pith2026190810821,
author = {Pith},
title = {Pith review of: On Coded Caching with Private Demands},
year = {2026},
howpublished = {\url{https://pith.science/paper/KZ4RMTTO}},
note = {Machine review of arXiv:1908.10821}
}
read the original abstract
Caching is an efficient way to reduce network traffic congestion during peak hours by storing some content at the user's local cache memory without knowledge of later demands. For the shared-link caching model, Maddah-Ali and Niesen (MAN) proposed a two-phase (placement and delivery) coded caching strategy, which is order optimal within a constant factor. However, in the MAN coded caching scheme, each user can obtain the information about the demands of other users, i.e., the MAN coded caching scheme is inherently prone to tampering and spying the activity/demands of other users. In this paper, we formulate an information-theoretic shared-link caching model with private demands, where there are K cache-aided users (which can cache up to M files) connected to a central server with access to N files. Each user requests L files. Our objective is to design a two-phase private caching scheme with minimum load while preserving the information-theoretic privacy of the demands of each user with respect to other users. We propose two novel private coded caching schemes with the general underlying idea, which is to satisfy the users' requests by generating a set of coded multicast messages that is symmetric with respect to the library files. In the first scheme, we introduce a number of virtual users such that each L-subset of files is demanded by K real or virtual (effective) users and use the MAN delivery to generate multicast messages. This scheme incurs in an extremely large sub-packetization. Then, we propose a second scheme based on a novel MDS-coded cache placement. In this case, we generate multicast messages where each multicast message contains one MDS-coded symbol from each file in the library and thus is again symmetric over all the files from the viewpoint of each user. The proposed schemes are generally order optimal except for the case where N > LK and M< N/K.
Figures
Reference graph
Works this paper leans on
-
[1]
Living on the edge: The role of proactive caching in 5g wireless networks,
E. Bastug, M. Bennis, and M. Debbah, “Living on the edge: The role of proactive caching in 5g wireless networks,” IEEE Communications Magazine, vol. 52, pp. 82–89, Aug. 2014
work page 2014
-
[2]
Fundamental limits of caching,
M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” IEEE Trans. Infor. Theory, vol. 60, no. 5, pp. 2856– 2867, May 2014
work page 2014
-
[3]
On the optimality of uncoded cache placement,
K. Wan, D. Tuninetti, and P. Piantanida, “On the optimality of uncoded cache placement,” in IEEE Infor. Theory Workshop, Sep. 2016
work page 2016
-
[4]
Characterizing the rate-memory tradeoff in cache networks within a factor of 2,
Q. Yu, M. A. Maddah-Ali, and S. Avestimehr, “Characterizing the rate-memory tradeoff in cache networks within a factor of 2,” in IEEE Int. Symp. Inf. Theory , Jun. 2017
work page 2017
-
[5]
Improved lower bounds for coded caching,
H. Ghasemi and A. Ramamoorthy, “Improved lower bounds for coded caching,” IEEE Trans. Infor. Theory, vol. 63, no. 7, pp. 4388–4413, May 2017
work page 2017
-
[6]
The exact rate-memory tradeoff for caching with uncoded prefetching,
Q. Yu, M. A. Maddah-Ali, and S. Avestimehr, “The exact rate-memory tradeoff for caching with uncoded prefetching,” IEEE Trans. Infor. Theory, vol. 64, pp. 1281 – 1296, Feb. 2018. 34
work page 2018
-
[7]
Caching-aided coded multicasting with multiple random requests,
M. Ji, A. Tulino, J. Llorca, and G. Caire, “Caching-aided coded multicasting with multiple random requests,” in Proc. IEEE Inf. Theory Workshop (ITW) , May. 2015
work page 2015
-
[8]
Improved approximation of storage-rate tradeoff for caching with multiple demands,
A. Sengupta and R. Tandon, “Improved approximation of storage-rate tradeoff for caching with multiple demands,” IEEE Trans. Commun., vol. 65, no. 5, pp. 1940–1955, May. 2017
work page 1940
Show all 34 references
-
[9]
Decentralized coded caching attains order-optimal memory-rate tradeoff,
M. A. Maddah-Ali and U. Niesen, “Decentralized coded caching attains order-optimal memory-rate tradeoff,” IEEE/ACM Trans. Networking, vol. 23, no. 4, pp. 1029–1040, Aug. 2015
2015
-
[10]
Fundamental limits of caching in wireless d2d networks,
M. Ji, G. Caire, and A. Molisch, “Fundamental limits of caching in wireless d2d networks,” IEEE Trans. Inf. Theory , vol. 62, no. 1, pp. 849–869, 2016
2016
-
[11]
Multi-server coded caching,
S. P. Shariatpanahi, S. A. Motahari, and B. H. Khalaj, “Multi-server coded caching,” IEEE Trans. Infor. Theory , vol. 62, pp. 7253 – 7271, Dec. 2016
2016
-
[12]
Caching in combination networks,
M. Ji, A. M. Tulino, J. Llorca, and G. Caire, “Caching in combination networks,” 49th Asilomar Conf. on Sig., Sys. and Comp.,, Nov. 2015
2015
-
[13]
Caching in combination networks: Novel multicast message generation and delivery by leveraging the network topology,
K. Wan, M. Ji, P. Piantanida, and D. Tuninetti, “Caching in combination networks: Novel multicast message generation and delivery by leveraging the network topology,” in IEEE Intern. Conf. Commun (ICC 2018) , May 2018
2018
-
[14]
Fundamental limits of caching with secure delivery,
A. Sengupta, R. Tandon, and T. C. Clancy, “Fundamental limits of caching with secure delivery,”IEEE Trans. on Information Forensics and Security, vol. 10, no. 2, pp. 355–370, 2015
2015
-
[15]
Towards the exact rate-memory trade-off for uncoded caching with secure delivery,
M. Bahrami, M. A. Attia, R. Tandon, and B. Vasic, “Towards the exact rate-memory trade-off for uncoded caching with secure delivery,” in 55th Annual Allerton Conf. on Commun., Control, and Computing (Allerton) , Oct. 2017
2017
-
[16]
Private coded caching,
V . Ravindrakumar, P. Panda, N. Karamchandani, and V . M. Prabhakaran, “Private coded caching,” IEEE Trans. on Information Forensics and Security , vol. 13, no. 3, pp. 685–694, 2018
2018
-
[17]
How to share a secret,
A. Shamir, “How to share a secret,” Commun. ACM, vol. 22, no. 11, pp. 612–613, 1979
1979
-
[18]
Device-to-device secure coded caching,
A. A. Zewail and A. Yener, “Device-to-device secure coded caching,” arXiv:1809.06844, Sep. 2018
2018 arXiv
-
[19]
Bounds on caching d2d networks with secure delivery,
Z. H. A. . R. Mathar, “Bounds on caching d2d networks with secure delivery,” in 15th Int. Symp. Wireless Commun. Sys. (ISWCS), Aug. 2018
2018
-
[20]
Combination networks with or without secrecy constraints: The impact of caching relays,
A. A. Zewail and A. Yener, “Combination networks with or without secrecy constraints: The impact of caching relays,” in IEEE Journal on Selected Areas in Communications , vol. 36, no. 6, pp. 1140–1152, 2018
2018
-
[21]
Secrecy capacity-memory tradeoff of erasure broadcast channels,
S. Kamel, M. Sarkiss, M. Wigger, and G. R. Othman, “Secrecy capacity-memory tradeoff of erasure broadcast channels,” IEEE Trans. Inf. Theory , vol. 65, no. 8, pp. 5094–5124, 2019
2019
-
[22]
A content-delivery protocol, exploiting the privacy benefits of coded caching,
F. Engelmann and P. Elia, “A content-delivery protocol, exploiting the privacy benefits of coded caching,” 2017 15th Intern. Symp. on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt) , May 2017
2017
-
[23]
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 , pp. 41–50, 1995
1995
-
[24]
The capacity of private information retrieval,
H. Sun and S. A. Jafar, “The capacity of private information retrieval,” IEEE Trans. Inf. Theory , vol. 63, no. 7, pp. 4075–4088, 2017
2017
-
[25]
The capacity of private information retrieval with private side information,
Z. Chen, Z. Wang, and S. Jafar, “The capacity of private information retrieval with private side information,” available at arXiv:1709.03022, Sep. 2017
2017 arXiv
-
[26]
Single-server multi-user private information retrieval with side information,
S. Li and M. Gastpar, “Single-server multi-user private information retrieval with side information,” in IEEE Int. Symp. Inf. Theory, Jun. 2018
2018
-
[27]
The capacity of cache aided private information retrieval,
R. Tandon, “The capacity of cache aided private information retrieval,” in 55th Allerton Conf. Commun., Control, Comp. , Oct. 2017
2017
-
[28]
Cache-aided private information retrieval with partially known uncoded prefetching: Fundamental limits,
Y .-P. Wei, K. Banawan, and S. Ulukus, “Cache-aided private information retrieval with partially known uncoded prefetching: Fundamental limits,” available at arXiv:1712.07021 , Dec. 2017. 35
2017 arXiv
-
[29]
Fundamental limits of cache-aided private information retrieval with unknown and uncoded prefetching,
——, “Fundamental limits of cache-aided private information retrieval with unknown and uncoded prefetching,” available at arXiv:1709.01056, Sep. 2017
2017 arXiv
-
[30]
The capacity of private information retrieval from uncoded storage constrained databases,
M. A. Attia, D. Kumar, and R. Tandon, “The capacity of private information retrieval from uncoded storage constrained databases,” available at arXiv:1805.04104 , May 2018
2018 arXiv
-
[31]
The capacity of private computation,
H. Sun and S. A. Jafar, “The capacity of private computation,” IEEE Trans. Inf. Theory , vol. 65, no. 5, pp. 3880–3897, Jun. 2019
2019
-
[32]
A. E. Gamal and Y .-H. Kim, Network Information Theory . Cambridge, UK: Cambridge University Press, 2011
2011
-
[33]
Novel inter-file coded placement and d2d delivery for a cache-aided fog-ran architecture,
K. Wan, D. Tuninetti, M. Ji, and G. Caire, “Novel inter-file coded placement and d2d delivery for a cache-aided fog-ran architecture,” arXiv:1811.05498, Nov. 2018
2018 arXiv
-
[34]
On caching with more users than files,
K. Wan, D. Tuninetti, and P. Piantanida, “On caching with more users than files,” in IEEE Int. Symp. Inf. Theory , Jul. 2016
2016
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.