論文の概要: A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip
- arxiv url: http://arxiv.org/abs/2005.01565v3
- Date: Sun, 27 Oct 2024 07:52:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-01 16:56:10.539093
- Title: A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip
- Title（参考訳）: 適応型全情報係数フリップの低次境界
- Authors: Iftach Haitner, Yonatan Karidi-Heller,
- Abstract要約: コインフリッピングプロトコルでは、計算上の敵は、プロトコルの実行に沿ってどのパーティを腐敗させるかを選択することができる。
我々は、(丸い複雑さの)$n$-partyプロトコルが$omega(sqrtn)$ corruptionsに回復可能であることを証明している。
- 参考スコア（独自算出の注目度）: 2.469280630208887
- License:
- Abstract: In a distributed coin-flipping protocol, Blum [ACM Transactions on Computer Systems '83], the parties try to output a common (close to) uniform bit, even when some adversarially chosen parties try to bias the common output. In an adaptively secure full-information coin flip, Ben-Or and Linial [FOCS '85], the parties communicate over a broadcast channel, and a computationally unbounded adversary can choose which parties to corrupt along the protocol execution. Ben-Or and Linial proved that the $n$-party majority protocol is resilient to $O(\sqrt{n})$ corruptions (ignoring poly-logarithmic factors), and conjectured this is a tight upper bound for any $n$-party protocol (of any round complexity). Their conjecture was proved to be correct for single-turn (each party sends a single message) single-bit (a message is one bit) protocols Lichtenstein, Linial and Saks [Combinatorica '89], symmetric protocols Goldwasser, Tauman Kalai and Park [ICALP '15], and recently for (arbitrary message length) single-turn protocols Tauman Kalai, Komargodski and Raz [DISC '18]. Yet, the question of many-turn protocols was left entirely open. In this work, we close the above gap, proving that no $n$-party protocol (of any round complexity) is resilient to $\omega(\sqrt{n})$ (adaptive) corruptions.
- Abstract（参考訳）: 分散コインフリッピングプロトコルであるBlum[ACM Transactions on Computer Systems '83]では、一部の逆選択した当事者が共通の出力をバイアスしようとする場合でも、当事者は共通の(クロースに)均一なビットを出力しようとする。
適応的に安全な全情報コインフリップであるBen-OrとLinial[FOCS '85]では、当事者はブロードキャストチャネルを介して通信し、計算未拘束の敵は、プロトコル実行に沿ってどの当事者を腐敗させるかを選択できる。
Ben-Or と Linial は、$n$-party majority protocol が$O(\sqrt{n})$ corruptions (ポリ対数的因子を無視した) に耐性があることを証明し、これは任意の$n$-party protocol の厳密な上限であると推測した。
彼らの予想は、シングルターン(それぞれが1つのメッセージを送信する)のシングルビットプロトコル(メッセージは1ビット)、リヒテンシュタイン、リニアル、サクス(英語版)(Combinatorica '89]、対称プロトコル(英語版)(Goldwasser, Tauman Kalai and Park [ICALP '15])、最近(任意メッセージ長)のシングルターンプロトコル(英語版)(Tauman Kalai, Komargodski and Raz [DISC '18])に対して正しいことが証明された。
しかし、多ターンプロトコルの問題は完全に解決された。
この作業では、上記のギャップを埋めて、$n$のパーティプロトコル(どんなラウンドの複雑さでも)が$\omega(\sqrt{n})$(適応的な)汚職に回復可能であることを証明します。
関連論文リスト
- Juggernaut: Efficient Crypto-Agnostic Byzantine Agreement [1.77513002450736]
信頼できる設定によって、$tn/2$の汚職が存在する場合、ビザンツ協定の問題を解決することはよく知られている。
本稿では, レジリエンスに最適化されたビザンチン合意プロトコルを, 暗号に依存しないものに変換するコンパイラを提案する。
以上の結果より,少なくとも$n$の2因子はビット複雑性の最先端性を改善し,早期停止(決定論的)あるいは期待される一定ラウンド複雑性(ランダム化)を提供する。
論文 参考訳（メタデータ） (2024-10-15T23:44:29Z) - Tyche: Collateral-Free Coalition-Resistant Multiparty Lotteries with Arbitrary Payouts [23.27199615640474]
効率的な多人数抽選を行うためのプロトコル群であるTycheを提案する。
我々のプロトコルはコミット・アンド・リベラルなアプローチに基づいており、衝突耐性ハッシュ関数のみを必要とする。
私たちのプロトコルは安全で公平で、参加者のプライバシを保護しているものもあります。
論文 参考訳（メタデータ） (2024-09-05T12:19:37Z) - Improving device-independent weak coin flipping protocols [0.08192907805418585]
弱いコインフリップは、アリスとボブが遠隔でコインをひっくり返すが、反対の結果を求める暗号的なタスクである。
最高のプロトコルは10年以上前にSilman, Chailloux, Aharon, Kerenidis, Pironio, Massarによって考案された。
我々は、$n-1$を$n$デバイスからテストする方法を示し、残りのデバイスの性能を、後からプロトコルで使用するために見積もる。
論文 参考訳（メタデータ） (2024-04-25T23:17:37Z) - 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) - Communication Lower Bounds for Cryptographic Broadcast Protocols [7.233482131020069]
ブロードキャストプロトコルは、悪質な当事者による攻撃に対してさえも、指定された送信者の入力に$n$のパーティが同意することを可能にする。
この設定内の任意のブロードキャストプロトコルを攻撃して、任意のパーティに$k$の他のパーティへのメッセージ送信を強制できることを示します。
論文 参考訳（メタデータ） (2023-09-04T09:24:39Z) - Compression for Qubit Clocks [55.38708484314286]
クォービットクロックの同じ準備状態に対して$n$の圧縮プロトコルを提案する。
このプロトコルは、状態を$(1/2)log n$ qubitsと$(1/2)log n$ classical bitsに忠実にエンコードする。
論文 参考訳（メタデータ） (2022-09-14T09:45:53Z) - Distributed Contextual Linear Bandits with Minimax Optimal Communication
Cost [48.288452411283444]
そこでは,$N$エージェントが協調して,$d$次元の特徴を持つ線形帯域最適化問題を解く。
本稿では,LinUCBアルゴリズムの分散バッチ除去版であるDisBE-LUCBを提案する。
我々は、DisBE-LUCBの通信コストがわずか$tildemathcalO(dN)$であり、その後悔は少なくとも$tildemathcalO(dN)$であることを示す。
論文 参考訳（メタデータ） (2022-05-26T05:56:23Z) - Unconditionally secure relativistic multi-party biased coin flipping and
die rolling [0.0]
我々は、相対論的多党偏り型転がりプロトコルを導入し、コインフリップを$M geq 2$party、$N geq 2$ outcomesに一般化する。
提案手法は,すべての当事者が出力を受け取り,任意の当事者が秘密入力を行わないような,最も一般的なランダムなマルチパーティ計算を,無条件のセキュリティで実装できることを実証する。
論文 参考訳（メタデータ） (2021-07-19T23:28:32Z) - On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。
目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文 参考訳（メタデータ） (2020-09-21T04:13:34Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z) - Moniqua: Modulo Quantized Communication in Decentralized SGD [45.468216452357375]
Moniquaは、分散化されたアルゴリズムが量子化された通信を使用することを可能にする技術である。
我々は,Moniquaが他の量子化された分散アルゴリズムよりもウォールクロック時間に早く収束することを示す。
論文 参考訳（メタデータ） (2020-02-26T20:58:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。