Data Compression with Private Local Decodability

Classical compression schemes suggest that message symbols cannot be privately decoded; if a string Xⁿ is encoded into a codeword C^nR at a non-trivial rate R, then the decoding of an individual symbol X_i reveals information about the rest of the symbols Xⁿ\X_i.While this holds for virtually all lossless compression schemes, it is shown that this need not be the case. This paper proposes a lossless compression scheme for bit strings with the following properties. For any sufficiently small p > 0, it encodes each length-n bit string of Hamming weight at most np into a binary codeword of length O(np log 2 1/p) such that the subset of compressed bits that need to be probed in order to decode a particular message bit reveals no additional information about the other message bits.