論文の概要: 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%の汚職に直面して放送される。
関連論文リスト
- Juggernaut: Efficient Crypto-Agnostic Byzantine Agreement [1.77513002450736]
信頼できる設定によって、$tn/2$の汚職が存在する場合、ビザンツ協定の問題を解決することはよく知られている。
本稿では, レジリエンスに最適化されたビザンチン合意プロトコルを, 暗号に依存しないものに変換するコンパイラを提案する。
以上の結果より,少なくとも$n$の2因子はビット複雑性の最先端性を改善し,早期停止(決定論的)あるいは期待される一定ラウンド複雑性(ランダム化)を提供する。
論文 参考訳（メタデータ） (2024-10-15T23:44:29Z) - Asynchronous Approximate Agreement with Quadratic Communication [23.27199615640474]
非同期ネットワークは$n$のメッセージ送信パーティで、そのうちの最大$t$はビザンチンです。
本研究では,入力の凸内積にほぼ等しい出力が得られるような近似一致について検討する。
これは、信頼できるブロードキャスト毎に$Theta(n2)$メッセージ、またはイテレーション毎に$Theta(n3)$メッセージを取る。
論文 参考訳（メタデータ） (2024-08-10T09:03:06Z) - 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) - On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。
目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文 参考訳（メタデータ） (2020-09-21T04:13:34Z) - A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip [2.469280630208887]
コインフリッピングプロトコルでは、計算上の敵は、プロトコルの実行に沿ってどのパーティを腐敗させるかを選択することができる。
我々は、(丸い複雑さの)$n$-partyプロトコルが$omega(sqrtn)$ corruptionsに回復可能であることを証明している。
論文 参考訳（メタデータ） (2020-05-04T15:29:11Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。