論文の概要: Efficient Extensions for Asynchronous Byzantine Agreement via Weak Agreement
- arxiv url: http://arxiv.org/abs/2502.02320v2
- Date: Mon, 10 Feb 2025 14:06:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-11 14:28:50.793014
- Title: Efficient Extensions for Asynchronous Byzantine Agreement via Weak Agreement
- Title(参考訳): 弱弱協定による非同期ビザンチン協定の効率的な拡張
- Authors: Mose Mizrahi Erbes, Roger Wattenhofer,
- Abstract要約: 多値BAから二値BAへの新たな還元効果を示す。
我々は,多値WAを用いて,$ell$-bit入力のための2つの効率的なWAプロトコルを設計する。
我々のWAプロトコルはバイナリBAを、ラウンドオーバーヘッドが一定で、通信オーバーヘッドが$$$2、セキュリティがほぼ最適である複数値BAに拡張します。
- 参考スコア(独自算出の注目度): 23.27199615640474
- License:
- Abstract: In this work, we study multivalued byzantine agreement (BA) in an asynchronous network of $n$ parties where up to $t < \frac{n}{3}$ parties are byzantine. In this setting, we present a novel reduction from multivalued BA to binary BA. This reduction allows one to achieve BA on $\ell$-bit inputs with one instance of binary BA, one instance of weak agreement (WA) on $\ell$-bit inputs and $\Theta(\ell n + n^2)$ bits of additional communication. Afterwards, as our reduction uses multivalued WA, we design two new efficient WA protocols for $\ell$-bit inputs. In the first one, we use almost-universal hashing to achieve statistical security with probability $1 - 2^{-\lambda}$ against $t < \frac{n}{3}$ failures with $\Theta(n^2(\lambda + \log n + \log \ell))$ bits of communication. Then, we replace the hashes with error correcting code symbols and add a step based on the synchronous multivalued BA protocol COOL [DISC '21] to obtain our second protocol, which for any fixed $\varepsilon > 0$ achieves perfect security against $t \leq \frac{n}{3 + \varepsilon}$ failures with $\Theta(\ell n + n^2)$ bits of communication. Used in our reduction, our WA protocols extend binary BA to multivalued BA with a constant round overhead, a quadratic-in-$n$ communication overhead, and near-optimal security.
- Abstract(参考訳): 本研究では,最大$t < \frac{n}{3}$パーティがビザンチンである場合の,$n$パーティの非同期ネットワークにおける多値ビザンチン合意(BA)について検討する。
そこで本研究では,多値BAから二値BAへの新たな還元法を提案する。
この還元により、$\ell$-bitの入力に対して$\ell$-bitの入力に対してBAを達成することができ、$\ell$-bitの入力に対して弱一致(WA)のインスタンスと$\Theta(\ell n + n^2)の付加的な通信を行う。
その後、我々はマルチ値WAを用いて、$$\ell$-bit入力のための2つの効率的なWAプロトコルを設計した。
まず、確率1 - 2^{-\lambda}$ $t < \frac{n}{3}$ failures with $\Theta(n^2(\lambda + \log n + \log \ell))$ bits of communication。
次に、ハッシュを誤り訂正符号記号に置き換え、同期多重値のBAプロトコルであるCOOL[DISC '21]に基づいてステップを追加し、固定された$\varepsilon > 0$に対して$t \leq \frac{n}{3 + \varepsilon}$障害を$\Theta(\ell n + n^2)$ビットの通信に対して完全なセキュリティを達成する。
我々のWAプロトコルは,2値BAを,ラウンドオーバーヘッドが一定であり,通信オーバーヘッドが2-in-$$で,セキュリティがほぼ最適である多値BAに拡張する。
関連論文リスト
- OciorABA: Improved Error-Free Asynchronous Byzantine Agreement via Partial Vector Agreement [15.464948077412021]
我々は,OciorABAと呼ばれる,エラーフリーで情報理論的にセキュアな多値非同期ビザンチン契約プロトコルを提案する。
プロトコル設計では、新しいプリミティブ、非同期部分ベクトルアグリーメント(APVA)を導入する。
論文 参考訳(メタデータ) (2025-01-20T23:36:11Z) - 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) - Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳(メタデータ) (2024-06-18T08:54:04Z) - Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。
この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文 参考訳(メタデータ) (2024-05-09T17:40:09Z) - 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) - Coordinated Attacks against Contextual Bandits: Fundamental Limits and
Defense Mechanisms [75.17357040707347]
オンラインレコメンデーションシステムによってモチベーションされた我々は,文脈的包帯における最適政策の発見問題を提案する。
目標は、優れたユーザに対する報酬を可能な限り少ないユーザインタラクションで最大化するポリシーを、しっかりと学習することだ。
効率的なロバストな平均推定器を用いることで、$tildeO(min(S,A)cdot alpha/epsilon2)$ upper-boundを実現できることを示す。
論文 参考訳(メタデータ) (2022-01-30T01:45:13Z) - Tight Bounds for the Randomized and Quantum Communication Complexities
of Equality with Small Error [1.6522364074260811]
誤差が小さいEquality関数のランダム化および量子化通信複雑性を$epsilon$で調べる。
任意の$log(n/epsilon)-log(sqrtn/epsilon)+3$プロトコルが少なくとも$log(n/epsilon)-log(sqrtn/epsilon)-O(1)$ qubitsを通信することを示す。
論文 参考訳(メタデータ) (2021-07-25T13:52:42Z) - An Efficient Simulation of Quantum Secret Sharing [7.195824023358536]
秘密を効率的なシミュレーションで共有するためのセキュアな$d$レベル$QSS$プロトコルを提案する。
プレイヤーへの秘密に関する情報は公表されていない。
そのセキュリティ分析によると、このプロトコルでは、インターセプト-リセプト、インターセプト、エンタングル対策、偽造、衝突、共謀攻撃は不可能である。
論文 参考訳(メタデータ) (2021-03-20T16:42:02Z) - On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。
目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文 参考訳(メタデータ) (2020-09-21T04:13:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。