論文の概要: Differentially Private Compression and the Sensitivity of LZ77

• arxiv url: http://arxiv.org/abs/2502.09584v2
• Date: Tue, 11 Mar 2025 13:03:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-12 15:38:35.476417
• Title: Differentially Private Compression and the Sensitivity of LZ77
• Title（参考訳）: LZ77の差分圧縮と感度
• Authors: Jeremiah Blocki, Seunghoon Lee, Brayan Sebastián Yepes Garcia,
• Abstract要約: 我々は、人気のある"Compress-Then-Encrypt"フレームワークの安全性の欠如を動機とする、差分プライベートなデータ圧縮方式について検討する。 提案した差分圧縮-Then-Encryptフレームワークでは、圧縮されたファイルにランダムな正のパディングを加え、漏洩が厳密なプライバシー保証を満たすことを保証する。 我々の主な技術的貢献は、LZ77圧縮スキームの微粒化感度を分析することである。
• 参考スコア（独自算出の注目度）: 11.961645395911132
• License:
• 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.
• Abstract（参考訳）: 我々は,人気の高い"Compress-Then-Encrypt"フレームワークの安全性の欠如を動機とする,差分プライベートなデータ圧縮方式の研究を開始する。 データ圧縮は、ファイルの保存や送信時にストレージ/帯域幅を減らすためにデータの冗長性を利用する便利なツールである。 しかし、もしファイルの内容が秘密であるなら、圧縮されたファイルの長さは、ファイル自体の内容に関する機密情報を漏洩させる可能性がある。 データ暗号化スキームは、メッセージの長さではなく機密メッセージの内容を隠すように設計されているため、圧縮されたファイルの暗号化は、この漏洩を排除しない。 提案した差分圧縮-Then-Encryptフレームワークでは、圧縮されたファイルにランダムな正のパディングを加えて、リークが厳格なプライバシー保証である$(\epsilon,\delta)$-differential Privacyを満たすようにします。 追加が必要なパディングの量は、入力の小さな変更に対する圧縮スキームの感度、すなわち、どの程度に入力メッセージの単一文字を変更できるかによって圧縮されたファイルの長さに影響を与える。 いくつかの一般的な圧縮スキームは入力の小さな変化に対して非常に敏感であるが、有効なデータ圧縮スキームは必ずしも高感度であるとは限らないと論じる。 我々の主な技術的貢献は、LZ77圧縮スキーム(IEEE Trans. Inf. Theory 1977)の微粒化感度の分析である。 LZ77圧縮スキームのグローバル感度は上界$\mathcal{O}(W^{2/3}\log n)$であり、$W\leq n$はスライドウィンドウのサイズを表す。 W=n$のとき、LZ77圧縮スキームの大域的な感度に対して、下界の$\Omega(n^{2/3}\log^{1/3}n)$を示す。

関連論文リスト

• Concise and Precise Context Compression for Tool-Using Language Models [60.606281074373136]
  ツールを用いた言語モデルにおいて,ツール文書を簡潔かつ高精度な要約シーケンスに圧縮する2つの手法を提案する。 API-BankとAPIBenchの結果,最大16倍の圧縮率で上行ベースラインに匹敵する性能を示した。
  論文  参考訳（メタデータ） (2024-07-02T08:17:00Z)
• Understanding is Compression [18.747845226548456]
  6G通信速度要件は、データ圧縮の革新的な新しいアイデアに対して、オープンな疑問を提起する。 大規模な言語モデル(LLM)は、これまで以上にデータをよりよく理解しています。 従来の圧縮アルゴリズムを全て破壊するLMCompressを提案する。
  論文  参考訳（メタデータ） (2024-06-24T03:58:11Z)
• UniCompress: Enhancing Multi-Data Medical Image Compression with Knowledge Distillation [59.3877309501938]
  Inlicit Neural Representation (INR) ネットワークは、その柔軟な圧縮比のため、顕著な汎用性を示している。 周波数領域情報を含むコードブックをINRネットワークへの事前入力として導入する。 これにより、INRの表現力が向上し、異なる画像ブロックに対して特異な条件付けが提供される。
  論文  参考訳（メタデータ） (2024-05-27T05:52:13Z)
