Secretive Coded Caching with Shared Caches

In wireless content delivery networks, caching helps in reducing the disparity in traffic load between peak and off-peak hours, by allowing end users to store parts of the library in their local caches. The seminal work by Maddah-Ali and Niesen in [1] established that congestion of the shared broadcast link can be reduced further by making coded transmissions that are useful to more than one user simultaneously. This system operates in two phases-placement phase and delivery phase. In the placement phase, the server fills the users’ caches with some fraction of all the files, without knowing their future demands. In the delivery phase, users reveal their file requests, and the server responds by sending coded multicast transmissions over the broadcast link such that, the users, from the transmissions and cache contents, can recover their requested files. The number of bits transmitted over the shared link, normalized by the file size, is known as the rate of the coded caching scheme. To reduce the load on the link, rate needs to be minimised. However, the placement and delivery as in [1] violates the secrecy constraint, as users get some information about all the files from their caches, even before they reveal their demands. In secretive coded caching, the two phases must be designed such that, users obtain no information about the files that they do not request.

Secretive coded caching problem was first studied in [2, 3] where the authors proposed an achievable coded caching scheme imposing the constraint of perfect secrecy, under both centralized and decentralized settings. Their general scheme was also secure against eavesdroppers, as in [4]. This problem was extended to the setup of Device-to-Device caching networks in [5] and to Combination networks in [6]. The authors in [7] considered secretive coded caching in a setting where at most $l$ out of the $K$ users are untrustworthy, and might collude among themselves. On setting the value of $l$ to unity, this scheme reduces to the original scheme in [3].

All the works cited above [2, 3, 5, 6, 7], consider a dedicated caching network, i.e., each user is privileged to access a cache, distinct from the remaining users in the network. However, to the best of our knowledge, in a shared cache setup, where multiple users are assisted by a single helper cache, secretive coded caching has not been studied so far. References [8] and [9] studied coded caching in this setting, without imposing the secrecy constraint, with uncoded and coded placement respectively. In [8], the authors formulate the worst case achievable rate (which they refer to as ‘delay’) and prove its optimality under uncoded placement through an index-coding-aided converse. They create multicasting opportunities in their delivery algorithm, by leveraging the content overlap between distinct caches, similar to that in [1]. In [9], the authors provide a scheme achieving lower worst-case delay than [8] by placing uncoded and coded sub-files in the helper caches, utilizing the knowledge of the user to cache association profile and optimising over the size of these sub-files to minimise rate.

Like any secretive coded caching problem, in our shared cache setup too, secrecy of content of files has to be preserved in two aspects: (i) caching, and (ii) transmission. To ensure no leakage of information via (i), we employ an appropriate secret-sharing scheme to encode the files before they are placed at the helper caches. By encoding the files this way, the cached contents alone reveal no information about the files to the users. For no information leakage via (ii), we securely deliver each multicast message so that, only the users who benefit from the transmission can decode it. This is done by XOR’ing each message with a unique key. This necessitates that the key used for encoding each multicast message serving a group of users is made privately available to the user caches of this group. Otherwise, any user associated to a given cache, can recover the files requested by the other users connected to the same cache, resulting in a breach of the secrecy constraint. We outline the contributions of this letter below:

• •

  We provide a secretively achievable coded caching scheme for a caching system with shared caches.

• •

  When our scheme is applied to the dedicated caches setup, we show that the secretively achievable rate-memory pair as obtained in [3] is recovered.

The rest of the paper is organized as follows. Section II sets up the problem. The proposed scheme is presented in Section III. In Section IV, we discuss the main results of the paper. Finally, we conclude the paper with Section V.

The system model is illustrated in Fig. 1. The server has a library of $N$ files, denoted by $W^{[N]}:=\{W^{1},W^{2},\dots,W^{N}$}, of size $B$ bits each. There are $K$ users in the system, and the number of files in the library exceeds the number of users, i.e., $N\geq K$. The users are assisted by $\Lambda(\leq K)$ helper caches, each with storage capacity of $M$ files. Further, user $k$ has a cache of normalized size $M_{k},\ \forall k\in[K]$.

