Differentially Private Compression and the Sensitivity of LZ77

• URL: http://arxiv.org/abs/2502.09584v2
• Date: Tue, 11 Mar 2025 13:03:39 GMT
• Title: Differentially Private Compression and the Sensitivity of LZ77
• Abstract summary: We study differentially private data-compression schemes motivated by the insecurity of the popular "Compress-Then-Encrypt" framework.<n>In our proposed Differentially Private Compress-Then-Encrypt framework, we add a random positive amount of padding to the compressed file to ensure that any leakage satisfies the rigorous privacy guarantee.<n>Our primary technical contribution is analyzing the fine-grained sensitivity of the LZ77 compression scheme.
• Score: 11.961645395911132
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We initiate the study of differentially private data-compression schemes motivated by the insecurity of the popular "Compress-Then-Encrypt" framework. Data compression is a useful tool which exploits redundancy in data to reduce storage/bandwidth when files are stored or transmitted. However, if the contents of a file are confidential then the length of a compressed file might leak confidential information about the content of the file itself. Encrypting a compressed file does not eliminate this leakage as data encryption schemes are only designed to hide the content of confidential message instead of the length of the message. In our proposed Differentially Private Compress-Then-Encrypt framework, we add a random positive amount of padding to the compressed file to ensure that any leakage satisfies the rigorous privacy guarantee of $(\epsilon,\delta)$-differential privacy. The amount of padding that needs to be added depends on the sensitivity of the compression scheme to small changes in the input, i.e., to what degree can changing a single character of the input message impact the length of the compressed file. While some popular compression schemes are highly sensitive to small changes in the input, we argue that effective data compression schemes do not necessarily have high sensitivity. Our primary technical contribution is analyzing the fine-grained sensitivity of the LZ77 compression scheme (IEEE Trans. Inf. Theory 1977) which is one of the most common compression schemes used in practice. We show that the global sensitivity of the LZ77 compression scheme has the upper bound $\mathcal{O}(W^{2/3}\log n)$ where $W\leq n$ denotes the size of the sliding window. When $W=n$, we show the lower bound $\Omega(n^{2/3}\log^{1/3}n)$ for the global sensitivity of the LZ77 compression scheme which is tight up to a sublogarithmic factor.

Related papers

• LLM-based Source Code Compression via Thresholded Symbol Ranking [1.133608012542551]
  General-purpose compressors (e.g., zstd, bzip2) offer a good trade-off between compression ratio and speed, but fail to exploit all special regularities inherent in source code.<n>Recent approaches leverage Large Language Models (LLMs) within Shannon's symbol-ranking framework.<n>We introduce $T$-bounded compressors deploying two novel symbol-ranking variants that bound predictions to the top-$T$ ranks.
  arXiv  Detail & Related papers  (2026-07-27T09:12:00Z)
• SemanticZip: A Pilot Framework for Lossy Text Compression with LLMs as Semantic Decompressors [0.0]
  We study a more aggressive but explicitly lossy setting: compress text into compact codes that an LLM can expand into task-relevant meaning.<n>Unlike ordinary summarization, SemanticZip does not require byte-identical reconstruction.<n>This paper is a pilot framework, not a benchmark claim.
  arXiv  Detail & Related papers  (2026-05-23T12:14:04Z)
• CompressionAttack: Exploiting Prompt Compression as a New Attack Surface in LLM-Powered Agents [7.68677090046928]
  This work identifies prompt compression as a novel attack surface and presents CompressionAttack, the first framework to exploit it.<n>Experiments on multiple LLMs show up to 80% attack success and 98% preference flips, while remaining highly stealthy and transferable.<n>Case studies in VSCode Cline and Ollama confirm real-world impact, and current defenses prove ineffective.
  arXiv  Detail & Related papers  (2025-10-27T03:37:41Z)
• Transformers from Compressed Representations [74.48571451824569]
  TEMPEST (TransformErs froM comPressed rEpreSenTations) is a method that exploits the inherent byte-stream structure of compressed files to design an effective tokenization and encoding strategy.<n>Our proposal substantially reduces the number of tokens required for semantic classification, thereby lowering both computational complexity and memory usage.
  arXiv  Detail & Related papers  (2025-10-26T13:48:03Z)
• Embedding Compression Distortion in Video Coding for Machines [67.97469042910855]
  Currently, video transmission serves not only the Human Visual System (HVS) for viewing but also machine perception for analysis. We propose a Compression Distortion Embedding (CDRE) framework, which extracts machine-perception-related distortion representation and embeds it into downstream models. Our framework can effectively boost the rate-task performance of existing codecs with minimal overhead in terms of execution time, and number of parameters.
  arXiv  Detail & Related papers  (2025-03-27T13:01:53Z)