• LLMLingua-2: Data Distillation for Efficient and Faithful Task-Agnostic Prompt Compression [43.048684907893104]
  本稿では, タスク非依存のプロンプト圧縮に着目し, 一般化性と効率性の向上を図る。 我々は,プロンプト圧縮をトークン分類問題として定式化し,圧縮されたプロンプトが元のプロンプトに忠実であることを保証する。 提案手法は, XLM-RoBERTa-large や mBERT などの小型モデルを用いて圧縮目標を明示的に学習することにより,低レイテンシを実現する。
  論文  参考訳（メタデータ） (2024-03-19T17:59:56Z)
• MISC: Ultra-low Bitrate Image Semantic Compression Driven by Large Multimodal Model [78.4051835615796]
  本稿では,マルチモーダル画像セマンティック圧縮法を提案する。 画像の意味情報を抽出するLMMエンコーダと、その意味に対応する領域を特定するマップエンコーダと、非常に圧縮されたビットストリームを生成する画像エンコーダと、前記情報に基づいて画像を再構成するデコーダとからなる。 知覚50%を節約しながら最適な一貫性と知覚結果を達成することができ、これは次世代のストレージと通信において強力な可能性を持つ。
  論文  参考訳（メタデータ） (2024-02-26T17:11:11Z)
• HE is all you need: Compressing FHE Ciphertexts using Additive HE [29.043858170208875]
  ホモモルフィック暗号化(HE)は、プライバシ保護アプリケーションを構築するための一般的なツールである。 そこで本研究では,大規模な同型暗号文を圧縮するために,小さな暗号文を含む付加的同型暗号方式を用いた新しい圧縮手法を提案する。
  論文  参考訳（メタデータ） (2023-03-16T02:28:40Z)
• Deep Lossy Plus Residual Coding for Lossless and Near-lossless Image Compression [85.93207826513192]
  本稿では、損失のない画像圧縮とほぼロスレス画像圧縮の両面において、統合された強力な深い損失+残差(DLPR)符号化フレームワークを提案する。 VAEのアプローチにおける連立損失と残留圧縮の問題を解く。 ほぼロスレスモードでは、元の残差を量子化し、与えられた$ell_infty$エラー境界を満たす。
  論文  参考訳（メタデータ） (2022-09-11T12:11:56Z)
• Towards Robust Data Hiding Against (JPEG) Compression: A Pseudo-Differentiable Deep Learning Approach [78.05383266222285]
  これらの圧縮に対抗できるデータ隠蔽の目標を達成することは、依然としてオープンな課題である。 ディープラーニングはデータの隠蔽に大きな成功を収めていますが、JPEGの非差別化性は、損失のある圧縮に対する堅牢性を改善するための深いパイプラインのトレーニングを困難にしています。 本稿では,上記の制約をすべて一度に解決するための,単純かつ効果的なアプローチを提案する。
  論文  参考訳（メタデータ） (2020-12-30T12:30:09Z)
• What's in the Image? Explorable Decoding of Compressed Images [45.22726784749359]
  ユビキタスJPEG標準のための新しいデコーダアーキテクチャを開発し、圧縮された画像の集合をトラバースする。 我々は、グラフィカル、医学的、法医学的なユースケースに関する我々のフレームワークを例示し、その幅広い潜在的な応用を実証する。
  論文  参考訳（メタデータ） (2020-06-16T17:15:44Z)
• Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor [5.09755285351264]
  我々は,ベクトルのカシン表現にインスパイアされた非バイアス圧縮法を考察し,これをエムカシン圧縮(KC)と呼ぶ。 KC は、各ベクトルエントリごとに数ビットしか通信する必要のない状態であっても、明示的な公式を導出するエム次元独立分散境界を享受する。
  論文  参考訳（メタデータ） (2020-02-20T17:20:51Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。