Technical Summary: Compression with Privacy-Preserving Random Access

1. Problem Statement

The paper addresses the problem of lossless compression of an i.i.d. binary source $X = (X_1, \dots, X_n)$ with the dual constraints of reliability and local privacy. The goal is to encode the source into a codeword $C$ of length $nR$ such that:

1. Reliability: Any source symbol $X_i$ can be reliably recovered by a local decoder accessing only a small subset of codeword bits $C_{I_i}$ (where $I_i \subset \{1, \dots, nR\}$).
2. Privacy: The subset of accessed bits $C_{I_i}$ must reveal no information about the remaining source symbols $X_{-i} = \{X_j : j \neq i\}$. Formally, $C_{I_i}$ must be independent of $X_{-i}$ conditioned on $X_i$.

The central challenge arises because compression necessitates overlap between the subsets $I_i$ and $I_j$ for different indices $i, j$. Such overlaps create a risk that bits accessed by decoder $i$ inadvertently leak information about $X_j$, violating the privacy constraint.

Previous work [12] demonstrated that for Bernoulli($p$) sources with small $p$, such schemes exist but with a rate $R$ that is strictly larger than the entropy $H(p)$ by a multiplicative factor of order $\log(1/p)$. A subsequent scheme [14] achieved entropy-rate compression using a "permute-and-compress" approach with amortized permutation costs, but this relied on asymptotic "chunking" (block lengths of $\log n$) and decoupled privacy from compression via a random permutation key.

The Core Question: Is the gap between the achievable rate and the source entropy intrinsic to the privacy constraint, or can private local decoding be achieved at any rate above entropy without relying on asymptotic chunking or external keys?

2. Methodology and Technical Approach

The authors propose a constructive existence proof based on random coding and a novel geometric representation of probability distributions.

A. Random Decoder Ensemble

The scheme employs a random decoder defined by a bipartite graph $G$ and decoding functions $f$:

• Graph Structure: Each of the $n$ local decoders is connected to a random subset of $b = \Theta(\log n)$ codeword bits.
• Decoding Function: Each local decoder computes a syndrome $S$ of the accessed bits using a Simplex code (dual of a Hamming code) and then applies a random binary mapping.
• Key Property: The use of the Simplex code syndrome ensures that the output of any local decoder cannot be determined by any two coordinates of its input. This limits the information leakage through overlaps, as the intersection of any two access sets $|I_i \cap I_j|$ is small (at most 2 with high probability).

B. Block-Marginal Polytope Representation

The core technical innovation is the use of the block-marginal polytope ($P_G$) to handle the simultaneous satisfaction of privacy and reliability constraints.

• Definition: Instead of constructing a joint distribution over the entire codeword directly, the authors define a vector $\phi$ representing the set of marginal distributions on the access sets $\{C_{I_i}\}$.
• Feasibility: A vector $\phi$ is "generatable" (i.e., $\phi \in P_G$) if there exists a joint codeword distribution that induces these specific marginals.
• The Strategy: The proof demonstrates that a specific "approximate" block-marginal vector, $\phi_{A,x}$, is generatable with high probability. This vector is a convex combination of:
  1. The Ideal Vector ($\phi_{I,x}$): Represents perfect reliability (decoding $X_i$ correctly) and perfect privacy (marginals depend only on $X_i$), but is difficult to generate directly.
  2. The Uniform Vector ($\phi_U$): Represents a completely random codeword (trivially private but unreliable), which is always generatable.

By showing that $\phi_{A,x} = \frac{n}{n+1}\phi_{I,x} + \frac{1}{n+1}\phi_U$ lies within the generatable set $P_G$, the authors prove the existence of a code that is private and has vanishing error probability.

C. Handling Overlaps (The Marginal Problem)

To prove that $\phi_{A,x} \in P_G$, the authors solve a marginal consistency problem. They construct a joint distribution through a three-stage perturbation of the uniform distribution:

1. Bit Marginals: Adjust the uniform distribution to match the required single-bit marginals.
2. Bit-Pair Marginals: Further adjust to match pairwise marginals. The condition $|I_i \cap I_j| \le 2$ is crucial here; it ensures that once bit-pair marginals are fixed, the block marginals can be adjusted independently without conflict.
3. Block Marginals: Final adjustment to match the full block marginals required for the code.

This constructive approach relies on the fact that the perturbations required to satisfy the constraints are small enough to maintain the non-negativity of the probability mass function.

3. Key Results

Theorem 1 (Main Result):
For any i.i.d. Bernoulli($p$) source with $0 < p \le 1/2$ and any rate $R > H(p)$, there exists a sequence of compression schemes that are:

• Locally Privately Decodable: The accessed bits for any $X_i$ are independent of $X_{-i}$.
• Reliable: The probability of decoding error vanishes as $n \to \infty$.
• Rate-Optimal: The scheme achieves any rate strictly above the entropy, closing the gap found in previous works.

Extension to Non-Binary Sources:
The result extends to non-binary i.i.d. sources by encoding the binary representation of each symbol independently. The achievable rate approaches $\sum H(p_\ell)$, which can be strictly less than $\log |\mathcal{X}|$ depending on the source distribution and binary labeling.

Distortion vs. Zero-Error:
The primary construction achieves small average distortion (Hamming distance) with high probability. The paper then employs a secondary compression step (re-encoding the error vector) using a result from [12] to achieve zero-error lossless compression while maintaining privacy.

4. Significance and Claims

The paper claims to resolve the question of whether privacy constraints inherently limit compression efficiency for local decoding.

• Closing the Gap: It demonstrates that the multiplicative gap to entropy observed in [12] is not intrinsic to the privacy constraint. Private local decoding can be achieved at any rate above entropy.
• Joint Optimization: Unlike the "permute-and-compress" scheme in [14], which effectively decouples privacy from compression by using a random permutation as a key, the proposed scheme jointly handles compression and privacy. It addresses the overlaps between access subsets directly through the geometric properties of the block-marginal polytope.
• Independent Interest: The technique of using a geometric representation (block-marginal polytope) to prove the existence of a joint distribution satisfying specific marginal constraints is presented as a tool of independent interest for related problems in the classical marginal problem.

5. Limitations and Open Problems

The authors note several limitations and open directions:

• Asymptotic Nature: The scheme is asymptotic; the block length $n$ must grow large for the rate to approach entropy and for the probabilistic arguments to hold.
• Explicit Construction: The proof is non-constructive regarding the specific encoder/decoder pair (it proves existence via random coding). Finding an explicit, efficient, and non-asymptotic scheme remains an open problem.
• Locality: The current scheme has a locality of $b = \Theta(\log n)$. It is an open question whether constant locality (independent of $n$) is achievable with privacy.
• Memory: The results are currently limited to memoryless (i.i.d.) sources; extending this to sources with memory is an open area of research.