論文の概要: Securing Unbounded Differential Privacy Against Timing Attacks

• arxiv url: http://arxiv.org/abs/2506.07868v1
• Date: Mon, 09 Jun 2025 15:35:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-10 21:10:47.149993
• Title: Securing Unbounded Differential Privacy Against Timing Attacks
• Title（参考訳）: タイムアタックに対する差別的プライバシーの保護
• Authors: Zachary Ratliff, Salil Vadhan,
• Abstract要約: 非有界設定における純粋な JOT-DP に必要な誤差は計算モデルに依存することを示す。 上界設定の純 JOT-DP プログラム $P'$ を非有界設定の純 JOT-DP プログラム $P'$ に変換する効率的な手順によりこれを証明する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent works have started to theoretically investigate how we can protect differentially private programs against timing attacks, by making the joint distribution the output and the runtime differentially private (JOT-DP). However, the existing approaches to JOT-DP have some limitations, particularly in the setting of unbounded DP (which protects the size of the dataset and applies to arbitrarily large datasets). First, the known conversion of pure DP programs to pure JOT-DP programs in the unbounded setting (a) incurs a constant additive increase in error probability (and thus does not provide vanishing error as $n\to\infty$) (b) produces JOT-DP programs that fail to preserve the computational efficiency of the original pure DP program and (c) is analyzed in a toy computational model in which the runtime is defined to be the number of coin flips. In this work, we overcome these limitations. Specifically, we show that the error required for pure JOT-DP in the unbounded setting depends on the model of computation. In a randomized RAM model where the dataset size $n$ is given (or can be computed in constant time) and we can generate random numbers (not just random bits) in constant time, polynomially small error probability is necessary and sufficient. If $n$ is not given or we only have a random-bit generator, an (arbitrarily small) constant error probability is necessary and sufficient. The aforementioned positive results are proven by efficient procedures to convert any pure JOT-DP program $P$ in the upper-bounded setting to a pure JOT-DP program $P'$ in the unbounded setting, such that the output distribution of $P'$ is $\gamma$-close in total variation distance to that of $P$, where $\gamma$ is either an arbitrarily small constant or polynomially small, depending on the model of computation.
• Abstract（参考訳）: 最近の研究は、共同分布を出力とし、実行時を独立にプライベートにする(JOT-DP)ことで、時間的攻撃に対して微分プライベートプログラムをいかに保護できるかを理論的に検討し始めている。 しかし、既存の JOT-DP のアプローチにはいくつかの制限があり、特に非有界 DP (データセットのサイズを保護し、任意に大きなデータセットに適用する) の設定には制限がある。 第一に、非有界環境における純粋DPプログラムの純粋なJOT-DPプログラムへの変換について (a) 誤差確率の一定加法的増加を生じさせる(従って$n\to\infty$として消滅誤差を与えない) (b)元の純DPプログラムの計算効率の維持に失敗したJOT-DPプログラムを作成し、 (c)は、ランタイムがコインフリップ数として定義される玩具計算モデルで解析される。 この作業では、これらの制限を克服します。 具体的には、非有界環境での純粋なJOT-DPに必要な誤差が計算モデルに依存することを示す。 データセットサイズ$n$が与えられる(あるいは一定時間で計算できる)ランダム化RAMモデルでは、一定時間内に乱数(ランダムビットだけでなく)を生成できるため、多項式的に小さな誤差確率が必要であり、十分である。 もし$n$が与えられなければ、ランダムビット生成器しか持たなければ、(任意に小さい)定数誤差確率は必要で十分である。 上記の正の結果は、任意の純粋な JOT-DP プログラム $P$ を上界設定の純 JOT-DP プログラム $P'$ に変換する効率的な手順によって証明され、計算モデルによっては、$P'$ の出力分布が$\gamma$-close の総変動距離で$P$ となるような、純粋な JOT-DP プログラム $P'$ を純粋な JOT-DP プログラム $P'$ に変換するための効率的な手順によって証明される。

関連論文リスト

• Private Mean Estimation with Person-Level Differential Privacy [6.621676316292624]
  複数のサンプルを持つ場合の個人レベルの個人別平均推定について検討した。 我々は、計算効率のよいアルゴリズムを、純粋DPで、計算効率の悪いアルゴリズムを、ほぼ一致する下界は、近似DPの最も寛容な場合を抑える。
  論文  参考訳（メタデータ） (2024-05-30T18:20:35Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。 トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
  論文  参考訳（メタデータ） (2023-03-30T02:51:00Z)
• Privately Estimating a Gaussian: Efficient, Robust and Optimal [6.901744415870126]
  純微分プライバシー(DP)モデルと近似微分プライバシー(DP)モデルの両方において、ガウス分布をプライベートに推定する効率的なアルゴリズムを提供する。 純粋なDP設定では、未知の$d$次元ガウス分布を任意の全変分誤差まで推定する効率的なアルゴリズムを与える。 平均推定の特別な場合、我々のアルゴリズムは$widetilde O(d1.5)$の最適なサンプル複雑性を達成し、以前の作業から$widetilde O(d1.5)$のバウンドを改善する。
  論文  参考訳（メタデータ） (2022-12-15T18:27:39Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Scaling Structured Inference with Randomization [64.18063627155128]
  本稿では、構造化されたモデルを数万の潜在状態に拡張するためにランダム化された動的プログラミング(RDP)のファミリを提案する。 我々の手法は古典的DPベースの推論に広く適用できる。 また、自動微分とも互換性があり、ニューラルネットワークとシームレスに統合できる。
  論文  参考訳（メタデータ） (2021-12-07T11:26:41Z)
• Lossless Compression of Efficient Private Local Randomizers [55.657133416044104]
  Locally Differentially Private (LDP) Reportsは、フェデレーション設定における統計と機械学習の収集に一般的に使用されます。 多くの場合、最もよく知られたldpアルゴリズムは、クライアントデバイスからサーバに強制的に大きなメッセージを送信する必要がある。 これにより、LDPアルゴリズムの通信コストの削減に大きく貢献しています。
  論文  参考訳（メタデータ） (2021-02-24T07:04:30Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)

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

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