論文の概要: Concurrent Asynchronous Byzantine Agreement in Expected-Constant Rounds, Revisited
- arxiv url: http://arxiv.org/abs/2312.14506v1
- Date: Fri, 22 Dec 2023 08:10:11 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-18 11:28:18.995873
- Title: Concurrent Asynchronous Byzantine Agreement in Expected-Constant Rounds, Revisited
- Title(参考訳): 日銀・日銀・日銀・日銀・日銀・日銀・日銀・日銀・日銀・日銀・日銀・日銀・日銀・日銀・日銀・日銀・日銀・日銀・日銀・日銀・日銀・日銀・日銀
- Authors: Ran Cohen, Pouyan Forghani, Juan Garay, Rutvik Patel, Vassilis Zikas,
- Abstract要約: 最適なレジリエンスを持つ非同期設定において,最初の情報理論多値OCCプロトコルを提案する。
我々のプロトコルは指数関数サイズのドメインで効率的に実装する。
また、CanettiのUniversal Composabilityフレームワークの証明も提供します。
- 参考スコア(独自算出の注目度): 3.8014967401609208
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: It is well known that without randomization, Byzantine agreement (BA) requires a linear number of rounds in the synchronous setting, while it is flat out impossible in the asynchronous setting. The primitive which allows to bypass the above limitation is known as oblivious common coin (OCC). It allows parties to agree with constant probability on a random coin, where agreement is oblivious, i.e., players are not aware whether or not agreement has been achieved. The starting point of our work is the observation that no known protocol exists for information-theoretic multi-valued OCC with optimal resiliency in the asynchronous setting (with eventual message delivery). This apparent hole in the literature is particularly problematic, as multi-valued OCC is implicitly or explicitly used in several constructions. In this paper, we present the first information-theoretic multi-valued OCC protocol in the asynchronous setting with optimal resiliency, i.e., tolerating $t < n/3$ corruptions, thereby filling this important gap. Further, our protocol efficiently implements OCC with an exponential-size domain, a property which is not even achieved by known constructions in the simpler, synchronous setting. We then turn to the problem of round-preserving parallel composition of asynchronous BA. A protocol for this task was proposed by Ben-Or and El-Yaniv [Distributed Computing '03]. Their construction, however, is flawed in several ways. Thus, as a second contribution, we provide a simpler, more modular protocol for the above task. Finally, and as a contribution of independent interest, we provide proofs in Canetti's Universal Composability framework; this makes our work the first one offering composability guarantees, which are important as BA is a core building block of secure multi-party computation protocols.
- Abstract(参考訳): ランダム化なしでは、Byzantine agreement (BA) は同期設定では直線的なラウンド数を必要とするが、非同期設定では不可能である。
上記の制限を回避できるプリミティブは、oblivious Common coin (OCC) として知られている。
ランダムなコインに一定の確率で合意できるが、これは合意が不可能である場合、つまり、プレイヤーは合意が達成されたかどうかを知らない。
私たちの研究の出発点は、非同期環境で最適なレジリエンス(最終的なメッセージ配信を伴う)を持つ情報理論多値OCCには、既知のプロトコルが存在しないことです。
文献のこの明らかな穴は特に問題であり、多値OCCはいくつかの構成で暗黙的または明示的に使用される。
本稿では,最適なレジリエンス,すなわち$t < n/3$の汚職を許容し,この重要なギャップを埋める非同期設定において,最初の情報理論多値OCCプロトコルを提案する。
さらに,本プロトコルは,よりシンプルで同期的な設定において,既知の構成では達成できない特性である指数的サイズのドメインでOCCを効率的に実装する。
次に、非同期BAの並列合成を丸保存する問題に目を向ける。
このタスクのプロトコルはBen-OrとEl-Yaniv [Distributed Computing '03]によって提案されました。
しかし、その構造はいくつかの点で欠陥がある。
したがって、第2のコントリビューションとして、上記のタスクに対してよりシンプルでモジュール化されたプロトコルを提供しています。
BAはセキュアなマルチパーティ計算プロトコルのコアビルディングブロックであるため、コンポーザビリティの保証を提供する最初のフレームワークになります。
関連論文リスト
- MindFlayer: Efficient Asynchronous Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Times [49.1574468325115]
並列作業者の助けを借りてスムーズな非関数の期待を最小化する問題について検討する。
本稿では,ノイズの重み付けを行う新しい非同期SGD手法であるMindlayer SGDを提案する。
我々の理論は、ノイズが重く尾行されている場合に、Mindlayer SGDの優位性を実証するものである。
論文 参考訳(メタデータ) (2024-10-05T21:11:32Z) - A Study on Asynchronous Vote-based Blockchains [4.79997217554732]
投票ベースのブロックチェーンは、Byzantine Fault Toleranceコンセンサスプロトコルを使用して、ある状態から別の状態へ移行する。
本稿では,非同期環境におけるリーダベースの協調を可能にする,強大なBFTコンセンサスモデルを提案する。
我々のプロトコルはメッセージの複雑さを大幅に減らし、しきい値のシグネチャに頼ることなく線形ビューの変更を実現する最初のプロトコルです。
論文 参考訳(メタデータ) (2024-09-12T15:54:40Z) - Strong Priority and Determinacy in Timed CCS [0.0]
プロセス代数の標準理論を優先して構築し、「構成的還元」と呼ばれる新しいスケジューリング機構を同定する。
大規模な「コヒーレント」プロセスが構成的還元の共役性であることを示す。
論文 参考訳(メタデータ) (2024-03-07T16:02:31Z) - Federated Contextual Cascading Bandits with Asynchronous Communication
and Heterogeneous Users [95.77678166036561]
繊細な通信プロトコルを用いたUPB型アルゴリズムを提案する。
同期フレームワークで達成されたものと同等のサブ線形後悔境界を与えます。
合成および実世界のデータセットに関する実証評価は、後悔と通信コストの観点から、我々のアルゴリズムの優れた性能を検証する。
論文 参考訳(メタデータ) (2024-02-26T05:31:14Z) - Protocols for Quantum Weak Coin Flipping [0.1499944454332829]
弱いコインフリップは重要な暗号プリミティブである。
我々は関連するユニタリ作用素の正確な構成を与える。
本稿では, 明快なコインフリッププロトコルの構築について述べる。
論文 参考訳(メタデータ) (2024-02-24T16:52:54Z) - Oblivious Transfer from Zero-Knowledge Proofs, or How to Achieve
Round-Optimal Quantum Oblivious Transfer and Zero-Knowledge Proofs on Quantum
States [0.0]
従来のZero-Knowledge(ZK)プロトコルを、構成可能な(量子)Obliivious Transfer(OT)プロトコルに変換する。
ランダムオラクルモデルでセキュアな第1ラウンド最適(2-message)量子OTプロトコルを提供する。
私たちの構築の中心には、受信した量子状態のプロパティを追加情報を公開することなく証明できる新しい方法があります。
論文 参考訳(メタデータ) (2023-03-02T18:38:15Z) - ByzSecAgg: A Byzantine-Resistant Secure Aggregation Scheme for Federated
Learning Based on Coded Computing and Vector Commitment [90.60126724503662]
ByzSecAggは、フェデレートラーニングのための効率的なセキュアアグリゲーションスキームである。
ByzSecAggは、ビザンツの攻撃やプライバシーの漏洩から保護されている。
論文 参考訳(メタデータ) (2023-02-20T11:15:18Z) - Is Vertical Logistic Regression Privacy-Preserving? A Comprehensive
Privacy Analysis and Beyond [57.10914865054868]
垂直ロジスティック回帰(VLR)をミニバッチ降下勾配で訓練した。
我々は、オープンソースのフェデレーション学習フレームワークのクラスにおいて、VLRの包括的で厳密なプライバシー分析を提供する。
論文 参考訳(メタデータ) (2022-07-19T05:47:30Z) - RACA: Relation-Aware Credit Assignment for Ad-Hoc Cooperation in
Multi-Agent Deep Reinforcement Learning [55.55009081609396]
本稿では、アドホックな協調シナリオにおいてゼロショットの一般化を実現するRACA(Relation-Aware Credit Assignment)と呼ばれる新しい手法を提案する。
RACAは、エージェント間のトポロジ構造を符号化するために、グラフベースのエンコーダ関係を利用する。
提案手法は,StarCraftIIマイクロマネジメントベンチマークとアドホック協調シナリオのベースライン手法よりも優れている。
論文 参考訳(メタデータ) (2022-06-02T03:39:27Z) - The Round Complexity of Local Operations and Classical Communication
(LOCC) in Random-Party Entanglement Distillation [4.211128681972148]
分散量子情報処理のための強力な運用パラダイムは、事前に共有された絡み合いを操作することである。
与えられたタスクのLOCCラウンドの複雑さは、タスクを完了するために古典的なコミュニケーションのラウンドがいくつ必要かを記述する。
3つの量子ビットでのランダムなパーティー蒸留では、最適なプロトコルで必要とされる通信ラウンドの数は、使用する絡み合い尺度に依存する。
論文 参考訳(メタデータ) (2022-04-02T06:47:43Z) - Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth
Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。
定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。
我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
論文 参考訳(メタデータ) (2021-06-30T18:32:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。