Cache-Aided Variable-Length Coding with Perfect Privacy
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916794451623936 |
|---|---|
| author | Zamani, Amirreza Skoglund, Mikael |
| author_facet | Zamani, Amirreza Skoglund, Mikael |
| contents | A cache-aided compression problem with perfect privacy is studied, where a server has access to a database of $N$ files, $(Y_1,...,Y_N)$, each of size $F$ bits. The server is connected to $K$ users through a shared link, where each user has access to a local cache of size $MF$ bits. In the placement phase, the server fills the users$'$ caches without prior knowledge of their future demands, while the delivery phase takes place after the users send their demands to the server. We assume that each file $Y_i$ is arbitrarily correlated with a private attribute $X$, and an adversary is assumed to have access to the shared link. The users and the server have access to a shared secret key $W$. The goal is to design the cache contents and the delivered message $\cal C$ such that the average length of $\mathcal{C}$ is minimized, while satisfying: i. The response $\cal C$ does not disclose any information about $X$, i.e., $X$ and $\cal C$ are statistically independent yielding $I(X;\mathcal{C})=0$, which corresponds to the perfect privacy constraint; ii. User $i$ is able to decode its demand, $Y_{d_i}$, by using its local cache $Z_i$, delivered message $\cal C$, and the shared secret key $W$. Due to the correlation of database with the private attribute, existing codes for cache-aided delivery do not fulfill the perfect privacy constraint. Indeed, in this work, we propose a lossless variable-length coding scheme that combines privacy-aware compression with coded caching techniques. In particular, we use two-part code construction and Functional Representation Lemma. Furthermore, we propose an alternative coding scheme based on the minimum entropy coupling concept and a greedy entropy-based algorithm. We show that the proposed scheme improves the previous results obtained by Functional Representation Lemma. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_13184 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Cache-Aided Variable-Length Coding with Perfect Privacy Zamani, Amirreza Skoglund, Mikael Information Theory A cache-aided compression problem with perfect privacy is studied, where a server has access to a database of $N$ files, $(Y_1,...,Y_N)$, each of size $F$ bits. The server is connected to $K$ users through a shared link, where each user has access to a local cache of size $MF$ bits. In the placement phase, the server fills the users$'$ caches without prior knowledge of their future demands, while the delivery phase takes place after the users send their demands to the server. We assume that each file $Y_i$ is arbitrarily correlated with a private attribute $X$, and an adversary is assumed to have access to the shared link. The users and the server have access to a shared secret key $W$. The goal is to design the cache contents and the delivered message $\cal C$ such that the average length of $\mathcal{C}$ is minimized, while satisfying: i. The response $\cal C$ does not disclose any information about $X$, i.e., $X$ and $\cal C$ are statistically independent yielding $I(X;\mathcal{C})=0$, which corresponds to the perfect privacy constraint; ii. User $i$ is able to decode its demand, $Y_{d_i}$, by using its local cache $Z_i$, delivered message $\cal C$, and the shared secret key $W$. Due to the correlation of database with the private attribute, existing codes for cache-aided delivery do not fulfill the perfect privacy constraint. Indeed, in this work, we propose a lossless variable-length coding scheme that combines privacy-aware compression with coded caching techniques. In particular, we use two-part code construction and Functional Representation Lemma. Furthermore, we propose an alternative coding scheme based on the minimum entropy coupling concept and a greedy entropy-based algorithm. We show that the proposed scheme improves the previous results obtained by Functional Representation Lemma. |
| title | Cache-Aided Variable-Length Coding with Perfect Privacy |
| topic | Information Theory |
| url | https://arxiv.org/abs/2306.13184 |