Compression with Privacy-Preserving Random Access

Abstract

We show that an i.i.d.\ binary source sequence $X_1,\dots ,X_n$ can be losslessly compressed at any rate above entropy while ensuring that the decoding of any $X_i$ reveals no information about the remaining symbols $\{X_j:j\ne i\}$. This problem reduces to a marginal consistency problem induced by the simultaneous privacy and reliability constraints. To address it, we develop a technique based on a geometric representation of codeword distributions, which may be of independent interest.

The present version contains significant updates to the proofs and presentation