論文の概要: Efficient Extensions for Asynchronous Byzantine Agreement via Weak Agreement
- arxiv url: http://arxiv.org/abs/2502.02320v1
- Date: Tue, 04 Feb 2025 13:44:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-05 14:56:11.954840
- Title: Efficient Extensions for Asynchronous Byzantine Agreement via Weak Agreement
- Title（参考訳）: 弱弱協定による非同期ビザンチン協定の効率的な拡張
- Authors: Mose Mizrahi Erbes, Roger Wattenhofer,
- Abstract要約: 我々は、$n$パーティの非同期ネットワークを、最大$t$で、そのうちの最大$t$はビザンチンであり、$t fracn3$失敗は、$ell$-bit入力のビザンチン合意(BA)を、$ell$-bit入力の1つのインスタンス、$ell$-bit入力の1つのインスタンス、バイナリBAと$Theta(ell n + n2)$追加通信のビットに還元する。
我々のWAプロトコルはどちらも、バイナリBAから多値BAへの最先端の情報理論拡張につながります。
- 参考スコア（独自算出の注目度）: 23.27199615640474
- License:
- Abstract: We consider an asynchronous network of $n$ parties, up to $t$ of which are byzantine, and against $t < \frac{n}{3}$ failures reduce byzantine agreement (BA) on $\ell$-bit inputs to one instance of weak agreement (WA) on $\ell$-bit inputs, one instance of binary BA and $\Theta(\ell n + n^2)$ bits of additional communication. Then, to use in this reduction, we design two information-theoretic WA protocols. In the first one, we use almost-universal hashing to achieve statistical security except with probability $2^{-\lambda}$ against $t < \frac{n}{3}$ failures with $\Theta(n^2(\lambda + \log n + \log \ell)) = \mathcal{O}(\ell n + n^2(\lambda + \log n))$ bits of communication. Then, we modify our first protocol by replacing the hashes with error correcting code symbols and introducing a preliminary step based on the COOL protocol for synchronous multivalued BA [DISC '21] to achieve perfect security against $t \leq \frac{n}{3 + \varepsilon}$ failures with $\Theta(\ell n + n^2)$ bits of communication. Our WA protocols both lead to state-of-the-art information-theoretic extensions from binary BA to multivalued BA.
- Abstract（参考訳）: 我々は、$n$パーティの非同期ネットワークを、最大$t$と、$t < \frac{n}{3}$障害に対して、$\ell$-bit入力のビザンチン合意(BA)を、$\ell$-bit入力の1つのインスタンス、$\ell$-bit入力の1つのインスタンス、バイナリBAのインスタンス、$\Theta(\ell n + n^2)$追加通信のビットに還元する。
そして,この削減のために2つの情報理論WAプロトコルを設計する。
まず、確率$t < \frac{n}{3}$ failures with $\Theta(n^2(\lambda + \log n + \log \ell)) = \mathcal{O}(\ell n + n^2(\lambda + \log n))$ bits of communication。
次に、ハッシュを誤り訂正符号記号に置き換え、同期多重値BAのためのCOOLプロトコルに基づく予備ステップを導入し、$t \leq \frac{n}{3 + \varepsilon}$障害を$\Theta(\ell n + n^2)$通信ビットで完全なセキュリティを実現する。
我々のWAプロトコルはどちらも、バイナリBAから多値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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。