Fugu-MT 論文翻訳(概要): Subcubic Coin Tossing in Asynchrony without Setup

論文の概要: Subcubic Coin Tossing in Asynchrony without Setup

arxiv url: http://arxiv.org/abs/2603.02071v1
Date: Mon, 02 Mar 2026 16:58:44 GMT
ステータス: 翻訳完了
システム内更新日: 2026-03-03 19:50:56.986715
Title: Subcubic Coin Tossing in Asynchrony without Setup
Title（参考訳）: セットアップなしで非同期でサブキュビックコインを投げる
Authors: Mose Mizrahi, Roger Wattenhofer,
Abstract要約: コイントスキング(英: coin tossing)とは、パーティーが予測不可能なランダムな値に合意しようとするタスクであり、ビザンチン党の影響により失敗する可能性がある。我々は、大まかに言えば、強力だがコストがかかる一般的な硬貨を安価だが品質の低い硬貨に変えるための、適応的に安全な委員会ベースの方法を提案する。我々は、$widetildeO(varepsilon-2kn3 - 2/k)$の通信で$widetildeO($widetildeO)の安いコインを得るために、$widetildeO(varepsilon-2kn3 - 2/k)$の強い(非常に稀に失敗する)コインをどのように使うかを示す。
参考スコア（独自算出の注目度）: 34.662213518530315
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider an asynchronous network of $n$ parties connected to each other via secure channels, up to $t$ of which are byzantine. We study common coin tossing, a task where the parties try to agree on an unpredictable random value, with some chance of failure due to the byzantine parties' influence. Coin tossing is a well known and often studied task due to its use in byzantine agreement. In this work, we present an adaptively secure committee-based method to roughly speaking turn strong but costly common coins into cheaper but lower-quality ones. For all $k > 2$ and $\varepsilon > 0$, we show how to use a strong (very rarely failing) coin that costs $\widetilde{O}(n^k)$ bits of communication to get a cheaper coin that costs $\widetilde{O}(\varepsilon^{-2k}n^{3 - 2/k})$ bits of communication. This latter coin tolerates $\varepsilon n$ fewer byzantine parties than the former, and it fails with an arbitrarily small constant probability. For any $\varepsilon > 0$, our method allows us to get a perfectly secure binary coin that tolerates $t \leq (\frac{1}{4} - \varepsilon)n$ faults with $O(n^{2.5}(\varepsilon^{-8} + \log n))$ messages of size $O(\log n)$, as well as a setup-free cryptographically secure binary coin that tolerates $t \leq (\frac{1}{3} - \varepsilon)n$ faults with $O(n^{7/3}\varepsilon^{-6}κ\log n)$ bits of communication (where $κ= Ω(\log n)$ is a cryptographic security paramater). These coins both have $O(\log n)$ latency. They are to our knowledge the first setup-free coins that cost $o(n^3)$ bits of communication but still succeed with at least constant probability against $t = Θ(n)$ adaptive byzantine faults. As such, they for the first time enable setup-free (and even perfectly secure) asynchronous byzantine agreement with $o(n^3)$ communication against $Θ(n)$ adaptive byzantine faults.
Abstract（参考訳）: セキュアなチャネルを通じて接続された$n$のパーティの非同期ネットワークを、最大$t$はビザンチンとみなす。両当事者が予測不可能なランダムな値に合意しようとする作業である共通貨幣投射について検討する。コイン投げはよく知られ、ビザンチン協定で使用されるためしばしば研究される課題である。本研究では,高額だが高額な共通硬貨を安価で低品質の硬貨に大まかに話すための,適応的に安全な委員会ベース方式を提案する。すべての$k > 2$と$\varepsilon > 0$に対して、$\widetilde{O}(n^k)$の通信ビットを使って$\widetilde{O}(\varepsilon^{-2k}n^{3 - 2/k})$の通信ビットを得る方法を示す。後者の硬貨は、前者よりもベザンチン派がより少ない$\varepsilon n$を許容し、任意に小さな確率で失敗する。例えば、$t \leq (\frac{1}{4} - \varepsilon)n$ faults with $O(n^{2.5}(\varepsilon^{-8} + \log n))$ message of size $O(\log n)$, and tolerates $t \leq (\frac{1}{3} - \varepsilon)n$ faults with $O(n^{7/3}\varepsilon^{-6}κ\log n)$ bits of communication (where $κ= Ω(\log n$$) is a cryptomater security. これらのコインはどちらも$O(\log n)$遅延を持つ。彼らは、最初のセットアップフリーなコインで、$o(n^3)$ビットの通信をしたが、少なくとも一定の確率で、少なくとも$t = s(n)$アダプティブ・ビザンチン・フォールトに対して成功している。したがって、これらは初めて$o(n^3)$とのセットアップフリーな(そして完璧にセキュアな)非同期ビザンチン契約を可能にし、$(n)$アダプティブ・ビザンチンフォールトに対する通信を可能にする。

論文の概要: Subcubic Coin Tossing in Asynchrony without Setup

関連論文リスト