論文の概要: Communication Lower Bounds for Cryptographic Broadcast Protocols
- arxiv url: http://arxiv.org/abs/2309.01466v1
- Date: Mon, 4 Sep 2023 09:24:39 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-25 23:19:21.993629
- Title: Communication Lower Bounds for Cryptographic Broadcast Protocols
- Title(参考訳): 暗号化放送プロトコルにおける低域通信
- Authors: Erica Blum, Elette Boyle, Ran Cohen, Chen-Da Liu-Zhang,
- Abstract要約: ブロードキャストプロトコルは、悪質な当事者による攻撃に対してさえも、指定された送信者の入力に$n$のパーティが同意することを可能にする。
この設定内の任意のブロードキャストプロトコルを攻撃して、任意のパーティに$k$の他のパーティへのメッセージ送信を強制できることを示します。
- 参考スコア(独自算出の注目度): 7.233482131020069
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Broadcast protocols enable a set of $n$ parties to agree on the input of a designated sender, even facing attacks by malicious parties. In the honest-majority setting, randomization and cryptography were harnessed to achieve low-communication broadcast with sub-quadratic total communication and balanced sub-linear cost per party. However, comparatively little is known in the dishonest-majority setting. Here, the most communication-efficient constructions are based on Dolev and Strong (SICOMP '83), and sub-quadratic broadcast has not been achieved. On the other hand, the only nontrivial $\omega(n)$ communication lower bounds are restricted to deterministic protocols, or against strong adaptive adversaries that can perform "after the fact" removal of messages. We provide new communication lower bounds in this space, which hold against arbitrary cryptography and setup assumptions, as well as a simple protocol showing near tightness of our first bound. 1) We demonstrate a tradeoff between resiliency and communication for protocols secure against $n-o(n)$ static corruptions. For example, $\Omega(n\cdot {\sf polylog}(n))$ messages are needed when the number of honest parties is $n/{\sf polylog}(n)$; $\Omega(n\sqrt{n})$ messages are needed for $O(\sqrt{n})$ honest parties; and $\Omega(n^2)$ messages are needed for $O(1)$ honest parties. Complementarily, we demonstrate broadcast with $O(n\cdot{\sf polylog}(n))$ total communication facing any constant fraction of static corruptions. 2) Our second bound considers $n/2 + k$ corruptions and a weakly adaptive adversary that cannot remove messages "after the fact." We show that any broadcast protocol within this setting can be attacked to force an arbitrary party to send messages to $k$ other parties. This rules out, for example, broadcast facing 51% corruptions in which all non-sender parties have sublinear communication locality.
- Abstract(参考訳): ブロードキャストプロトコルは、悪質な当事者による攻撃に対してさえも、指定された送信者の入力に$n$のパーティが同意することを可能にする。
正直な設定では、ランダム化と暗号を利用して、サブクアドラルな全通信とバランスの取れたサブ線形コストで低コミュニケーションの放送を実現した。
しかし、不正直な設定ではほとんど知られていない。
ここでは、通信効率が最も高い構成はドレフとストロング(SICOMP '83)に基づいており、サブクオーラ放送は行われていない。
一方、非自明な$\omega(n)$の通信下界は決定論的プロトコルに制限されるか、あるいはメッセージの削除後に"実行された"強い適応的敵に対して制限される。
我々は、任意の暗号や設定の前提に反する、この空間における新しい通信の下限と、最初のバウンダリの密接度を示す単純なプロトコルを提供する。
1)$n-o(n)$の静的汚職に対してセキュアなプロトコルに対するレジリエンスと通信のトレードオフを示す。
例えば、$\Omega(n\cdot {\sf polylog}(n))$メッセージは、正直な相手の数が$n/{\sf polylog}(n)$; $\Omega(n\sqrt{n})$メッセージは$O(\sqrt{n})$正直な相手、$\Omega(n^2)$メッセージは$O(1)$正直な相手の場合に必要である。
相補的に$O(n\cdot{\sf polylog}(n))$トータル通信で、静的な破損の一定割合に直面した放送を実演する。
2つ目の境界線は、$n/2 + k$の汚職と、"事実の後に"メッセージを削除することができない弱い適応的な敵を考える。
この設定内の任意のブロードキャストプロトコルを攻撃して、任意のパーティに$k$の他のパーティへのメッセージ送信を強制できることを示します。
例えば、このルールは、すべての非売春当事者がサブリニアな通信地域を持つ51%の汚職に直面して放送される。
関連論文リスト
- Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
本稿では,プライバシのシャッフルモデルにおけるプライベートベクトル平均推定の問題について検討する。
我々は,$tildemathcalOleft(min(nvarepsilon2,d)right)$ message per users を用いて,最適なエラーを実現する新しいマルチメッセージプロトコルを提案する。
論文 参考訳(メタデータ) (2024-04-16T00:56:36Z) - SwiftAgg+: Achieving Asymptotically Optimal Communication Load in Secure
Aggregation for Federated Learning [83.94234859890402]
SwiftAgg+は、フェデレーション学習システムのための新しいセキュアアグリゲーションプロトコルである。
中央サーバは、分散ユーザである$NinmathbbN$のローカルモデルを集約する。
論文 参考訳(メタデータ) (2022-03-24T13:12:23Z) - SwiftAgg: Communication-Efficient and Dropout-Resistant Secure
Aggregation for Federated Learning with Worst-Case Security Guarantees [83.94234859890402]
我々は,フェデレート学習システムのための新しいセキュアアグリゲーションプロトコルSwiftAggを提案する。
中央サーバは、ローカルデータに基づいてトレーニングされた、$N$の分散ユーザのローカルモデルを集約する。
SwiftAggは、セキュリティ上の妥協なしに、通信オーバーヘッドを大幅に削減する。
論文 参考訳(メタデータ) (2022-02-08T22:08:56Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳(メタデータ) (2021-07-22T14:25:16Z) - Communication Complexity of Private Simultaneous Quantum Messages
Protocols [0.609170287691728]
本稿では、量子通信の利点と、プライベート同時量子メッセージモデルの事前絡み合いについて検討する。
プライバシ条件は,PSQMモデルの通信コストを必然的に増大させることを示す。
また,共有絡み合った状態と共有ランダム文字列を持つPSQMプロトコルの通信複雑性の指数的差を示す。
論文 参考訳(メタデータ) (2021-05-15T03:08:01Z) - Sparse Normal Means Estimation with Sublinear Communication [13.257075075199781]
通信制約のある分散環境における正規平均推定の問題点を考察する。
信号対雑音比(SNR)がわずかに高くなると、$mu$のサポートはより少ない通信で正確に回復できることを示す。
論文 参考訳(メタデータ) (2021-02-05T08:52:25Z) - On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。
目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文 参考訳(メタデータ) (2020-09-21T04:13:34Z) - Toward Adversarial Robustness via Semi-supervised Robust Training [93.36310070269643]
アドリラルな例は、ディープニューラルネットワーク(DNN)に対する深刻な脅威であることが示されている。
R_stand$ と $R_rob$ の2つの異なるリスクを共同で最小化することで、新しい防御手法であるロバストトレーニング(RT)を提案する。
論文 参考訳(メタデータ) (2020-03-16T02:14:08Z) - Capacity Approaching Coding for Low Noise Interactive Quantum
Communication, Part I: Large Alphabets [15.078027648304115]
ノイズの多いチャネル上での双方向の対話型量子通信を実現する際の問題点を考察する。
$mathrmpoly(n)$ sizeアルファベット上のノイズのないquditチャネルの場合、主な結果は2-theta(nepsilon)$未満の確率で失敗するシミュレーション手法である。
我々は、$sqrtepsilon$項の定数係数まで最適であると推測する。
論文 参考訳(メタデータ) (2020-01-09T02:48:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。