Entropy-Achieving Compression with Private Local Decodability

A fixed-length compression scheme is said to be locally decodable if any bit of the source sequence can be recovered by probing only a small subset of the compressed bits. A recent work addressed the problem of private locally decodable compression: Is it possible to compress a source Xn such that the compressed bits probed by the local decoder to recover any Xi reveal no information about the remainder of the source sequence Xj:j≠i ? A compression scheme was proposed that achieved a non-trivial rate and private local decoding, but it remained unclear whether the gap to entropy was inherent to the privacy property or not. We show that private local decodability is not a fundamental impediment to compression, and prove the existence of an entropy-achieving compression scheme for i.i.d. bit strings that guarantees the private local decodability of any individual source symbol.