Private Variable-Length Coding with Zero Leakage

• Main Authors: Zamani, Amirreza, Oechtering, Tobias J., Gunduz, Deniz, Skoglund, Mikael
• Format: Conference Proceeding
• Language: English
• Subjects: Codes; Conferences; Encoding; Entropy; Forensics; Privacy; Upper bound
• ISSN: 2157-4774
• DOI: 10.1109/WIFS58808.2023.10374696

A private compression design problem is studied, where an encoder observes useful data Y , wishes to compress it using variable length code and communicates it through an unsecured channel. Since Y is correlated with private attribute X , the encoder uses a private compression mechanism to design encoded message \mathcal{C} and sends it over the channel. An adversary is assumed to have access to the output of the encoder, i.e., \mathcal{C} , and tries to estimate X . Furthermore, it is assumed that both encoder and decoder have access to a shared secret key W . The design goal is to encode message \mathcal{C} with minimum possible average length that satisfies a perfect privacy constraint. To do so we first consider two different privacy mechanism design problems and find upper bounds on the entropy of the optimizers by solving a linear program. We use the obtained optimizers to design \mathcal{C} . In two cases we strengthen the existing bounds: 1. \vert \mathcal{X}\vert \geq\vert \mathcal{Y}\vert; 2 . The realization of (X,\ Y) follows a specific joint distribution. In particular, considering the second case we use two-part construction coding to achieve the upper bounds. Furthermore, in a numerical example we study the obtained bounds and show that they can improve the existing results.