• ChunkKV: Semantic-Preserving KV Cache Compression for Efficient Long-Context LLM Inference [61.412894960600205]
  Large Language Models (LLMs) require significant GPU memory when processing long texts.<n>ChunkKV reimagines KV cache compression by treating semantic chunks as basic compression units.<n>Result: ChunkKV outperforms state-of-the-art methods by up to 8.7% in precision.
  arXiv  Detail & Related papers  (2025-02-01T03:49:47Z)
• UNComp: Can Matrix Entropy Uncover Sparsity? -- A Compressor Design from an Uncertainty-Aware Perspective [85.08718140718707]
  UNComp is an uncertainty-aware framework that uncovers sparsity patterns that can be used for adaptive compression.<n>By focusing on uncertainty to analyze the sparsity pattern in detail, UNComp reduces the KV cache size to 4.74% of the original, achieves a 6% prefill speedup, and improves throughput by 6.4x.
  arXiv  Detail & Related papers  (2024-10-04T02:32:36Z)
• Understanding is Compression [18.747845226548456]
  6G communication speed requirement raises open question for revolutionary new ideas of data compression. We show large language models (LLMs) understand data better than ever before. We present LMCompress, which shatters all previous compression algorithms.
  arXiv  Detail & Related papers  (2024-06-24T03:58:11Z)
• UniCompress: Enhancing Multi-Data Medical Image Compression with Knowledge Distillation [59.3877309501938]
  Implicit Neural Representation (INR) networks have shown remarkable versatility due to their flexible compression ratios. We introduce a codebook containing frequency domain information as a prior input to the INR network. This enhances the representational power of INR and provides distinctive conditioning for different image blocks.
  arXiv  Detail & Related papers  (2024-05-27T05:52:13Z)
• LLMLingua-2: Data Distillation for Efficient and Faithful Task-Agnostic Prompt Compression [43.048684907893104]
  This paper focuses on task-agnostic prompt compression for better generalizability and efficiency. We formulate prompt compression as a token classification problem to guarantee the faithfulness of the compressed prompt to the original one. Our approach leads to lower latency by explicitly learning the compression objective with smaller models such as XLM-RoBERTa-large and mBERT.
  arXiv  Detail & Related papers  (2024-03-19T17:59:56Z)
• MISC: Ultra-low Bitrate Image Semantic Compression Driven by Large Multimodal Model [78.4051835615796]
  This paper proposes a method called Multimodal Image Semantic Compression. It consists of an LMM encoder for extracting the semantic information of the image, a map encoder to locate the region corresponding to the semantic, an image encoder generates an extremely compressed bitstream, and a decoder reconstructs the image based on the above information. It can achieve optimal consistency and perception results while saving perceptual 50%, which has strong potential applications in the next generation of storage and communication.
  arXiv  Detail & Related papers  (2024-02-26T17:11:11Z)
• HE is all you need: Compressing FHE Ciphertexts using Additive HE [29.043858170208875]
  Homomorphic Encryption (HE) is a commonly used tool for building privacy-preserving applications. We present a new compression technique that uses an additive homomorphic encryption scheme with small ciphertexts to compress large homomorphic ciphertexts.
  arXiv  Detail & Related papers  (2023-03-16T02:28:40Z)
• Deep Lossy Plus Residual Coding for Lossless and Near-lossless Image Compression [85.93207826513192]
  We propose a unified and powerful deep lossy plus residual (DLPR) coding framework for both lossless and near-lossless image compression. We solve the joint lossy and residual compression problem in the approach of VAEs. In the near-lossless mode, we quantize the original residuals to satisfy a given $ell_infty$ error bound.
  arXiv  Detail & Related papers  (2022-09-11T12:11:56Z)
• Towards Robust Data Hiding Against (JPEG) Compression: A Pseudo-Differentiable Deep Learning Approach [78.05383266222285]
  It is still an open challenge to achieve the goal of data hiding that can be against these compressions. Deep learning has shown large success in data hiding, while non-differentiability of JPEG makes it challenging to train a deep pipeline for improving robustness against lossy compression. In this work, we propose a simple yet effective approach to address all the above limitations at once.
  arXiv  Detail & Related papers  (2020-12-30T12:30:09Z)
• What's in the Image? Explorable Decoding of Compressed Images [45.22726784749359]
  We develop a novel decoder architecture for the ubiquitous JPEG standard, which allows traversing the set of decompressed images. We exemplify our framework on graphical, medical and forensic use cases, demonstrating its wide range of potential applications.
  arXiv  Detail & Related papers  (2020-06-16T17:15:44Z)
• Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor [5.09755285351264]
  We consider an unbiased compression method inspired by the Kashin representation of vectors, which we call em Kashin compression (KC). KC enjoys a em dimension independent variance bound for which we derive an explicit formula even in the regime when only a few bits need to be communicate per each vector entry.
  arXiv  Detail & Related papers  (2020-02-20T17:20:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.