{'fraction_non_alphanumeric': 0.056001323517247084, 'fraction_numerical': 0.016709405244437092, 'mean_word_length': 3.5525324797589906, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 42, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Fundamental Limits of Caching with Secure Delivery

Caching is emerging as a vital tool for alleviating the severe capacity crunch in modern content-centric wireless networks. The main idea behind caching is to store parts of popular content in end-users' memory and leverage the locally stored content to reduce peak data rates. By jointly designing content placement and delivery mechanisms, recent works have shown order-wise reduction in transmission rates in contrast to traditional methods. In this work, we consider the secure caching problem with the additional goal of minimizing information leakage to an external wiretapper. The fundamental cache memory vs. transmission rate trade-off for the secure caching problem is characterized. Rather surprisingly, these results show that security can be introduced at a negligible cost, particularly for large number of files and users. It is also shown that the rate achieved by the proposed caching scheme with secure delivery is within a constant multiplicative factor from the information-theoretic optimal rate for almost all parameter values of practical interest.


I. INTRODUCTION
Caching is a technique which helps in reducing the peak network load at times of high traffic volume with the aid of local file storage and content duplication. Fractions of popular files are duplicated and stored apriori in users' cache memories distributed across a given network. At times of high demand, the users can be partly served locally from their cache, thereby reducing the network load. Caching generally works in two phases -the storage phase and the delivery phase. The general caching problem has been well studied in literature [1]- [4]. In [1], a file assignment viewpoint, analogous to the caching problem, is investigated through different models for assigning files to storage devices. The delivery phase of the caching system can operate as a series of dedicated unicast transmissions to each user by communicating fractions of requested files which are not stored in their caches. However, this is not a scalable solution as the number of users in the system increases. A more efficient solution would be multicasting to all users while simultaneously satisfying all demands. Thus, an important aspect in caching is multicast delivery. Most of the prior works in this area tend to use a fixed delivery scheme and then optimize the storage phase to suit the delivery scheme [3], [4]. Further, their investigations are mainly based on the gains obtained from local content distribution, ignoring the global cache size as a factor for extracting caching gain.
More recently, [5]- [7] have proposed an information theoretic formulation of the caching problem. In [5], a scheme is proposed which, in addition to the local caching gain, is also capable of offering a global caching gain. The scheme takes the cumulative size of the network cache memory into consideration and jointly designs the cache storage phase and a coded mutlicast delivery phase. This achieves a global caching gain which provides significant improvement over local caching gain. The fundamental concepts presented in [5] are extended in [6], [7] to the more general scenarios of decentralized storage and non-uniform user demands which are modeled by heavy-tailed popularity distributions like the Zipf distribution [8], [9]. Some extensions of the caching problem have also been investigated in the case of Device-to-Device (D2D) communications [9], [10]. The authors in [9] use the interaction of cache memories of the distributed devices to enable efficient frequency reuse.
In this paper, we investigate the fundamental security aspects of the caching problem. To this end, we introduce the secure caching problem in which the multicast communication between the central server and the users (delivery phase) occurs over a public (insecure) channel. The defining feature of this problem is to capture the tradeoff the centralized cache placement as well as the decentralized placement with secure file delivery.
The main contribution of this paper is an approximate characterization of R * s (M ). We design centralized and decentralized caching algorithms which make use of coded multicast delivery to extract global caching gain in the system. The system has uniformly distributed orthogonal keys which are stored and shared among users for secure multicast delivery. We present novel upper and lower bounds on R * s (M ) and show that these bounds are within a constant multiplicative gap. Indeed, for a fixed M , it is intuitively clear that R * s (M ) ≥ R * (M ), i.e., the minimum rate in presence of a wiretapper must be in general larger than in the absence of a wiretapper. From our results, we show, rather surprisingly, that the cost for incorporating security in both the centralized and decentralized caching schemes is negligible when the number of users and files are large. It is also shown that the achievable rates of the centralized and decentralized secure caching schemes are asymptotically equal.

II. SYSTEM MODEL
Let (W 1 , W 2 , . . . , W N ) be N independent random variables each uniformly distributed over for some F ∈ N. Each W n represents a file of size F bits. A (M, R s ) secure caching scheme comprises of K random caching functions, N K random encoding functions and KN K decoding functions. The K random caching functions map the files (W 1 , . . . , W N ) into the cache content: for each user k ∈ [K] during the storage (or placement) phase. The maximum allowable size of the contents of each cache Z k is M F bits. The N K random encoding functions map the files (W 1 , . . . , W N ) to the input X (d1,...,dK ) ψ (d1,...,dK ) W 1 , . . . , W N of the shared link in response to the requests (d 1 , . . . , d K ) ∈ [N ] K during the delivery phase. Finally, the KN K decoding functions map the received signal over the insecure shared link X (d1,...,dK ) and the cache content Z k to the estimateŴ P(Ŵ (d1,...,dK ),k = W dk ).
Definition 1. The pair (M, R s ) is securely achievable if for any ǫ > 0 and every large enough file size F , there exists a (M, R s ) secure caching scheme with P e ≤ ǫ and L ≤ ǫ. We define the secure memory-rate tradeoff Notation: The following notations are used throughout the rest of the paper: R * s (M ) denotes the rate achieved by the optimal secure caching scheme as a function of the cache memory size M , R C s (M ) denotes the rate achieved by the centralized caching scheme with secure delivery and R D s (M ) denotes the rate of the decentralized caching scheme with secure delivery as proposed in this paper. The symbol ⊕ denotes the bit-wise XOR operation.

III. CENTRALIZED CACHING WITH SECURE DELIVERY
The first result gives an achievable rate which upper bounds the optimal memory-rate trade-off R * s (M ) for the centralized caching scheme with secure delivery. We first consider the case where K ≤ N i.e., the number of files is at least as large as the number of users. Security is incorporated by introducing randomness in the storage and delivery phase of the achievable scheme in form of a set of uniformly distributed orthogonal keys (independent of the data) stored in the cache of each user. The total cache memory (of size M F bits) is divided into two partsdata memory (of size M D F bits) and key memory (of size M K F bits) such that M = M D + M K . The server uses the keys stored at the users' caches to encode the delivery signal X (d1,...,dK ) such that the transmission is secure from a wiretapper. Theorem 1. For N files and K ≤ N users, each with a cache size of M ∈ (N −1) is securely achievable. For any 1 ≤ M ≤ N , the lower convex envelope of these points is achievable.
The proof of Theorem 1 is presented in Appendix A. The centralized caching scheme achieving the rate in Theorem 1 is given in Algorithm 1 in Appendix A. Similar to [5], the achievable rate in (8) consists of three factors. The first factor is K. In case of no data caching, this is worst case rate. In order to make the delivery phase secure, however, each user has to store a unique key (of the same size as a single file). During delivery, the server encodes the user's requested file with its key and transmits it. Thus even with no data storage in cache, the cache memory size has to be at least F bits to store a key. Thus in the secure problem, M = 0 is infeasible and the worst case rate of K is achieved at M = 1. Thus in this case M D = 0, M K = 1 and the (M, R C s ) pair (1, K) is achievable. Another extreme point is M = N i.e., the case where all files are stored in the user's cache and no multicasting is required. In this case M D = N, M K = 0 and the (M, R C s ) pair (N, 0) is achievable. We refer to a scheme which achieves points on the line joining (1, K) and (N, 0) as the conventional secure scheme. This scheme naively stores files and keys in the cache and ignores the global caching gain for 1 < M < N .
The second factor in (8) This is the secure local caching gain and is relevant whenever M is of the order of N . The third factor in (8) which is the secure global caching gain. It is a multicasting gain available to all users for all possible demands. The scheme in Theorem 1 designs the placement of data content and keys in the users' cache such that coded secure multicasting can be achieved among users for every possible request (d 1 , . . . , d K ). The intelligent placement of keys in the caches of the users and encoding the transmissions during delivery phase introduce security in the system. We next consider at the case where K > N i.e., the number of users is larger than the number of files in the system. Theorem 2. For N files and K > N users, each with a cache size of M ∈ (N −1) K · {0, 1, 2, . . . , K} + 1, is securely achievable. For any 1 ≤ M ≤ N , the lower convex envelope of these points is achievable.
The proof of Theorem 2 is presented in Appendix B. In this regime, the rate is given by the minimum of the rate in Theorem 2 and the rate achieved by the conventional secure scheme. Comparing Theorem 1 to (Th.1, [5]), we can observe that the terms M N in (Th.1, [5]) have been replaced by M −1 N −1 . However, the combination of the global and local gains leads to the rate in (8) being higher than the rate in (Th.1, [5]) for a given value of M, N . This is a cost paid for the security in the system. Next, we characterize the lower bound on R * s (M ) by the following theorem.
Theorem 3. For any N ∈ N files and K ∈ K users, each having a cache size 1 ≤ M ≤ N , The proof of Theorem 3 is presented in Appendix C. We next present a series of examples to explain the intuition   behind the results and highlight the interesting features.

Example 1.
We first illustrate the achievable scheme in Theorem 1 with a simple example of N = 2 files and K = 2 users. For this case, from Theorem 1 we have M ∈ 2−1 2 {0, 1, 2} + 1 = {1, 3 2 , 2} be the possible cache sizes for each user. Let the two files be W 1 = A and W 2 = B. The bounds in Theorems 1 and 3 are shown in Fig. 2(a) along with the bounds for the non-secure case from [5]. We first start with the upper bound in Theorem 1. Consider the extreme point M = 1. In this case, the cache of both users Z 1 , Z 2 only stores two unique keys K 1 , K 2 and the server transmits both the files A, B over the shared link XOR-ed with a key. Given the worst-case demand , where A 1 , A 2 , B 1 , B 2 are each of size F/2 bits. We also generate a key K 12 ∼ unif{1, . . . , 2 (F/2) }, which is independent of both the files A, B and has the same size as the sub-files i.e., F/2 bits. In the storage phase, the server fills the caches as follows: Z 1 = (A 1 , B 1 , K 12 ) and Z 2 = (A 2 , B 2 , K 12 ) i.e., each user stores one exclusive part of each file and the key. Thus M D = 1/2 + 1/2 = 1 and M K = 1/2. Now, consider the worst case request (d 1 , d 2 ) = (A, B). From the cache storage phase, it is clear that in order to satisfy this request, user 1 requires the file fragment A 2 while user 2 requires the file fragment B 1 . In this case, the server transmits X (A,B) = {A 2 ⊕ B 1 ⊕ K 12 } which is of rate 1/2. User 1 can obtain A 2 by XOR-ing out B 1 , K 12 while user 2 can get B 1 by XOR-ing out A 2 , K 12 from X (A,B) . A wiretapper, on the other hand, would gain no knowledge of either file from the transmission since I X (A,B) ; A, B = 0 which follows from the fact that the key K 12 is uniformly distributed. Thus the (M, R C s ) pair (3/2, 1/2) is securely achievable. This can be seen in the secure upper bound in Fig. 2(a).
Given that the points (1, 2),(3/2, 1/2) and (2, 0) are achievable, the lines joining pairs of these points are also achievable. The points on the lines can be achieved by dividing the cache memory and transmitted signal proportionally between the caching schemes for the two end-points. This can be illustrated as follows. Consider two caching schemes which achieve the memory rate pairs (M 1 , R 1 (M 1 )) and (M 2 , R 2 (M 2 )). For achieving any rate on the line joining the two points, we divide each file, of size F bits, into fragments F = F 1 + F 2 bits where F 1 = αF and F 2 = (1 − α)F bits. The rate achieved by the two schemes are then R 1 (M 1 )F 1 and R 2 (M 2 )F 2 bits. Thus, if these two schemes operate on a shared basis for a cache size M = M 1 + M 2 , the rate achieved by the Central Server User 1 User 2

Insecure Link
Wiretapper composite scheme is: which gives a point on the line joining the two achievable schemes. Thus, this proves the achievability of the secure upper bound in Fig 2(a). The gap between the insecure and secure achievable bounds results from the storage of the key in the users' cache. ✸ In the two user example, it can be seen that there is only a single key K 12 in the system. Thus, if the key is compromised, the security of the entire system fails. The scheme proposed in Theorem 1 for general values of (N, K), however is more robust in its key management when the number of files and users increase. For larger number of users, the system is able to avoid a single point of failure by operating at an appropriate point on secure memory-rate tradeoff. We next illustrate this point through an example.

Example 2.
We consider the case for N = K = 3. For this case, from Theorem 1, M ∈ {1, 5 3 , 7 3 , 3}. Let there be three files A, B, C. The end points M = 1 and M = 3 are trivial. We consider the case of M = 5/3. The system and bounds for this case is illustrated in Fig. 3(b) and 3(a). Each file is split into 3 equal parts i.e., . We also have 3 keys in the system, K 12 , K 13 , K 23 . In this case each subfile and each key is of size F/3 bits. In general, the key K ij is placed in the caches of users i and j. The keys are chosen combinatorially and a general strategy is discussed in Appendix A. The overall cache placement is as follows: Thus each cache has size M = 5× (1/3) = 5/3, where M D = 1, M K = 2/3. Now considering a worst case request where all users request different files, (d 1 , d 2 , d 3 ) = (A, B, C), the server can make the following transmission such that everyone can securely retrieve their requested files: The rate for this transmission is R C s = 3 × 1 3 = 1. It is easy to see that each user can retrieve its requested file from the transmission and its cache. A wiretapper on the other hand would gain no information about the files (A, B, C) from the transmission X (A,B,C) since I(X (A,B,C) ; A, B, C) = 0. Thus the (M, R C s ) pair (5/3, 1) is securely achievable. It can be seen from the cache contents that there are multiple keys in the system thereby avoiding a single point of failure. If an user/key is compromised, then the keys containing the users' index can be replaced with new ones or removed. Thus when the N = K = 3 system operates at this point, it is more robust to key failures. In general, if we choose operating points (M, R C s ) such that M K > 1/K, single points of failure in the system can be avoided. Thus based on more rigid security constraints, we can choose more keys and a greater transmission rate with lower cache memory. Thus the scheme forms an interesting memory-rate trade-off based on users' security constraints. ✸ We next present the main idea behind the proof of the converse stated in Theorem 3 through a novel extension of the cut-set bound to incorporate the security constraint. To this end, we focus on the caching system with N = 2 files (denoted by A and B) and K = 2 users (with cache contents denoted by Z 1 and Z 2 ). Consider the scenario in which user 1 demands file A and user 2 demands file B, i.e., the demand vector is (d 1 , d 2 ) = (A, B). It is easy to check that using the communication X (A,B) from the central server along with the two caches Z 1 , Z 2 , both files (A, B) can be recovered. This implies the following constraint: Next, for the communication X (A,B) to be secure, we also require the following security constraint to hold: Using these two constraints, we next show that for any scheme, the following bound of Theorem 3 must necessarily hold: From the constraints (12)-(13), we have the following sequence of inequalities: This implies Taking the limit ǫ → 0, we arrive at the proof of M ≥ 1. Now consider the fact that given any two transmissions from the server X (A,B) , X (B,A) and one cache Z 1 , both the files A, B can be recovered. Again, we have the following constraints for file retrieval and security: Thus we have, This implies that Taking the limit ǫ → 0, we arrive at the proof of R * s + M ≥ 2. We can see that both (15) and (19) hold for all achievable (M, R s ) pairs. Thus we have, R * s (M ) ≥ 2 − M and M ≥ 1 which gives the lower bound in Fig. 2(a).
Next, we look at the upper bound on the optimal rate for the secure and non-secure schemes for the case when the number of files and users increase. When N = K = 20, it can be seen from Fig. 4(a) that the secure and non-secure bounds almost coincide. For large values of N, K i.e., N = K = 100, the bounds are practically identical as seen in Fig. 4(b). This result shows that security from a wiretapper can be achieved at almost negligible cost compared to a non-secure scheme.
The trade-off between the fraction of cache memory occupied by the data and the keys in the secure caching system is shown in Fig. 5 for N = 5 files and K = 5 users. Consider the cache memory constraint in Theorem 1 i.e., M ∈ N −1 K t + 1, ∀t ∈ {0, 1, 2, . . . , K}. Now, we know that the cache memory is divided into data and key memory M = M D + M K . As shown in Appendix A, we have M K = 1 − t/K and M D = N t/K. From , data memory dominates. Since the main objective of caching is to reduce traffic at peak network loads, the system should be operated at a trade-off point where the data memory dominates the key memory. Also, in Example 2, we argued that single points of failure in system i.e., a single key for all users can be avoided for It is to be noted that in a general caching scenario, users may enter or leave the system at any time. In the case that only one key is used across all users, the compromise of the key of a single user leaving the system can violate the security of the entire system. It is also undesirable that new keys be redistributed to the entire system each time an user leaves. The proposed scheme avoids this scenario by sharing keys. In case an user leaves or is compromised, only the keys contained in that user's cache need to be replaced, leaving the others untouched. Thus we propose the region of operation to be: In general, a close inspection of Algorithm 1 reveals that when t ≤ K − r i.e., when M ≥ (N − 1)(K − r)/K + 1, a wiretapper can obtain all the keys in the system if it gains access to any r of the K user caches. This means that if r users are compromised, system security will be violated. It is a trivial fact that at t = 0, M = 1 and each user has one unique key. In this case, the wiretapper will need access to all the users' caches in order to break down the security of the system. From Fig. 5, we can see that Regime 5 is the weakest from the security perspective as there is only one key in the system. Thus operation in Regimes 1-4 is recommended for the case of N = K = 5. Now, considering the conventional secure scheme, it is seen that there is no coupling of users and hence no sharing of keys for any transmission. Here, only local caching gain is extracted and each transmission is useful to only one user. It is easy to see that in this system, each user can store an unique key of size |K| = (1− M −1 N −1 )F bits. Thus this scheme requires the wiretapper to have access to all the caches for the system security to be compromised. Comparing the conventional and proposed schemes from the security perspective, it can be seen that the proposed scheme is a trade-off between security and minimization of the rate over the shared link. While the conventional scheme is more difficult to compromise for all values of M , the proposed scheme is able to improve immensely on the transmission rate while still providing security. The fact that users share keys makes it relatively easier for the wiretapper to compromise the system. However, for a large number of users, the proposed scheme achieves magnitude order improvement in rate over the conventional scheme and it is highly unlikely that a very large number of users will be simultaneously compromised. Thus the proposed scheme should be preferred over the conventional scheme, especially for large number of users and files.
Next, we compare the achievable rate from Theorems 1 and 2 and the lower bound on the optimal rate in Theorem 3, and show that a constant multiplicative gap exists between the optimal R * s (M ) and the achievable rate.
Theorem 4. For any N ∈ N files and K ∈ K users, each having a cache size 1 ≤ M ≤ N , The proof of Theorem 4 is presented in Appendix D. In practice the bound is much tighter as the result in Theorem 4 was obtained using approximations. Using numerical simulations, it is found to be less than 5. In all cases the gap is slightly larger than the gap, 12, obtained in the case of the non-secure caching scheme in [5]. In the next section, we analyse the case of decentralized caching.

IV. DECENTRALIZED CACHING WITH SECURE DELIVERY
In this section, we extend the secure caching problem to a decentralized caching scheme as discussed in [7]. In the decentralized caching scheme, each user k with total cache memory M F bits, which is once again divided into a data memory (M D F bits) and key memory (M K F bits), is allowed to cache any random M −1 N −1 bits of each of the N files in the system. After the cache placement phase, the central server has two alternatives for delivering the requested files: the coded secure scheme or the conventional secure scheme.
In the coded delivery scheme, the central server aims to extract global caching gain. It maps the contents of individual users' caches to fragments (which contain non-overlapping combination of bits) in each file. The fragments reflect which user (or set of users) has cached bits contained in the given fragment. This phase is followed by a centralized key placement procedure where the server stores shared keys in each user's cache. Similar to the centralized scheme, the keys are orthogonal to each other and generated uniformly at random. We argue that key placement needs to be centralized to maintain key integrity and to secure the files from an external wiretapper. In the delivery phase, the server receives a request (d 1 , . . . , d K ) and forms coded multicast transmissions to extract global caching gain from the system. It then encodes the transmissions with the shared keys and transmits them over the multicast link. The decentralized algorithm is formally presented in Algorithm 2 in Appendix E.
In the conventional delivery procedure, the server extracts only local caching gain. In this case each user has  [7] for large file size F to satisfy all the requests. After the cache placement, the central server chooses the scheme which provides the minimum rate over the shared link considering the worst-case request by the users. The secure rate is then characterized by the following theorem.

Theorem 5. For N files and K users, each with a cache size of
is securely achievable. For any 1 ≤ M ≤ N the lower complex envelope of these points is achievable.
The proof of Theorem 5 is given in Appendix E. The variable t represents the part of the cache memory used to store data at each user i.e., M D = t (as detailed in Appendix E). Theorem 5 is defined for t > 0. At t = 0, we see that M = 1 i.e., the caches store a single key of the size of each file and entire files, XOR-ed with the keys, are transferred over the shared link. Thus the rate in this case is R D s (1) min{N, K}. As before, the same argument holds for the infeasibility of the secure scheme for M = 0. The following example illustrates the caching scheme which achieves the rate in Theorem 5.

Example 3.
We consider the case for N = 3 files and K = 3 users, each with a cache of size M . Let the three files be denoted as (W 1 , W 2 , W 3 ) = (A, B, C). Fig. 6 shows the rate achieved by the secure decentralized caching scheme given by Theorem 5 along with the rate of the insecure decentralized scheme from [7] and the corresponding centralized bounds. In the decentralized placement phase, each of the 3 users caches a subset of (M − 1)F/2 bits of each file independently at random. Thus, each bit of a file is cached by a specific user with probability (M − 1)/2. Considering the first file A, the server maps the storage of fragments of file A at the different users' caches into splits, A T , such that T ⊆ {1, 2, 3}, |T | = i for i = 0, 1, 2, 3. Thus there are 3 where A φ consists of bits of A which are not stored in any users' cache. On the other hand, A 123 has bits which are stored in all users cache. In general, bits in A T are stored in user k's cache if k ∈ T . By law of large numbers, we have: F bits with probability approaching one for large enough file size F. Thus we have: Note that |A 1 | ≈ |A 2 | ≈ |A 3 | and |A 12 | ≈ |A 13 | ≈ |A 23 |. The same analysis holds for files B, C. Next, we consider the generation of keys K S for S ⊆ {1, 2, 3}, |S| = j for j = 1, 2, 3. Thus the keys generated in the system are: It can be seen that there are 2 K − 1 = 7 unique keys in the system. Next we look at the cache contents from the central server's perspective after the centralized key placement phase and before the delivery procedure begins: It is to be noted that the cache placement phase is entirely decentralized as the users do not need to consider the number of other users in the system or their cache contents while storing file fragments in their cache. Next, we consider the delivery procedure of the decentralized caching scheme. The system is characterized based on the worst possible rate over the shared link. Thus we consider a request (W d1 , W d2 , W d3 ) = (A, B, C). The server responds by transmitting the reply X (A,B,C) . Let the set S ⊆ {1, 2, 3} : |S| = s for s = 3, 2, 1. Then we have: where W dk,S\{k} corresponds to the fraction of the file W dk , requested by user k which is not present in user k's cache but is present in the cache of the other s − 1 users in S. Thus, for K = 3 users in the system, the coded secure multicast delivery procedure has 3 phases for each of s = 3, 2, 1.
It can be seen that K 123 is associated with sub-files A 23 , B 13 , C 12 . Thus the size of the key is |K 123 | = max{|A 23 |, |B 13 |, |C 12 |}. In this case, each sub-file is zero padded to the size of the largest sub-file in the set. If we consider each of these files are of equal size, then the key has the size of each sub-file. For ease of exposition, we consider that the sub-files are of approximately equal size.
Considering user 1, we see that Z 1 contains B 13 , C 12 and K 123 . Thus user 1 can XOR out A 23 from the transmission. Thus user 1 can extract the requested part of the information. It can be seen that the same holds for users 2 and 3. Thus the transmission is useful for all users and the key makes it secure from the wiretapper. For s = 3, there is only one transmission of the size of each of these sub-files. Thus the rate over the shared link for this transmission is: Again for user 1, we can see that Z 1 contains B 1 , C 1 , K 12 , K 13 . Thus it can extract A 2 , A 3 from this transmission. Similarly the other users can extract fragments of their requested files from the transmission. In this case, there are three transmissions each of the size of file fragment, say, A 2 . Thus the rate of this transmission is: These transmissions are sent to individual users, containing the residual fragments not stored in each user. The size of each transmission is equal to the size of the file fragments A φ , B φ , C φ . Thus the rate of this is: Again considering user 1, we can see that the fragments of A not present in its cache i.e., A φ , A 2 , A 3 , A 23 are extracted from the entire transmission. The same holds true for the other users. The rate for the composite transmission X (A,B,C) is obtained by summing (22), (23) and (24): which is the expression given in Theorem 5 for N = K = 3. The (M, R D s ) trade-off for the secure and non-secure schemes for N = K = 3 is shown in Fig. 6. Now, we have: Considering the point M = 5/3, we have R D s (M ) = 38/27. Thus the (M, R D s ) = (5/3, 38/27) is securely achievable. This is seen from the (M, R D s ) trade-off in Fig. 6. Similarly other points on the trade-off curve can be evaluated using other feasible values of M . All points on the lines joining the achievable (M, R D s ) points are also achievable. Compared to the centralized secure scheme, we see that the decentralized scheme performs slightly worse than the centralized i.e., there is a cost incurred due to decentralized data storage. Compared to the non-secure decentralized bound from [7], we also observe that a cost for security is paid i.e., a higher achievable rate for a given cache size. ✸ Next, we consider the centralized and decentralized trade-off for a large number of files and users. Fig. 7(a) illustrates the case for N = K = 20. Compared to Fig. 6, we can see that as the number of files and users increase, the decentralized scheme approaches the centralized caching. Thus for large number of files and users, the rates are asymptotically equal. Comparing with the non-secure decentralized scheme from [7], Fig. 7(b) shows, surprisingly and similar to the centralized case, that the cost for security is almost negligible when number of files and users increase. The following theorem and corollary compares the rate of the achievable secure decentralized scheme given in Theorem 5 to the lower bound on the rate of the optimal secure scheme given in Theorem 3 and the rate of the achievable secure centralized caching scheme given in Theorems 1 and 2.
The proof of Theorem 6 is given in Appendix F. Theorem 6 implies that no scheme, regardless of complexity can improve by more than a constant factor upon the secure decentralized caching scheme presented in Algorithm 2.

Corollary 7.
Let R C s (M ) be the rate of the secure centralized caching scheme given in Theorem 1 and R D s (M ) be the rate of the secure decentralized caching scheme given in Theorem 5. For N ∈ N files and K ∈ N users, for Corollary 7 is a direct outcome of the results presented in Theorem 4 and Theorem 6. It shows that the decentralized scheme is at most a factor 17 worse than the secure centralized scheme. This is a loose bound and can be numerically tightened to around 1.5.

V. CONCLUSION
In this paper, we have analyzed the problem of secure caching in the presence of an external wiretapper for both centralized and decentralized cache placement. We have proposed a key based secure caching strategy which is robust to compromise of users and keys. We have approximated the information theoretic optimal rate of the secure caching problem with novel upper and lower bounds. It has been shown that there is a constant multiplicative gap between the optimal and the achievable rates for the given scheme in case of both centralized and decentralized caching scenarios. We have shown that for large number of files and users, the secure bounds approach that of the non-secure case i.e., the cost of security in the system is negligible when the number of files and users increase. We also show that for a large number of files and users, the centralized and decentralized secure schemes are asymptotically equal.

APPENDIX A PROOF OF THEOREM 1
In this section, we discuss the secure centralized caching strategy which achieves the upper bound R C s (M ) as stated in Theorem 1. The algorithm achieving the rate in Theorem 1 is presented in Algorithm 1. for n = 1, 2, . . . , N do 8: File W n,T is place in cache, Z k , of user k if k ∈ T

9:
Key K Tk is placed in cache, Z k , of user k if k ∈ T k 10: end for 11: end for Coded Delivery: 12: for S such that S ⊆ {1, 2, . . . , K}, |S| = t + 1 do 13: Server sends K S ⊕ k∈S W dk,S\{k} 14: end for There are two phases in the caching strategy: the storage phase and the delivery phase. We consider a cache size M ≤ N and M ∈ N −1 K · {0, 1. . . . , K} + 1. Let t ∈ {0, 1, . . . , K} be an integer between 0 and K. The cache memory size can then be parametrized by t as: From (28), we have t = K(M −1) N −1 . Next, we break up the total cache memory into data memory and key memory, M = M D + M K , as follows: From the discussion in Section III, we know that the conventional secure scheme achieves the (M, R s ) pair (1, min{N, K}) and (N, 0). Thus R * s (1) ≤ min{N, K} and R * s (N ) = 0. We therefore consider the case in which 1 < M < N . In this case, t ∈ {1, 2, . . . , K − 1}.

Storage Phase:
In the placement phase, each file W n for n = 1, . . . , N is split into K t non-overlapping sub-files of equal size F/ K t : For each n, the sub-file W n,τ is placed the cache of user k if k ∈ τ . Since |τ | = t, for each user k ∈ τ , there are t − 1 out of K − 1 possible users with whom it shares a sub-file of a given file W n . Thus each user caches N K−1 t−1 sub-files.Next we generate a set of keys, each of the size of a sub-file i.e. of size F/ K t : The key K τk is placed in the cache of user k if k ∈ τ k . The keys are generated such that all the keys are orthogonal to each other and each key is distributed according to Again, since |τ k | = t + 1, each user k ∈ τ k shares key K τk with t out of K − 1 possible users. Thus there are K−1 t keys in the cache of each user. Given each key and sub-file has size F/ K t , number of bits required for storage at each user is: which satisfies the memory constraint.

Delivery Phase:
We now elaborate on the delivery phase. Consider a request vector (d 1 , . . . , d k ) ∈ {1, . . . , N K } where user k requests the file W dk . Let S ⊆ {1, . . . , K} be a subset of |S| = t + 1 users. Every t users in S share a sub-file in their cache which is requested by the t + 1-th user. Given a user k ∈ S and |S \ {k}| = t, the sub-file W dk,S\{k} is requested by user k as it is a sub-file of W dk which is missing at user k since k / ∈ S \ {k}. The file is present in the cache of the t users s ∈ S \ {k}. For each such subset S ⊆ {1, . . . , K}, the server sends the following transmission: X (d1,...,dk) = K S ⊕ s∈S W ds,S\{s} : S ⊆ {1, 2, . . . , K}, |S| = t + 1 .
The number of subsets S is K t+1 . Thus there are K t+1 transmissions and an unique key associated with each transmission i.e., there are K t+1 keys in the system. Each transmission has the size of a subfile and thus the total number of bits sent over the rate-limited link is: Next, we show that the delivery phase does not reveal any information to the wiretapper i.e., we show that I X (d1,...,dk) ; W 1 , . . . , W N = 0 We have, where, the last equality follows from the fact that the keys are uniformly distributed and are independent of the files (W 1 , . . . , W N ). Using the fact that H(A, B) ≤ H(A) + H(B) 2 , we have: On the other hand, we have: where the equality in (39) follows from the fact that the keys are orthogonal to each other and they are uniformly distributed as in (32). Substituting (38) and (39) into (37), we have: Using the fact that for any X, Y , I(X; Y ) ≥ 0, we have: which proves that the rate R C s (M ) is securely achievable. This completes the proof of Theorem 1.

APPENDIX B PROOF OF THEOREM 2
In this section, we characterize the achievable rate for the case of K > N i.e., the number of users is greater than the number of files. In this case, there is a natural opportunity of multicasting all N files to K users. In our secure setting, a conventional caching scheme [5] achieves a rate of The rate obtained in Theorem 2 is a minimum of the rate in Theorem 1 and R(M ): For K > N , (43) reduces to: This concludes the proof of Theorem 2.

APPENDIX C PROOF OF THEOREM 3
In this section, we prove the information-theoretic lower bound on R * s (M ) for any N, K ∈ N. Let s be an integer such that s ∈ {1, . . . , min{N, K}}.
Consider the first s caches Z 1 , . . . , Z s . For a request vector (d 1 , d 2 , . . . , d s , d s+1 , . . . , d K ) = (1, 2, . . . , s, φ, . . . , φ), the transmission X 1 = X (d1,...,dk) , along with the caches Z 1 , . . . , Z s must be able to decode the files W 1 , . . . , W s . Similarly there for another request (d 1 , d 2 , . . . , d s , d s+1 , . . . , d K ) = (s + 1, s + 2, . . . , 2s, φ, . . . , φ), the transmission X 2 , which along with caches Z 1 , . . . , Z s , must be able to decode the files W s+1 , . . . , W 2s . Thus considering ⌊N/s⌋ different requests, the transmissions from the central server denoted by X 1 , . . . , X ⌊N/s⌋ , along with the caches Z 1 , . . . , Z s , must be able to decode the files W 1 , . . . , W s⌊N/s⌋ . Let In addition, we also have constraints based on file retrieval and security. The file retrieval constraint is based on the fact that given all possible transmissions and caches, all files can can be retrieved. The security constraint is that a wiretapper should not be able to retrieve any information about the files from any transmission by the server. Using Definition 1, we have: I( W ; X l ) ≤ ǫ; l = 1, . . . , ⌊N/s⌋ We present a novel extension to the cut-set bound argument [12] to include the security and file retrieval constraints. Consider the information flow consisting of transmissions X 1 , . . . , X ⌊N/s⌋ and caches Z 1 , . . . , Z s for decoding files W 1 , . . . , W s⌊N/s⌋ . This flow has minimum capacity s⌊N/s⌋. Thus, we have: ≤ I W ; X \{l} , Z|X l + 2ǫ ≤ H X \{l} , Z + 2ǫ Solving for R * s and optimizing over all possible s, we have: which concludes the proof of Theorem 3.

APPENDIX D PROOF OF THEOREM 4
In this section, we prove that a constant multiplicative gap exists between the securely achievable rate R C s (M ) given in Theorems 1 and 2 and the optimal secure rate R * s (M ). We will consider two cases: min{N, K} ≤ 17 and min{N, K} ≥ 18. For min{N, K} ≤ 17, we have from Theorem 2: Also, setting s = 1 in Theorem 3 gives: Thus we have: For min{N, K} ≥ 18, we consider the fact that the rate in Theorem 2 has 3 distinct regimes: We consider each of the three regimes separately.
By Theorem 1, we have: By Theorem 3 and using the fact that ⌊N/s⌋ ≥ N/s − 1, we have: Combining (52) and (54), we have: ChoosingM = M − (N − 1)/K, and using the fact that R C s (M ) is monotonically decreasing in M , we have: where we have used M −1 N −1 > 1 K in the last inequality. Now setting s = ⌊0.1530 N −1 M −1 ⌋ ∈ {1, . . . , min{N, K}} in Theorem 3, we have: Combining (57) and (58), we get: Regime 3: 0.0628(N − 1) < M − 1 ≤ N − 1 LetM − 1 be a multiple of (N − 1)/K less than equal to 0.0628(N − 1), such that Then we have: Now by Theorem 1 and using (60), we have: Thus we have, from (61) and (62): Setting s = 1 in Theorem 3, we have again: Thus combining (63) and (64), we get: Thus we have proved that for any N, K ∈ N and all 1 ≤ M ≤ N , there is a constant multiplicative gap of 17 between the achievable rate and the information theoretic optimal. This concludes the proof of Theorem 4.

APPENDIX E PROOF OF THEOREM 5
The decentralized algorithm which achieves the rate in Theorem 5 is given in Algorithm 2. Given N files and K users, each with a cache size of M F bits, we first aim to show that the memory constraint M ∈ N −1 N t + 1 for t ∈ (0, N ] is valid. We will then evaluate the rate of Algorithm 2 and show that the multicast delivery is information theoretically secure.
Considering the proposed decentralized scheme in Algorithm 2, each user is allowed to cache any random subset of M −1 N −1 F bits of any file W n . Since the choice of these subsets is uniform, given a particular bit in file W n , the probability of the bit being cached at a given user is: Considering a fixed subset of s out of K users, the probability that this bit is cached exactly at these s users and not cached at the remaining (K − s) users is q s (1 − q) K−s . The expected number of bits of W n that are cached The actual realization of the random number of bits of a file W n cached at s users is within the range: For ease of exposition, we consider all the fragments of files shared by s users have the same size. Hence the factor o(F ) can be ignored for large enough F .

Memory Constraint
Next, the server maps the contents of the users' caches to non-overlapping fragments in files such that each fragment reflects which users have cached the bits contained in the fragment. First, we aim to calculate the number of fragment of each file that a user stores. Referring to Algorithm 2, Line 5, the variable i signifies the number of users which share a given file fragment. For i = 0, the file fragments are W n,φ which is not stored at any user. When i = 1, the file fragments are W n,k for k = 1, . . . , K which are stored only at one user and hence shared by none. In general for any i, the fragments W n,S such that |S| = i are stored at i users and shared by any given user with i − 1 other users. Thus, for a given a user k, the number of fragments it shares with i − 1 out of the remaining K − 1 users for each i is given by K−1 i−1 . From (67), we have the size of fragments which are stored at exactly i users is F q i (1 − q) K−i . Thus, the total memory at each user for storing data is given by: Next, we describe the centralized key placement. For each sub-set S ⊆ {1, . . . , K} of size s, i.e., |S| = s, where s = 1, 2, . . . , K, a key K S is generated as follows: Subsequently, the key K S is placed in the cache of user k if k ∈ S. The centralized key generation and placement phase is inherently related to the delivery phase of the decentralized algorithm since the size of a key is related to the size of file fragment which is encoded with the key during coded delivery. Consider the coded delivery phase in Algorithm 2, Line 15 − 19. Given a request (d 1 , . . . , d K ), the composite transmission X (d1,...,dK ) is sent by the central server. The composite transmission can thus be written as: where X s (d1,...,dK ) consists of K s transmissions, one for each possible sub-set S of size s i.e., X s (d1,...,dK ) = K S ⊕ k∈S W dk,S\{k} : |S| = s .
W dk,S\{k} denotes the part of the file W dk requested by user k which is present in the caches all the users in set S except in the cache of user k. The key K S is associated with the transmission ⊕ k∈S W dk,S\{k} . Furthermore, from the design of the key placement, the key K S is available in the cache of all the s users in the sub-set S.
Since |S \ {k}| = s − 1, from (67) we have, the expected size of the fragment W dk,S\{k} is given by: For a fixed value of s, the size of each transmission in X s (d1,...,dK ) is given by: Thus, each key K S must be chosen with the size: which is precisely how each key is generated according to (70). Now, for a given value of s, a user k needs file fragments contained in S \ {k} i.e., s − 1 other users in the set S. This set of s − 1 users need to be chosen out of the remaining K − 1 users. Thus for each s, there are K−1 s−1 keys associated with each user. Thus the total number of keys at each user is given by: The total memory occupied by keys at each users' cache is given by: From (76) and (69), we have: which proves the memory constraint. Putting M D = t, the memory break up can be parametrized as: Now, when the data memory t = 0, M = 1 which is the condition for storing just keys in caches ad sending entire files over the shared link. On the other hand, when t = N , M = N i.e., the entire files are stored in the caches and there is no need for a transmission. Thus t ∈ (0, N ] is the region of interest. Hence M ∈ N −1 N · (0, N ] + 1 is valid. Note that the constraint on M is due to the centralized key placement and is thus the cost for security. Remark 1. Considering the range for file fragment size in (68), if we consider that the fragments are not indeed of equal size, then in turn the key size is also within the range M K ± o(F ). If this is the case, then the cache memory constraint will be within the range M ± o(F ). Since o(F ) can generally be ignored in comparison to M , the cache memory constraint is satisfied on an average.

Calculation of R D s (M ) A. Analysis of Conventional Secure Scheme
We begin with the analysis of the conventional secure delivery scheme. For N ≤ K, the worst case request corresponds at least one user requesting every file. Considering all users request file W n , they all have F (M − 1)/(N − 1) of its bits already in their cache. Thus for F large enough, at most random linear combinations need to be sent to the users requesting the file n. For ease of exposition, o(F ) can be ignored. In the conventional scheme, each user k stores an unique key K k of size 1 − M −1 N −1 F bits which is XOR-ed with the data before transmission. As this is done for all N files, the normalized delivery rate is: If N > K, then at most K different files can be requested. The transmission after XOR-ing with a key K k for each user k has a normalized rate of: Thus for all N and M ∈ (0, N ], the conventional scheme has a normalized rate of:

B. Analysis of the proposed scheme
Considering the secure delivery procedure for the coded caching scheme in Algorithm 2, we can see that there are K s subsets S of cardinality s. Thus there are K s transmissions for each s = K, K − 1, . . . , 1.
Now, for the coded secure transmission, the unique key K S is associated with each subset S. The total number of unique keys in the system is given by: Now, considering the fragment size of W dk,S\{k} in (73) and the transmission X s (d1,...,dK ) in (72), for each value of s, the size of each transmission is given by: Summing over all values of s, the rate of the composite transmission X (d1,...,dK ) is: The server can use either the proposed scheme or the conventional scheme, whichever uses the minimal rate. Thus combining (79) and (82), Algorithm 2 achieves a rate of: Using the fact that the expression in (83) can be simplified to give the expression in Theorem 5:

Proof of Secure Achievability
Next, we show that the delivery phase does not reveal any information to the wiretapper i.e., we show that: I X (d1,...,dK ) ; W 1 , . . . , W N = 0 (85) In the decentralized scheme, the central server transmits X (d1,...,dK ) to satisfy the requests (d 1 , . . . , d k ) of the K users. The composite transmission X (d1,...,dK ) , given in (71), consists of K s transmissions for each s = K, K − Using the fact that the rate can be upper bounded as: for all M ∈ N −1 N · (0, N ] + 1. We consider two cases: min{N, K} ≤ 17 and min{N, K} ≥ 18. First considering min{N, K} ≤ 17, from (92), we have: Also, setting s = 1 in Theorem 3 gives: Thus we have: For min{N, K} ≥ 18, we consider 3 distinct regimes: Using (92), we have: Now setting s = ⌊0.1460 N −1 M −1 ⌋ in Theorem 3, we have: Combining (100) Setting s = 1 in Theorem 3, we have again: Thus combining (103) and (104), we get: Thus we have proved that for any N, K ∈ N and all 1 ≤ M ≤ N , there is a constant multiplicative gap of 17 between the achievable secure decentralized rate and the information theoretic optimal for any secure scheme. This concludes the proof of Theorem 6.