論文の概要: The Complexity of Verifying Boolean Programs as Differentially Private

• arxiv url: http://arxiv.org/abs/2309.04642v1
• Date: Fri, 8 Sep 2023 23:45:35 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-25 16:20:50.038615
• Title: The Complexity of Verifying Boolean Programs as Differentially Private
• Title（参考訳）: ブールプログラムの差分私的検証の複雑さ
• Authors: Mark Bun, Marco Gaboardi, Ludmila Glinskih,
• Abstract要約: プライバシパラメータの特定の値に対して、プログラムが差分プライベートかどうかを決定する問題は、PSPACE完全であることを示す。 また、プログラムが提供するプライバシパラメータを近似する問題はPSPACEハードであることを示す。
• 参考スコア（独自算出の注目度）: 16.322548156117545
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the complexity of the problem of verifying differential privacy for while-like programs working over boolean values and making probabilistic choices. Programs in this class can be interpreted into finite-state discrete-time Markov Chains (DTMC). We show that the problem of deciding whether a program is differentially private for specific values of the privacy parameters is PSPACE-complete. To show that this problem is in PSPACE, we adapt classical results about computing hitting probabilities for DTMC. To show PSPACE-hardness we use a reduction from the problem of checking whether a program almost surely terminates or not. We also show that the problem of approximating the privacy parameters that a program provides is PSPACE-hard. Moreover, we investigate the complexity of similar problems also for several relaxations of differential privacy: R\'enyi differential privacy, concentrated differential privacy, and truncated concentrated differential privacy. For these notions, we consider gap-versions of the problem of deciding whether a program is private or not and we show that all of them are PSPACE-complete.
• Abstract（参考訳）: ブール値に作用する時間型プログラムの差分プライバシーの検証と確率的選択の複雑さについて検討する。 このクラスのプログラムは有限状態離散時間マルコフ連鎖(DTMC)と解釈できる。 プライバシパラメータの特定の値に対して、プログラムが差分プライベートかどうかを決定する問題は、PSPACE完全であることを示す。 この問題がPSPACEにあることを示すため、DTMCの計算確率に対する古典的な結果に適応する。 PSPACE-hardnessを示すために、プログラムがほぼ確実に終了するかどうかをチェックする問題から減算を用いる。 また、プログラムが提供するプライバシパラメータを近似する問題はPSPACEハードであることを示す。 さらに, 差分プライバシーの緩和, R'enyi差分プライバシー, 集中型差分プライバシー, 集中型差分プライバシーなど, 類似の問題の複雑さについても検討した。 これらの概念に対して、プログラムがプライベートかどうかを判断する問題のギャップ変換を考察し、それらすべてがPSPACE完全であることを示す。

関連論文リスト

• Masked Differential Privacy [64.32494202656801]
  本稿では,差分プライバシーを適用した機密領域を制御できる「マスク型差分プライバシー(DP)」という効果的なアプローチを提案する。 提案手法はデータに基づいて選択的に動作し,DPアプリケーションや差分プライバシーをデータサンプル内の他のプライバシー技術と組み合わせることなく,非感性時間領域を定義できる。
  論文  参考訳（メタデータ） (2024-10-22T15:22:53Z)
• On Differential Privacy and Adaptive Data Analysis with Bounded Space [76.10334958368618]
  差分プライバシーと適応データ分析の2つの関連分野の空間複雑性について検討する。 差分プライバシーで効率的に解くために指数関数的に多くの空間を必要とする問題Pが存在することを示す。 アダプティブデータ分析の研究の行は、アダプティブクエリのシーケンスに応答するのに必要なサンプルの数を理解することに焦点を当てている。
  論文  参考訳（メタデータ） (2023-02-11T14:45:31Z)
• On the Statistical Complexity of Estimation and Testing under Privacy Constraints [17.04261371990489]
  差分プライバシー下での統計的テストのパワーをプラグアンドプレイ方式で特徴付ける方法を示す。 プライバシ保護のレベルが非常に高い場合にのみ、プライバシの維持が顕著なパフォーマンス低下をもたらすことを示す。 最後に,プライベート凸解法であるDP-SGLDアルゴリズムを高信頼度で最大推定できることを示した。
  論文  参考訳（メタデータ） (2022-10-05T12:55:53Z)
• Algorithms with More Granular Differential Privacy Guarantees [65.3684804101664]
  我々は、属性ごとのプライバシー保証を定量化できる部分微分プライバシー(DP)について検討する。 本研究では,複数の基本データ分析および学習タスクについて検討し,属性ごとのプライバシパラメータが個人全体のプライバシーパラメータよりも小さい設計アルゴリズムについて検討する。
  論文  参考訳（メタデータ） (2022-09-08T22:43:50Z)
• Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
  DP-SGDで訓練されたモデルをリリースする際の個々の事例に対するプライバシー保証を特徴付ける。 ほとんどの例では、最悪のケースよりも強力なプライバシー保証を享受しています。 これは、モデルユーティリティの観点からは守られないグループが同時に、より弱いプライバシー保証を経験することを意味する。
  論文  参考訳（メタデータ） (2022-06-06T13:49:37Z)
• Fully Adaptive Composition in Differential Privacy [53.01656650117495]
  よく知られた高度な合成定理は、基本的なプライバシー構成が許すよりも、プライベートデータベースを2倍にクエリすることができる。 アルゴリズムとプライバシパラメータの両方を適応的に選択できる完全適応型合成を導入する。 適応的に選択されたプライバシパラメータが許されているにもかかわらず、定数を含む高度なコンポジションのレートに適合するフィルタを構築します。
  論文  参考訳（メタデータ） (2022-03-10T17:03:12Z)
• Private Optimization Without Constraint Violations [14.920650598301476]
  本稿では,制約の右辺がプライベートデータに依存する場合,線形制約を伴う差分プライベート最適化の問題について検討する。 これまでの研究では、プライバシーを維持しながら、時には制約に違反したソリューションが提供されていた。 確率 1 の制約を満たす近似解を解くアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-07-02T15:08:52Z)
• Bounding, Concentrating, and Truncating: Unifying Privacy Loss Composition for Data Analytics [2.614355818010333]
  アナリストが純粋なDP、境界範囲(指数的なメカニズムなど)、集中的なDPメカニズムを任意の順序で選択できる場合、強いプライバシー損失バウンダリを提供する。 また、アナリストが純粋なDPと境界範囲のメカニズムをバッチで選択できる場合に適用される最適なプライバシー損失境界を提供する。
  論文  参考訳（メタデータ） (2020-04-15T17:33:10Z)
• Privately Learning Markov Random Fields [44.95321417724914]
  我々は、差分プライバシーの制約の下でランダムフィールド(イジングモデルを含む)を学習する問題を考察する。 私たちは、さまざまなプライバシー制約の下で、両方の問題に対してアルゴリズムと低いバウンダリを提供します。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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