Like the system model introduced in [8], the $K$ users are partitioned into $\Lambda$ groups, based on the cache they have access to. This is reflected by the user-to-cache association $\mathcal{U}=\{\mathcal{U}_{1},\mathcal{U}_{2},\ldots,\mathcal{U}_{\Lambda}\}$, where $\forall\lambda\in[\Lambda]=\{1,2,\dots,\Lambda\}$, $\mathcal{U}_{\lambda}$ is the ordered set of users accessing cache $\lambda$. The $j^{th}$ user in $\mathcal{U}_{\lambda}$ is denoted by $\mathcal{U}_{\lambda}(j)$. The user-association profile is given by the vector $\boldsymbol{\mathcal{L}}=(\mathcal{L}_{1},\mathcal{L}_{2},\ldots,\mathcal{L}_{\Lambda})$, with $\mathcal{L}_{1}\geq\mathcal{L}_{2},\ldots,\geq\mathcal{L}_{\Lambda}$, where $\mathcal{L}_{\lambda}$ represents the number of users associated to the $\lambda^{th}$ most populated helper cache. The most populated cache has the maximum number of users assigned to it. $\sum_{\lambda=1}^{\Lambda}\mathcal{L}_{\lambda}=K$. Without loss of generality, we assume that caches are labelled in a non-increasing order of the number of users that access them, i.e., $|\mathcal{U}_{\lambda}|=\mathcal{L}_{\lambda}\ \forall\lambda\in[\Lambda]$. Therefore, cache $1$ is accessed by $\mathcal{L}_{1}$ number of users, cache $2$ is accessed by $\mathcal{L}_{2}$ number of users, and so on. If not, we can simply relabel the caches to obtain this ordering. The system in our formulation operates in four phases:

1. a)

   Helper Cache Placement Phase: The server, after encoding each file into shares populates the helper caches with these shares without knowing the user-to-cache association.

2. b)

   User-to-Cache Assignment Phase: This occurs after the shares have been placed. Each user is assigned to a single helper cache and $\mathcal{U}$ is communicated to the server.

3. c)

   User Cache Placement Phase: Once the user-to-cache association is conveyed, the server privately places unique keys in the user caches.

4. d)

   Delivery Phase: Each user requests for a single file from the library. In response, the server broadcasts coded multicast messages over the shared link so as to satisfy the users’ demands, and ensuring that the users gain no information about the content of the files they did not request.

To summarize, the system model considered in this paper differs from the one in [8] in the following aspects:

• •

  User $k$ has a dedicated cache of size $M_{k}\geq 1,\ \forall k\in[K]$ to store keys.

• •

  There is an additional phase for placing these keys in the user caches.

The content in the helper and user cache, comprising the shares and keys, that user $k$ has access to is denoted by $\mathcal{Z}_{k}$, $\forall\ k\in[K]$. In the delivery phase, each user requests for a unique file. Users convey their requests to the server in the form of a demand vector $\mathbf{d}=(d_{1},d_{2},\dots,d_{K})$, which represents that user $k$ has requested $W^{d_{k}}$. We assume $N\geq K$ and the worst case demand vector, i.e., $d_{i}\neq d_{j},\ \forall\ \ i,j\in[K],i\neq j$. Let, for a profile $\boldsymbol{\mathcal{L}}$, $X_{\mathbf{d}}(\boldsymbol{\mathcal{L}})$ denote the transmitted message vector corresponding to the demand $\mathbf{d}$. Given this setting, the perfect secrecy constraint has to be met by all the users. By the definition in [3], for perfect secrecy, information leakage must be $0$, i.e.,

