Private Variable-Length Coding with Zero Leakage
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914728162361344 |
|---|---|
| author | Zamani, Amirreza Oechtering, Tobias J. Gündüz, Deniz Skoglund, Mikael |
| author_facet | Zamani, Amirreza Oechtering, Tobias J. Gündüz, Deniz Skoglund, Mikael |
| contents | 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 $\cal C$ and sends it over the channel. An adversary is assumed to have access to the output of the encoder, i.e., $\cal 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 $\cal 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 $\cal C$. In two cases we strengthen the existing bounds: 1. $|\mathcal{X}|\geq |\mathcal{Y}|$; 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_19837 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Private Variable-Length Coding with Zero Leakage Zamani, Amirreza Oechtering, Tobias J. Gündüz, Deniz Skoglund, Mikael Information Theory 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 $\cal C$ and sends it over the channel. An adversary is assumed to have access to the output of the encoder, i.e., $\cal 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 $\cal 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 $\cal C$. In two cases we strengthen the existing bounds: 1. $|\mathcal{X}|\geq |\mathcal{Y}|$; 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. |
| title | Private Variable-Length Coding with Zero Leakage |
| topic | Information Theory |
| url | https://arxiv.org/abs/2310.19837 |