Private Variable-Length Coding with Sequential Encoder

A multi-user private data compression problem is studied. A server has access to a database of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N$</tex> files, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(Y_{1},\ldots,\ Y_{N})$</tex>, each of size <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$F$</tex> bits and is connected to an encoder. The encoder is connected through an unsecured link to a user. We assume that each file <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$Y_{i}$</tex> is arbitrarily correlated with a private attribute <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$X$</tex>, 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$W$</tex>. We assume that at each time the user asks for a file <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$Y_{d_{i}}$</tex>, where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(d_{1},\ \ldots,\ d_{K})$</tex> corresponds to the demand vector. The goal is to design the delivered message <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{C}=(\mathcal{C}_{1},\ \ldots,\mathcal{C}_{K})$</tex> after the user send his demands to the encoder such that the average length of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{C}$</tex> is minimized, while satisfying: <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbf{i}$</tex>. The message <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{C}$</tex> does not reveal any information about <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$X$</tex>, i.e., <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$X$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{C}$</tex> are independent, which corresponds to the perfect privacy constraint; ii. The user is able to decode its demands, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$Y_{d_{i}}$</tex>, by using <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{C}$</tex>, and the shared key <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$W$</tex>. Here, the encoder sequentially encode each demand <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$Y_{d_{i}}$</tex> at time <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$i$</tex>, 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{C}$</tex> in an example. Finally, we study an application considering cache-aided networks.