論文の概要: Extending Asynchronous Byzantine Agreement with Crusader Agreement
- arxiv url: http://arxiv.org/abs/2502.02320v3
- Date: Mon, 05 May 2025 07:56:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-06 14:44:43.908979
- Title: Extending Asynchronous Byzantine Agreement with Crusader Agreement
- Title（参考訳）: 十字軍協定による非同期ビザンチン協定の延長
- Authors: Mose Mizrahi Erbes, Roger Wattenhofer,
- Abstract要約: 多値BAから二値BAへの新たな削減を提案する。
削減には多値CAを用いるため、$ell$-bit入力のための2つの情報理論CAプロトコルも設計する。
- 参考スコア（独自算出の注目度）: 23.27199615640474
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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. We present a new reduction from multivalued BA to binary BA. It allows one to achieve BA on $\ell$-bit inputs with one instance of binary BA, one instance of crusader agreement (CA) on $\ell$-bit inputs and $\Theta(\ell n + n^2)$ bits of additional communication. As our reduction uses multivalued CA, we also design two new information-theoretic CA 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}$ faults with $\Theta(\ell n + n^2(\lambda + \log n))$ bits of communication. Following this, we replace the hashes with error correcting code symbols and add a preliminary step based on the synchronous multivalued BA protocol COOL [DISC '21] to obtain a second, perfectly secure CA protocol that can for any $\varepsilon > 0$ be set to tolerate $t \leq \frac{n}{3 + \varepsilon}$ faults with $\mathcal{O}\bigl(\frac{\ell n}{\min(1, \varepsilon^2)} + n^2\max\bigl(1, \log \frac{1}{\varepsilon}\bigr) \bigr)$ bits of communication. Our CA protocols allow one to extend binary BA to multivalued BA with a constant round overhead, a quadratic-in-$n$ communication overhead, and information-theoretic security.
- Abstract（参考訳）: 本研究では,最大$t < \frac{n}{3}$パーティがビザンチンである場合の,$n$パーティの非同期ネットワークにおける多値ビザンチン合意(BA)について検討する。
多値BAから二値BAへの新たな削減を提案する。
これにより、$\ell$-bitの入力に対して$\ell$-bitの入力に対してBAを達成することができ、$\ell$-bitの入力に対してCrusader agreement (CA)のインスタンスと$\Theta(\ell n + n^2)の追加通信を行う。
削減には多値CAを用いるため,$$\ell$-bit入力のための2つの情報理論CAプロトコルも設計する。
まず、確率1 - 2^{-\lambda}$ $t < \frac{n}{3}$ Faults with $\Theta(\ell n + n^2(\lambda + \log n))$ bits of communication。
次に、ハッシュをエラー訂正符号記号に置き換え、同期マルチ数値のBAプロトコル COOL [DISC '21] に基づいた予備ステップを追加して、$t \leq \frac{n}{3 + \varepsilon}$ Faults with $\mathcal{O}\bigl(\frac{\ell n}{\min(1, \varepsilon^2)} + n^2\max\bigl(1, \log \frac{1}{\varepsilon}\bigr) \bigr)$ bits of communication を許容できる、第2の完全なCAプロトコルを得る。
当社のCAプロトコルでは,バイナリBAをラウンドオーバーヘッドが一定で,通信オーバーヘッドが$$$2の2値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) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳（メタデータ） (2022-10-15T09:22:22Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。