where $I(;)$ is the mutual information, and $W^{[N]\setminus d_{k}}$ is the set of all files except the one requested by user $k$. The maximum load on the shared link of a shared cache system with profile $\boldsymbol{\mathcal{L}}$, under the constraint of $\eqref{sec_per}$ is given by the effective number of files that the server broadcasts in the delivery phase to meet the users’ demands when they are all distinct. This is quantified by the number of bits transmitted by the server, normalised by file size, for worst case demand vector and is known as the secretively achievable rate $R^{s}(\boldsymbol{\mathcal{L}})$, expressed in units of files.

Before describing the general scheme, we see an example.

Example 1: Consider a network with $N=K=M=3,M_{k}\geq 1,k\in[3]$, and file size of $B$ bits. $\mathcal{U}_{1}=\{1,2\}$, $\mathcal{U}_{2}=\{3\}$; hence $\boldsymbol{\mathcal{L}}=(2,1)$. The server selects $V^{1},V^{2},V^{3}$ randomly and uniformly from the Galois field $\mathbb{F}_{2^{B}}$. In the helper-cache placement phase, the server places, $\forall n\in[3]$, $S^{n}_{1}=W^{n}\oplus V^{n}$ in cache 1 and $S^{n}_{2}=V^{n}$ in cache 2. The server also selects two random keys $T_{\{1,3\}}$ and $T_{\{2\}}$ uniformly from $\mathbb{F}_{2^{B}}$. In the user cache placement phase, the server privately places $T_{\{1,3\}}$ in user caches 1 and 3, $T_{\{2\}}$ in user cache 2. In the delivery phase, let $\mathbf{d}=(1,2,3)$. The server transmits $S^{1}_{2}\oplus S^{3}_{1}\oplus T_{\{1,3\}}$ and $S^{2}_{1}\oplus T_{\{2\}}$. User 1 can decode $W^{1}$ but obtains no information about $W^{2}$ and $W^{3}$. This holds for users 2 and 3 as well. The rate is thus $2$ units.

We now describe the general coded caching scheme and derive the secretively achievable rate $R^{s}(\boldsymbol{\mathcal{L}})$ for memory points $M$ where $t=\frac{\Lambda M}{M+N}\in\{0,1,\dots,\Lambda-1\}$ is the caching parameter. The rate corresponding to non-integer values of $t$ are achievable through memory sharing. The steps involved are as follows:

In the context of secretive (non-secretive) coded caching, the caching parameter, $t$ indicates the number of helper caches in which a given share (sub-file) is placed. Fig. 2 depicts the rate vs $t$ plots for shared cache setting with and without secrecy imposed. The secretively achievable rate is higher than the non-secretively achievable rate $\forall t$ except when $t=0$. This is because, the former involves shares, instead of sub-files in the placement and delivery phases. The shares consume larger number of bits compared to sub-files due to the randomness introduced in the form of encryption keys.

Intuitively, the total number of missing shares is the same irrespective of $\boldsymbol{\mathcal{L}}$. But, the number of users served in a single transmission with $\boldsymbol{\mathcal{L}}_{\text{unif}}$ is always $t+1$, where $t$ is the number of helper caches in which a given share is placed. This way, the uniform profile exploits full multicasting gain, thus requiring minimum number of transmissions.

In this letter, we proposed a secretively achievable coded caching scheme with shared caches, and showed that when our scheme is applied to the dedicated cache network, the general achievable scheme presented in [3] is recovered. In our solution, we indicated that the users associated to the same cache act as potential eavesdroppers, thus violating the secrecy. Therefore, we secure each message in the delivery phase with a unique key. The secretively achievable rate varies with the user association profile $\boldsymbol{\mathcal{L}}$, and is minimum in the case of uniform profile $\boldsymbol{\mathcal{L}_{\text{unif}}}$. However, testing the optimality of our scheme remains open. Finding an information theoretic lower bound on the optimal rate is an interesting direction to pursue.