Compression with privacy keeps data safe for sources with memory

Compression of Sources with Memory and Private Random Access

Information Theory

Summary

The paper studies how to compress sequences of information while keeping each piece private during access. The authors show that for data coming from processes with memory (like stationary sources), you can compress efficiently while still keeping access to each piece private and accurate most of the time. However, if the source is more complex and not predictable (non-ergodic), there is a cost in compression rate to maintain this privacy. This work extends previous results that were only known for memoryless data sources.

What this means in practice

  • For data storage engineers: Implement storage systems that allow private retrieval of individual data symbols without leaking other data information, improving privacy guarantees with minimal storage overhead.
  • For network security teams: Design communication protocols that compress data streams with memory while ensuring privacy during local decoding at receivers, reducing bandwidth without sacrificing security.

A theory result. No direct application yet.

Authors

Venkat Chandar, Aslan Tchamkerten, Shashank Vatedka

Abstract

Private local decoding imposes a stringent constraint on compression: the codeword bits used to recover a source symbol must reveal nothing about the remaining symbols beyond what the recovered symbol itself reveals. For memoryless sources, this constraint is known to be compatible with entropy-rate compression. We show that the same holds for any stationary ergodic source over a finite alphabet. Specifically, every rate above the entropy rate is achievable with exact privacy and error-free local decoding on a set of source sequences whose probability tends to one. In contrast, we exhibit non-ergodic sources for which private local decoding incurs a strictly positive rate penalty.