論文の概要: Combinatorial Privacy: Private Multi-Party Bitstream Grand Sum by Hiding in Birkhoff Polytopes

• arxiv url: http://arxiv.org/abs/2603.22808v2
• Date: Thu, 26 Mar 2026 06:57:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-27 13:32:29.883068
• Title: Combinatorial Privacy: Private Multi-Party Bitstream Grand Sum by Hiding in Birkhoff Polytopes
• Title（参考訳）: プライベート・マルチ・パートナーのBitstream Grand Sum:Birkhoff Polytopesに隠された
• Authors: Praneeth Vepakomma,
• Abstract要約: PolyVeilは、Birkhoff polytopeでプライベートビットを置換行列としてエンコードする、$k$クライアント間の総和プロトコルである。 P-hardnessは完全な行列ビューを必要とするが、非空のDPはスカラービューを必要とする。 プロトコルはPKIを必要とせず、$O(k)$通信を持ち、正確な集約を出力する。
• 参考スコア（独自算出の注目度）: 6.178002001006941
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce PolyVeil, a protocol for private Boolean summation across $k$ clients that encodes private bits as permutation matrices in the Birkhoff polytope. A two-layer architecture gives the server perfect simulation-based security (statistical distance zero) while a separate aggregator faces \#P-hard likelihood inference via the permanent and mixed discriminant. Two variants (full and compressed) differ in what the aggregator observes. We develop a finite-sample $(\varepsilon,δ)$-DP analysis with explicit constants. In the full variant, where the aggregator sees a doubly stochastic matrix per client, the log-Lipschitz constant grows as $n^4 K_t$ and a signal-to-noise analysis shows the DP guarantee is non-vacuous only when the private signal is undetectable. In the compressed variant, where the aggregator sees a single scalar, the univariate density ratio yields non-vacuous $\varepsilon$ at moderate SNR, with the optimal decoy count balancing CLT accuracy against noise concentration. This exposes a fundamental tension. \#P-hardness requires the full matrix view (Birkhoff structure visible), while non-vacuous DP requires the scalar view (low dimensionality). Whether both hold simultaneously in one variant remains open. The protocol needs no PKI, has $O(k)$ communication, and outputs exact aggregates.
• Abstract（参考訳）: 我々はPolyVeilを紹介した。PolyVeilは、プライベートビットをBirkhoffポリトープの置換行列としてエンコードする、$k$クライアント間のプライベートブール和のためのプロトコルである。 2層アーキテクチャでは、サーバの完全なシミュレーションベースのセキュリティ(統計距離ゼロ)が与えられ、一方、分離されたアグリゲータは、永続的および混合的な判別器を介して、 \#P-ハードな確率推論に直面している。 2つの変種(フルおよび圧縮)はアグリゲーターが観察するものと異なる。 有限サンプル $(\varepsilon,δ)$-DP を明示定数で解析する。 集約器がクライアント毎の確率行列を2倍にすると、対数-Lipschitz定数は$n^4 K_t$として増加し、信号-雑音解析によりDP保証は検出不能な場合にのみ空でないことを示す。 圧縮された変種では、アグリゲータが1つのスカラーを見ることができるが、一変量密度比は、中等度SNRにおいて非空の$\varepsilon$となり、CLTの精度と雑音の濃度とのバランスが最適である。 これは根本的な緊張を露呈する。 \#P-硬度は完全な行列ビュー(ビルホフ構造が可視)を必要とするが、非空のDPはスカラービュー(低次元性)を必要とする。 どちらも1つの変種で同時に保持するかどうかは未定である。 プロトコルはPKIを必要とせず、$O(k)$通信を持ち、正確な集約を出力する。

関連論文リスト

• DP-CSGP: Differentially Private Stochastic Gradient Push with Compressed Communication [71.60998478544028]
  本稿では,分散学習グラフのための圧縮通信(termedfrac-CSGP)を用いた差分的プライベート・グラディエント・プッシュを提案する。 一般の非数学的かつ滑らかな目的関数に対して,本アルゴリズムは高精度かつ効率的な通信を実現するために設計されていることを示す。
  論文  参考訳（メタデータ） (2025-12-15T17:37:02Z)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
  論文  参考訳（メタデータ） (2025-06-30T13:27:39Z)
• Beyond Laplace and Gaussian: Exploring the Generalized Gaussian Mechanism for Private Machine Learning [49.66162382667325]
  一般化ガウス機構(英語版)を考察し、ある$beta geq 1$に対して$e-frac| x |sigmabeta $ に比例した付加雑音項 $x$ をサンプリングする。 GGメカニズムとその変種に対するプライバシ会計は独立であり、プライバシ会計の計算コストを大幅に向上させることを示す。
  論文  参考訳（メタデータ） (2025-06-14T15:49:25Z)
• Lightweight Protocols for Distributed Private Quantile Estimation [12.586899971090277]
  我々は、各ユーザが1つのデータポイントを1つのドメインに[B]$で保持するときに、1つの量子を推定する2つの強調適応アルゴリズムを考察する。 適応的な設定では、$varepsilon$-LDPアルゴリズムを用い、$O(fraclog Bvarepsilon2alpha2)$ユーザしか必要としないエラー$alpha$内の量子化を推定できる。
  論文  参考訳（メタデータ） (2025-02-05T08:39:02Z)
• Private Mean Estimation with Person-Level Differential Privacy [6.621676316292624]
  複数のサンプルを持つ場合の個人レベルの個人別平均推定について検討した。 我々は、計算効率のよいアルゴリズムを、純粋DPで、計算効率の悪いアルゴリズムを、ほぼ一致する下界は、近似DPの最も寛容な場合を抑える。
  論文  参考訳（メタデータ） (2024-05-30T18:20:35Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Settling the Sample Complexity of Model-Based Offline Reinforcement Learning [50.5790774201146]
  オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。 事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。 モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
  論文  参考訳（メタデータ） (2022-04-11T17:26:19Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming [10.952006057356714]
  プライバシと通信の制約下での周波数推定の基本的問題について検討し,そのデータを$k$のパーティ間で分散する。 私たちは、ローカルディファレンシャルプライバシ(LDP)と(分散)ディファレンシャルプライバシよりも一般的なマルチパーティディファレンシャルプライバシ(MDP)のモデルを採用しています。 我々のプロトコルは、より厳密な2つの制約によって許容可能な最適性(対数因子まで)を達成する。
  論文  参考訳（メタデータ） (2021-04-05T08:15:20Z)

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

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