{'fraction_non_alphanumeric': 0.04772747973403771, 'fraction_numerical': 0.011248747609071864, 'mean_word_length': 3.8950066874721356, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Fundamental Limits of Secretive Coded Caching

Recent work by Maddah-Ali and Niesen introduced coded caching which demonstrated the benefits of joint design of storage and transmission policies in content delivery networks. They studied a setup where a server communicates with a set of users, each equipped with a local cache, over a shared error-free link and proposed an order-optimal caching and delivery scheme. In this paper, we introduce the problem of secretive coded caching where we impose the additional constraint that a user should not be able to learn anything, from either the content stored in its cache or the server transmissions, about a file it did not request. We propose a feasible scheme for this setting and demonstrate its order-optimality with respect to information-theoretic lower bounds.


I. INTRODUCTION
Broadband data consumption has grown at a rapid pace over last couple of decades, owing in great part to multimedia applications such as Video-on-Demand [1]. Content delivery networks attempt to mitigate this extra load on the communication network by deploying storage units or caches where some of the popular content can be pre-fetched during the off-peak hours.
Content caching and delivery has been studied extensively in the literature, see for example [16], [3], [2] and references therein. However, most of the work proposes caching schemes where those parts of the requested files that are available at nearby caches are served locally and the remaining parts are served by a remote server via separate unicast transmissions to the users. In contrast, recent work [8], [9] has studied an information-theoretic formulation of the problem and proposed the idea of coded caching which uses the available cache memory to not only provide local access to content but to also generate coded-multicasting opportunities among users with different demands. The setup studied in [8], [9] consists of a server communicating to a set of users, each equipped with a cache of uniform size, over a broadcast link and the objective is to minimize the worst-case server transmission rate, over all feasible user demands. For this setup, coded caching is shown to provide significant benefits over traditional caching and delivery, and is in fact within a constant factor of the optimal. In this work, we consider a similar problem setup where we have the additional constraint that no user should be able to obtain any information, from its cache content as well as the server transmission, about any file other than the one it has requested. We call this setup 'secretive' and devise a secretive coded caching scheme for the setup based on ideas from secret sharing [4], [13], and show that the performance of this scheme is within a constant factor of the optimal for almost all parameter values of interest.
The results of [8], [9] on coded caching have been extended in several other directions as well, ranging from heterogeneous cache sizes [15], unequal file sizes [17], to improved converse arguments [5], [12]. Content caching and delivery has also been studied in the context of device-to-device networks, multi-server topologies, and heterogeneous wireless networks in [7], [14], and [6] respectively. The work closest to ours is [11], which considers the problem of secure coded caching, where the goal is to protect information about the files from an eavesdropper which can listen to the server transmissions. However, [11] doesn't capture the notion of 'secrecy' that we consider here. Throughout the paper by 'security', 'secure' we mean protection against an eavesdropper and 'secretive', 'secrecy' refer to our problem of interest. While most of the work in this paper focuses on secretive coded caching, we will also briefly discuss the case where one requires both secrecy and security.
The rest of the paper is organized as follows. We describe the problem setup in Section II and present our main results in Section III. We discuss some examples in Section IV-C before describing our proposed secretive coded caching scheme in Section V and presenting converse arguments in Section VI. Order-optimality of the proposed scheme is established in Section VII and we conclude with a discussion of our results in Section VIII.

II. PROBLEM FORMULATION
Notation: For n ∈ N, we denote by [n] the set {1, 2, . . . , n}. A vector of random variables will be denoted by bold-faced upper case letters, e.g., Y = (Y 1 , Y 2 , . . . , Y n ). For a set A ⊆ [n], we will denote the vector of random variables indexed by We consider a single-hop content delivery network, as illustrated in Figure 1. The system consists of a server hosting a collection of N files, W = (W 1 , W 2 , . . . , W N ), each of size F bits. We will assume that W 1 , W 2 , . . . , W N are independent random variables each distributed uniformly over [2 F ]. The server is connected via a shared, error-free link to K users, each with a cache memory of size M F bits. We will refer to M as the normalized cache memory size.
The system works in two phases: a placement phase followed by a delivery phase. In the placement phase, the user caches are populated with content related to the N files using a possibly randomized scheme. Formally, we denote the content stored in cache k by a random variable Z k which takes Each user k generates an estimate W d k of its requested file W d k using only its stored cache content Z k and the server transmission X d (W, Z). The probability of error of a placement and delivery scheme is given by where the probability is over the files and the randomization in the placement phase, i.e., over the distribution p W p Z|W . In addition to recovering the demanded files, we also want each user to not obtain any information about the other files. The information leakage of a placement and delivery scheme is defined as: A placement and delivery scheme is said to be an ( , δ)secretive scheme if its probability of error P e ≤ and information leakage L ≤ δ.
The memory-rate pair (M, R) is said to be secretively achievable, if for any , δ > 0 and large enough file size F , there exists an ( , δ)-secretive scheme. The object of interest in this paper is the optimal server transmission rate R S (M ) for normalized cache memory size M , given by

III. MAIN RESULTS
The main result of this paper is an approximate characterization of the optimal server transmission rate R S (M ) for any normalized cache memory size M . We propose a secretive caching and delivery scheme to show the following upper bound on R S (M ).
For M = N (K−1), we achieve the rate R C (M ) = 1. Further, for any general 1 ≤ M ≤ N (K − 1), the convex envelope of these points is achievable.
Some comments are in order. Note that the achievable rate R C (M ) = 1 for M = N (K − 1). This is in fact the minimum achievable rate for any secretive caching and delivery scheme, i.e. R S (M ) ≥ 1, ∀ M . Intuitively, this is because the information leakage as defined in (2) is constrained to be negligible for any secretive scheme, and this implies that the contents of a cache cannot provide any information about the requested file on its own. Hence, for a user to learn the file it requested, it must receive from the server at least F bits. We provide a formal proof in Section VI. Similarly, note that we only consider M ≥ 1 in the above result. As we prove in Section VI, this is indeed a necessary condition for the existence of a secretive caching and delivery scheme.
The next result provides an information-theoretic lower bound on the server transmission rate of any secretive caching and delivery scheme.
The above result is obtained using cut-set based arguments and is presented in section VI. The lower bound can be further improved by using non-cut set based arguments as shown in Section VIII. However, the cut-set lower bound is indeed tight for the case with N = K = 2, as shown in Section IV. This lower bound also suffices to show that, in general, the server transmission rate of the proposed scheme is within a constant factor of the optimal for most regimes of interest: where c 1 is a constant independent of all the system parameters.
It is easy to verify that M 0 = 1 for N ≥ K. Recall that M ≥ 1 is necessary for any secretive caching and delivery scheme and thus our proposed scheme is order-optimal for all permissible values of the normalised cache memory size M . For N < K, we have M 0 ≤ 1+N/(N −1) < 5/2 and thus the above result establishes the order-optimality of our proposed scheme for all regimes of interest except for 1 ≤ M ≤ 5/2. This is because for N < K, the lower bound from theorem 5 depends only the number of files N . However, we expect the optimal rate to increase with the number of users K, since we have to ensure secrecy for a larger set of users.
IV. EXAMPLES A. Optimal Scheme for N = K = 2 and M = 1 Figure 2 shows an example setup with N = 2 files and K = 2 users with normalized cache memory size M = 1. Partition the two files W 1 , W 2 into two equal parts W 1 1 , W 2 1 and W 1 2 , W 2 2 respectively. Two independent and uniformly distributed random keys, T 1 and T 2 each of size F/2 bits, are generated. During the placement phase, the random keys and their combination with the file parts are put in the caches as shown in Figure 2. During the delivery phase, if the demand vector is (d 1 , d 2 ) = (1, 2), the server transmits W 2 1 ⊕ T 1 and W 1 2 ⊕ T 2 , of total size F bits. It can be easily verified that both the users can recover their requested files using their respective cache contents and the server transmission. Furthermore, neither user can derive any information about the file they did not request. Similarly, any other demand vector can also be secretively satisfied using a server transmission of size F bits. Specifically, note that when the users demand the same file, the server may send it in the clear. Thus, the memory-rate pair (M = 1, R = 1) is secretively achievable. As mentioned before, M ≥ 1, R ≥ 1 are necessary conditions for feasibility in our setup and so the scheme presented above is in fact optimal.
While the scheme described above is optimal, it is not immediately clear how to generalize it to larger number of files and caches. Instead, below we discuss a sub-optimal scheme at two different memory-rate points. This scheme easily generalizes to our order-optimal scheme.

B. General Scheme for M = 1
At M = 1, we cache independent keys T i of size F bits at each user i ∈ [K], see Figure 3 for an illustration when N = K = 2. During delivery, the server transmits W di ⊕T i for each user i ∈ [K], resulting in a rate of K. It is easy to verify that each user is able to recover its requested file and obtains no information about the other files. Finally, note that the rate Shown is the server transmission for demand vector (d 1 , d 2 ) = (1, 2). of this scheme matches the value of R C (1) (corresponding to M = 1) in (4).
At the other extreme when M = N (K −1), we use a secret sharing scheme as defined below: Definition For m < n, by an (m, n) secret sharing scheme, we mean a "scheme" p S1,...,Sn|W to generate n equal-sized shares S 1 , . . . , S n of a uniformly distributed secret W such that any m shares do not reveal any information about the secret and access to all the n shares completely reveals the secret. i.e., It is easy to see that, for such a scheme, the shares must have a size of at least log |W| n−m bits, where W is the alphabet of the secret. When |W| is large enough, secret sharing schemes which achieve this bound exist [4].
For each file W i , i ∈ [N ], we use a (K − 1, K) secret sharing scheme, which provides K shares, each of size F bits and denoted by {S j i } K j=1 , with the following properties: (i) No collection of K − 1 shares reveals any information about the file W i , and (ii) the file W i can be recovered from its K shares {S j i } K j=1 . Figure 4 illustrates the case of N = K = 2, where the K = 2 shares for each file W i are given by S 1  bits, and this agrees with the normalized cache memory size M = N (K − 1). Next, during the delivery phase, each user requests a file and the server transmits ⊕ k∈[K] S k d k of size F bits, resulting in a rate of 1. See Figure 5 for an illustration when N = K = 3. Since each user k ∈ [K] already has all the shares {S j i } i∈[N ],j =k , the missing share of the demanded file S k d k can be obtained, and the file W d k can be reconstructed. Furthermore for any other file than the one requested, each user k ∈ [K] only has (K − 1) shares which do not reveal any information because of the properties of the (K − 1, K) secret sharing scheme. Again, note that the rate of the proposed scheme agrees with the value of R C (M = N (K − 1)) in (4).

V. GENERAL ACHIEVABILITY SCHEME
In this section, we will generalize the ideas presented above to obtain a secretive caching and delivery scheme for all problem parameters N, K, and M , and characterize its rate to complete the proof of Theorem 1. In fact, we will propose an ( = 0, δ = 0)-secretive scheme, i.e. the probability of error as well as the information leakage are both zero.
We have already discussed the schemes which achieve R C (M ) as defined in (4) at M = 1 and M = N (K −1). Next, we consider M = N t/(K −t)+1 for some t ∈ {1, ..., K −2}. We use a ( K−1 t−1 , K t ) secret sharing scheme to create K t shares, each of size Then for any k ∈ [K], the shares satisfy the following properties: The identities (7), (8) imply that K−1 t−1 shares of a file reveal no information about it and shares of one file do not provide information about another file since they are independent; and (9) implies that K t shares of a file are sufficient for recovering it without error. During the placement phase, share S L i is t−1 shares of each of the N files in every user cache, the total memory size in bits needed for storing the shares is given by (10) In addition to the shares, for each subset V ⊂ [K] of users of size |V | = t + 1, an independently and uniformly generated key T V of size F s bits is cached at each user k ∈ V . For each user, the cache memory in bits needed to store the keys is given by Combining (10) and (11), the total memory needed per cache is given by ( N t K−t +1)F bits which agrees with M = N t/(K − t) + 1. See Figure 6 for an illustration of the placement phase when N = K = 3 and t = 1.
During the delivery phase, the demand vector (d 1 , ..., d K ) is revealed to the server and the users. Then for each V ⊂ [K] such that |V | = t + 1, the server transmits T V ⊕ k∈V S V \{k} d k on the shared link to the users. See Figure 6 for an example. Consider one such subset V and its associated server transmission. From the placement phase, each k ∈ V has the key T V as well as all the shares in the message except S V \{k} d k , and hence each user k can recover the share S V \{k} d k . It is easy to verify that at the end of the delivery phase, each user k would possess all the K t shares of its requested file W d k and thus, from (9), can recover it without error. Furthermore, the scheme ensures that the server transmissions do not reveal any information to a user about files it did not request. This combined with (7), (8) ensures that the information leakage, as defined in (2), of the placement and delivery phases of the proposed scheme is zero. Thus, we have a secretive caching and delivery scheme. Finally, the server transmission size in bits of our proposed scheme at M = N t/(K − t) + 1 is given by Substituting t = (M − 1)K/(N + M − 1), we obtain the achievable rate expression R C (M ) as defined in Theorem 1.

VI. A LOWER BOUND
In this section, we provide a lower bound on the optimal server transmission rate R S (M ), as defined in (3). Our proof is along similar lines as [8], [11].
Consider a tuple (M, R) which is secretively achievable. Fix s ∈ [min{N/2, K}] and consider users 1, 2 . . . , s. Suppose user i requests file i. Since the tuple (M, R) is secretively achievable, for any > 0, there exists a secretive placement and delivery scheme such that each user i can recover its requested file with a server transmission of rate R along with its cache content Z i with probability of error at most . Furthermore for any δ > 0, the information leakage to any user about a file other than the one it had requested is at most δ. Next, consider another scenario where each user i ∈ [s] requests file s + i. Again, since the tuple (R, M ) is secretively achievable, the recovery and secrecy conditions still hold true.
One can repeat the same argument for N/s different request patterns. Let X l denote the server transmission corresponding to the l th request instance when the demand pattern is given by (d 1 = (l − 1)s + 1, d 2 = (l − 1)s + 2, . . . , ls).
In words, W denotes the vector of all files except the one requested by the user k in the l th request instance, X denotes the vector of server transmissions in all the request instances except the l th one, and Z refers to the contents of all the user caches except the k th one.
Then, from the recovery and secrecy conditions, for (M, R) to be secretively achievable, for l ∈ [ N/s ], k ∈ [s], we have using Fano's inequality in (1) and using (2) Where for any x ∈ [0, 1], H b (x) is the binary entropy function.
Then, we have where (a), (b) follow from (12), (13) respectively. Rearranging the terms, we get The statement of Theorem 2 then follows by noting that the above inequality holds true for any s ∈ {1, 2, ..., min{N/2, K}} and by choosing , δ to be arbitrarily small.

VII. ORDER-OPTIMALITY
In this section, we show that the achievable rate R C (M ) is within a constant factor with the above information theoretic lower bound. In particular, we prove that for M ≥ 1 + max{ N (K−N ) Also, the achievable rate expression R C (M ) may be written as .
For values of M in our range of interest, if K ≤ N , On the other hand, if K > N , Thus, we have R C (M ) ≤ min{N, K}.  (16/15).

This gives
Region II: max{N, K}/(K − 1) ≤ M S < N/15. In this region, note that and that Now, (14) and following steps similar to the one used to get (15) we have Using (16) and (17) in the above inequality, we get Hence, Using R * S (M ) ≥ 1 with the above inequality, we get This proves Theorem 3.

VIII. DISCUSSION
As mentioned before, the work closest to ours is [11], which studied the optimal server transmission rates needed to keep the files secure from an eavesdropper listening to the transmissions on the shared link. In contrast, we imposed the secrecy requirement that users should not be able to learn about files they did not request. An obvious scenario of interest is when both the conditions, security against an eavesdropper and secrecy from users, have to be satisfied. Let R SE (M ) denote the optimal server transmission rate in such a setup, as a function of the normalized cache size M .
As an example, recall the setup in Figure 2 with N = K = 2 and M = 1 for which the minimum rate for a secretive scheme is given by R S (M = 1) = 1. Under the optimal scheme illustrated in Figure 2, when both users request say file W 1 , the server simply transmits W 1 on the shared link. While this sufficed for satisfying the user secrecy constraints, clearly it will not work in the presence of an eavesdropper. In fact, the memory-rate tuple (M = 1, R = 1) is not feasible if we insist on both secrecy from users and security against  Fig. 7. The plot shows the achievable rates for a setup with N = 15 files and K = 10 users under various conditions. The dashed red line is the achievable rate with no security obtained in [8]. The dash-dot black line is the achievable rate with only eavesdropper security achieved in [11]. The solid blue line is our achievable rate R C (M ) with eavesdropper security and secrecy against users. the eavesdropper. The optimal server transmission rate in this scenario is given by While the optimal scheme in the above example did not protect against eavesdroppers, the general achievability scheme proposed in Section V does in fact have this additional property since each server transmission to a subset V of users is protected using a key 3 T V . Thus, an eavesdropper who has access to these transmissions can obtain no information about the files. This implies that the rate function R C (M ) as defined in (4) is in fact achievable for the setup with both security and secrecy constraints, i.e. R SE (M ) ≤ R C (M ). Furthermore, it is easy to see that the lower bounds in Theorem 2 and the order-optimality result in Theorem 3 also continue to hold. Thus, the transmission rate for our proposed scheme is still within a constant factor of the optimal when both security and secrecy conditions are imposed. Figure 7 plots the order-optimal transmission rates under various constraints. Note that when either no constraint or only the security against eavesdropper constraint is imposed, the achievable rate is zero at M = N . On the other hand, once the user secrecy condition is activated, the minimum achievable rate for any value of M is one. Furthermore, as the figure illustrates, the gap between the rate with no security and the rate with security against an eavesdropper is not very large. This was in fact shown to be at most a constant factor in [11]. The same continues to hold for a large memory regime, 1 < M < N K−1 2K , when a further user secrecy constraint is also added. 3 Strictly speaking, this is not true for the scheme at the extreme memory point M = N (K − 1) since we don't use a key to protect the server transmission. However, this can be easily fixed without affecting orderoptimality by additionally storing a common key in each cache and securing the server transmission with this key.

APPENDIX A
Here we prove the claim made in section VIII, that for case where N = K = 2 with eavesdropper security and secrecy constraints, the optimal transmission rate is given by R SE (M ) = 3 − M .