Perfectly Private Lossless Variable-Length Coding With a Sequential Encoder
Abstract
A lossless data compression problem with a privacy constraint is studied where a server has access to a database of <inline-formula> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula> files, <inline-formula> <tex-math notation="LaTeX">$(Y_{1},\ldots,Y_{N})$ </tex-math></inline-formula>, each of size <inline-formula> <tex-math notation="LaTeX">$F$ </tex-math></inline-formula> bits and is connected to an encoder. The encoder is connected through an unsecured public link to a user. We assume that each file <inline-formula> <tex-math notation="LaTeX">$Y_{i}$ </tex-math></inline-formula> is arbitrarily correlated with a private attribute <inline-formula> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula>, which is assumed to be accessible by the encoder. Moreover, an adversary is assumed to have access to the public link. The user and the encoder have access to a shared secret key <inline-formula> <tex-math notation="LaTeX">$W$ </tex-math></inline-formula>. We assume that at each time the user asks for a file <inline-formula> <tex-math notation="LaTeX">$Y_{d_{i}}$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$(d_{1},\ldots,d_{K})$ </tex-math></inline-formula> corresponds to the demand vector. The goal is to design the delivered message <inline-formula> <tex-math notation="LaTeX">$\mathcal {C}=(\mathcal {C}_{1},\ldots,\mathcal {C}_{K})$ </tex-math></inline-formula> after the user sends the demands to the encoder such that the average length of <inline-formula> <tex-math notation="LaTeX">$\mathcal {C}$ </tex-math></inline-formula> is minimized, while satisfying: i. The message <inline-formula> <tex-math notation="LaTeX">$\cal C$ </tex-math></inline-formula> does not reveal any information about <inline-formula> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula> yielding <inline-formula> <tex-math notation="LaTeX">$I(X;\mathcal {C})=0$ </tex-math></inline-formula>, which corresponds to the perfect privacy constraint; ii. The user is able to decode its demands, <inline-formula> <tex-math notation="LaTeX">$Y_{d_{i}}$ </tex-math></inline-formula>, without any loss by using <inline-formula> <tex-math notation="LaTeX">$\cal C$ </tex-math></inline-formula> and the shared key <inline-formula> <tex-math notation="LaTeX">$W$ </tex-math></inline-formula>, i.e., <inline-formula> <tex-math notation="LaTeX">$H(Y_{d_{i}}|\mathcal {C},W)=0$ </tex-math></inline-formula>. Here, the encoder sequentially encodes each demand <inline-formula> <tex-math notation="LaTeX">$Y_{d_{i}}$ </tex-math></inline-formula> at time <inline-formula> <tex-math notation="LaTeX">$i$ </tex-math></inline-formula>, using the shared key, the database, the private attribute, and the previous demands. We propose a recursive coding framework with three constructions for generating the privacy-preserving auxiliary variables. In all designs, we use a multi-part code construction in which <inline-formula> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula> is concealed using a one-time pad scheme. In the first design, we employ an extension of the Functional Representation Lemma (FRL). We then improve this scheme by using minimum-entropy functional representation. In a special case, we further enhance both schemes using the concept of Wyner’s common information. We study the tightness of the proposed approaches by deriving lower bounds and comparing them with the upper bounds in an example. Finally, we study an application considering a cache-aided network with a limited-buffer encoder, in which the sequential encoding scheme can be applied.