.png){kind=icon}
.png){kind=icon}
Return
Cache-Aided Variable-Length Coding With Perfect Privacy
.png){kind=icon}
PRE
AI
DOI：10.1109/JSAC.2025.3638317.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A cache-aided compression problem with perfect privacy is studied, where a server has access to a database of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula> files, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(Y_{1},\ldots,Y_{N})$ </tex-math></inline-formula>, each of size <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$F$ </tex-math></inline-formula> bits. The server is connected to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$K$ </tex-math></inline-formula> users through a shared link, where each user has access to a local cache of size <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$MF$ </tex-math></inline-formula> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$Y_{i}$ </tex-math></inline-formula> is arbitrarily correlated with a private attribute <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula>, and an adversary is assumed to have access to the shared link. The users and the server have access to a shared secret key <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$W$ </tex-math></inline-formula>. The goal is to design the cache contents and the delivered message <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\cal C$ </tex-math></inline-formula> such that the average length of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {C}$ </tex-math></inline-formula> is minimized, while satisfying: 1) the response <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\cal C$ </tex-math></inline-formula> does not disclose any information about <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula>, i.e., <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\cal C$ </tex-math></inline-formula> are statistically independent yielding <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$I(X;\mathcal {C})=0$ </tex-math></inline-formula>, which corresponds to the perfect privacy constraint; and 2) user <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$i$ </tex-math></inline-formula> is able to decode its demand, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$Y_{d_{i}}$ </tex-math></inline-formula>, by using its local cache <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$Z_{i}$ </tex-math></inline-formula>, delivered message <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\cal C$ </tex-math></inline-formula>, and the shared secret key <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$W$ </tex-math></inline-formula>. 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. Considering two special cases we improve both coding schemes using the common information concept. Finally, we compare the proposed schemes in numerical examples and provide an application considering an encoder with limited buffer size.
Keywords:
Coded caching
perfect privacy
functional representation lemma
minimum entropy coupling
common information
Journal
IF:
17.2
Papers:
6.4K
Citations:
3.1W