Compression with Privacy-Preserving Random Access The work of Shashank Vatedka was supported by a Core Research Grant CRG/2022/004464 from SERB, India.

Venkat Chandar, Aslan Tchamkerten, Shashank Vatedka · 2025

Read Compression with Privacy-Preserving Random Access The work of Shashank Vatedka was supported by a Core Research Grant CRG/2022/004464 from SERB, India. by Venkat Chandar, Aslan Tchamkerten, Shashank Vatedka (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-14524.txt.

Introduction

Venkat Chandar, Aslan Tchamkerten, and Shashank Vatedka prove a compression result with a strong privacy demand. A binary source must be stored in compressed form above its entropy rate. At the same time, decoding any single symbol must reveal nothing about all the others. That joint demand creates a delicate consistency problem for code distributions.

The authors solve it with a geometric view of how codeword probabilities are arranged. Their method shows lossless recovery is still possible under the privacy rule. The geometric technique may help in other coding problems as well. The result separates the cost of privacy from the cost of compression in this basic source setting.

Catalog record

CREATORVenkat Chandar, Aslan Tchamkerten, Shashank Vatedka
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE82 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-14524

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Compression with Privacy-Preserving Random Access The work of Shashank Vatedka was supported by a Core Research Grant CRG/2022/004464 from SERB, India. Venkat Chandar, Aslan Tchamkerten, Shashank Vatedka Abstract It is shown that an i.i.d. binary source sequence X 1 , … , X n X_{1},\ldots,X_{n} can be losslessly compressed at any rate above entropy such that the individual decoding of any X i X_{i} reveals no information about the other bits { X j : j ≠ i } \{X_{j}:j\neq i\} . † † aftertitle: I Introduction Several recent works have studied compression with locality properties [ 12 , 14 , 2 , 22 , 17 , 23 , 27 , 26 , 11 , 24 , 29 ] , focusing on encoding and decoding primitives, and on algorithms and information-theoretic limits that characterize the minimum number of bits that must be accessed or updated to locally decode or modify a source symbol. In [ 3 ] , we introduced the problem of compression with private local decoding (also referred to as privacy-preserving random access ): can a binary source sequence {\bm{X}}=(X_{1},\ldots,X_{n}) (1) be losslessly compressed into a codeword C_{1},C_{2},\ldots,C_{nR} such that the local decoding of any X_{i} depends only on a subset of codeword symbols {\bm{C}}_{\mathcal{I}_{i}}\overset{\text{def}}{=}\{C_{j}:j\in\mathcal{I}_{i}\} , for some \mathcal{I}_{i}\subseteq[nR] , and reveals no information about the remaining source symbols \{X_{j}:j\neq i\} ? To ensure reliability, the codeword bits {\bm{C}}_{\mathcal{I}_{i}} accessed by local decoder i must enable a reliable distinction between the hypotheses X_{i}=0 and X_{i}=1 . To ensure privacy, these accessed bits must be independent of all other source symbols \{X_{j}:j\neq i\} . The challenge stems from compression; some codeword subsets {\bm{C}}_{\mathcal{I}_{i}} and {\bm{C}}_{\mathcal{I}_{j}} must overlap which potentially compromises local privacy. Somewhat counterintuitively, we showed that for an i.i.d. \mathrm{Bernoulli}(p) source, such a scheme exists and achieves a nontrivial compression rate R=c\,p\,\log^{2}\!\left(\tfrac{1}{p}\right), (2) for a universal constant c>0 and sufficiently small p (all logarithms are base two). However, it remained unclear whether the gap to the entropy H(p)\overset{\text{def}}{=}-p\log p-(1-p)\log(1-p) (3) is intrinsic to the privacy constraint. In particular, the scheme exhibits a multiplicative gap of order \log(1/p) in the small- p regime. In this paper, we show that for any i.i.d. \mathrm{Bernoulli} source, private local decoding does not fundamentally limit compression; there exist schemes that achieve private local decoding at any rate above entropy. The present paper provides the full version of the conference paper [ 4 ] which only sketched parts of the proofs of some of the results. Most recently, paper [ 9 ] proposed a simple low complexity scheme that achieves entropy with private local decoding for any i.i.d. source, not necessarily binary. The scheme mainly relies on concatenation: the parsing of the n -length source sequence into blocks of size \log n , which renders the scheme inherently asymptotic. The scheme provided in this paper does not rely on concatenation, and the techniques developed here—particularly those used to handle overlaps between the subsets \{{\bm{C}}_{\mathcal{I}_{i}}\} —form a central component of our approach and may be of independent interest. The objective is to compress a source sequence \bm{x} into a random nR -bit codeword {\bm{C}} such that each marginal {\bm{C}}_{\mathcal{I}_{i}} is independent of \{x_{j}:j\neq i\} while enabling reliable recovery of x_{i} . A key step is to show that these marginal constraints can be simultaneously satisfied through a joint codeword distribution, an instance of the classical marginal problem [ 6 ] . Existing methods are inconclusive in our setting, so we develop a technique that leverages a geometric representation of codeword distributions—the block marginal polytope —to prove, through a sequence of distribution perturbations, the existence of a codeword distribution that satisfies the marginal constraints. This perturbative approach may be of broader interest for tackling related variants of the marginal problem. Related Works Makhdoumi et al. [ 13 ] initiated the study of locally decodable source coding for random sequences in the information theory community. Mazumdar et al. [ 16 ] proposed a fixed-blocklength, entropy-achieving compression scheme that enables efficient local decoding of individual source bits. For a memoryless source P , they designed a rate- H(P)+\varepsilon compressor for which the decoding of a single bit requires probing only \Theta\!\left(\tfrac{1}{\varepsilon}\log\tfrac{1}{\varepsilon}\right) bits of the compressed codeword. They further showed that, for non-dyadic sources, any locally decodable compression scheme operating at rate H(P)+\varepsilon must probe at least \Omega(\log(1/\varepsilon)) bits of the compressed representation to achieve an o(1) probability of error in recovering any source symbol. Tatwawadi et al. [ 21 ] extended this achievability result to Markov sources and proposed a universal scheme in which the local decoder probes \Theta\!\left(\tfrac{1}{\varepsilon^{2}}\log\tfrac{1}{\varepsilon}\right) bits to recover any individual source bit. All of the above works in the bit-probe model consider fixed-length block coding. Variable-length source coding under local decodability constraints was studied by Pananjady and Courtade [ 18 ] , who established upper and lower bounds on the achievable compression rate for sparse sequences. Simultaneous local decoding and re-encoding was investigated by Vatedka et al. [ 25 ] , who designed compression schemes for which the average number of compressed bits that must be probed or updated for local decoding and re-encoding of a single source bit (for a memoryless source) is constant and independent of n . A distinct line of research considers locality in the context of channel coding, where each codeword symbol must be recoverable from a small subset of other codeword symbols; see, for instance, [ 28 , 7 , 20 , 1 , 15 , 19 ] and references therein. Paper organization Section II introduces the problem formulation and states the main result, Theorem 1 . Section III describes the compression scheme used to prove Theorem 1 . The remainder of the paper is devoted to the analysis underlying this result. Section IV develops a representation of codeword distributions that is instrumental to the subsequent arguments. Sections V , VI , and VII contain the proofs of the key intermediate results leading to Theorem 1 . Finally, Section VIII provides concluding remarks. II Problem Statement and Main Result Throughout the paper, we consider the compression of an i.i.d. Bernoulli( p ) bit string {\bm{X}}=X_{1},\ldots,X_{n} with parameter p=\mathrm{Pr}(X_{1}=1)\in(0,1/2) . We recall the notion of private local decodability [ 3 ] : Definition 1 (Locally decodable code) . Given an integer n\geq 1 and a constant R>0 , a rate- R locally decodable code {\cal{C}}_{n} consists of: • an encoder which maps each length-n bit string {\bm{x}} to a random nR -bit codeword 1 1 1 We write {nR} to mean \lceil nR\rceil . {\bm{C}}=C_{1},\ldots,C_{nR} according to a distribution P_{{\bm{C}}|{\bm{x}}} ; • a set of n deterministic decoding functions \{f_{i}:1\leq i\leq n\} where each function f_{i}:\{0,1\}^{|\mathcal{I}_{i}|}\to\{0,1\} takes as input a set of codeword components {\bm{C}}_{\mathcal{I}_{i}}\overset{\text{def}}{=}\{C_{j}:j\in\mathcal{I}_{i}\} indexed by some set of indices \mathcal{I}_{i}\subseteq\{1,2,\ldots,n\}, and outputs an estimate \hat{X}_{i}\overset{\text{def}}{=}f_{i}({\bm{C}}_{\mathcal{I}_{i}}). Definition 2 (Error probability and privacy) . The error probability of a rate- R locally decodable code {\cal{C}}_{n} is defined as P_{e}^{(n)}\overset{\text{def}}{=}\mathrm{Pr}(\hat{{\bm{X}}}\neq{\bm{X}}), where \hat{{\bm{X}}}\overset{\text{def}}{=}\hat{X}_{1},\ldots,\hat{X}_{n} denotes the concatenation of the estimates of the n local decoders, and where the probability is with respect to the randomness of the source and the randomness of the encoding, that is \mathrm{Pr}(\hat{{\bm{X}}}\neq{\bm{X}})=\sum_{{\bm{x}}}P_{{\bm{X}}}({\bm{x}})\sum_{{{\bm{c}}}:\hat{{\bm{x}}}({\bm{c}})\neq{\bm{x}}}P_{{\bm{C}}|{\bm{X}}}({\bm{c}}|{\bm{x}}). The code is said to be locally privately decodable (or simply private ) if \displaystyle

Read the complete text