Private Variable-Length Coding with Sequential Encoder
Amirreza Zamani, Tobias J. Oechtering, Denız Gündüz, Mikael Skoglund · 2025
A multi-user private data compression problem is studied. A server has access to a database of$N$files,$(Y_{1},\ldots,\ Y_{N})$, each of size$F$bits and is connected to an encoder. The encoder is connected through an unsecured link to a user. We assume that each file$Y_{i}$is arbitrarily correlated with a private attribute$X$, which is assumed to be accessible by the encoder. Moreover, an adversary is assumed to have access to the link. The users and the encoder have access to a shared secret key$W$. We assume that at each time the user asks for a file$Y_{d_{i}}$, where$(d_{1},\ \ldots,\ d_{K})$corresponds to the demand vector. The goal is to design the delivered message$\mathcal{C}=(\mathcal{C}_{1},\ \ldots,\mathcal{C}_{K})$after the user send his demands to the encoder such that the average length of$\mathcal{C}$is minimized, while satisfying:$\mathbf{i}$. The message$\mathcal{C}$does not reveal any information about$X$, i.e.,$X$and$\mathcal{C}$are independent, which corresponds to the perfect privacy constraint; ii. The user is able to decode its demands,$Y_{d_{i}}$, by using$\mathcal{C}$, and the shared key$W$. Here, the encoder sequentially encode each demand$Y_{d_{i}}$at time$i$, using the shared key and previous encoded messages. We propose a variable-length coding scheme that uses privacy-aware compression techniques. We study proposed upper and lower bounds on the average length of$\mathcal{C}$in an example. Finally, we study an application considering cache-aided networks.