論文の概要: Cheat-Penalised Quantum Weak Coin-Flipping
- arxiv url: http://arxiv.org/abs/2510.03218v1
- Date: Fri, 03 Oct 2025 17:54:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-06 16:35:52.528071
- Title: Cheat-Penalised Quantum Weak Coin-Flipping
- Title（参考訳）: チートパーナライズした量子弱銅フリップ
- Authors: Atul Singh Arora, Carl A. Miller, Mauro E. S. Morales, Jamie Sikora,
- Abstract要約: 我々は、不正に罰せられる弱いコインフリップと呼ばれる変種を研究し、もしパーティーが不正に捕まったら、彼らはLambda$ポイントを失う。
同じスペース要件に対して、悪意のある関係者が結果に偏りがあるかを低くするかを、どのように選択できるかを示します。
この結果から,マルチパーティ計算のためのセキュアで実用的な量子プロトコルが実現可能である可能性が示唆された。
- 参考スコア（独自算出の注目度）: 0.968297475519304
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Coin-flipping is a fundamental task in two-party cryptography where two remote mistrustful parties wish to generate a shared uniformly random bit. While quantum protocols promising near-perfect security exist for weak coin-flipping -- when the parties want opposing outcomes -- it has been shown that they must be inefficient in terms of their round complexity, and it is an open question of how space efficient they can be. In this work, we consider a variant called cheat-penalised weak coin-flipping in which if a party gets caught cheating, they lose $\Lambda$ points (compared to $0$ in the standard definition). We find that already for a small cheating penalty, the landscape of coin-flipping changes dramatically. For example, with $\Lambda=0.01$, we exhibit a protocol where neither Alice nor Bob can bias the result in their favour beyond $1/2 + 10^{-8}$, which uses $24$ qubits and $10^{16}$ rounds of communication (provably $10^{7}$ times better than any weak coin-flipping protocol with matching security). For the same space requirements, we demonstrate how one can choose between lowering how much a malicious party can bias the result (down to $1/2 + 10^{-10}$) and reducing the rounds of communication (down to $25,180$), depending on what is preferred. To find these protocols, we make two technical contributions. First, we extend the point game-protocol correspondence introduced by Kitaev and Mochon, to incorporate: (i) approximate point games, (ii) the cheat-penalised setting, and (iii) round and space complexity. Second, we give the first (to the best of our knowledge) numerical algorithm for constructing (approximate) point games that correspond to high security and low complexity. Our results open up the possibility of having secure and practical quantum protocols for multiparty computation.
- Abstract（参考訳）: コインフリッピングは、2つのリモート不信な当事者が一様ランダムな共有ビットを生成したいという、2つの暗号の基本的なタスクである。
量子プロトコルは、弱いコインフライング(弱いコインフライング)のために存在しているが、当事者が反対の成果を望む場合、それらはラウンドの複雑さの観点から非効率でなければならないことが示されている。
この研究では、不正に罰せられる弱いコインフリッピングと呼ばれる変種について検討し、あるパーティが不正に捕まった場合、彼らは$\Lambda$ポイント(標準定義では$0$)を失う。
少額の不正行為に対して、コインフライングの状況は劇的に変化している。
例えば、$\Lambda=0.01$では、アリスもボブも1/2 + 10^{-8}$以上の利益をバイアスしないプロトコルを示します。
同じスペース要件に対して、悪意ある当事者がどれだけ結果に偏りがあるか($1/2 + 10^{-10}$まで)を下げるか、そして通信のラウンドを減らし($25,180$まで)、何が望ましいかによってどのように選択できるかを示す。
これらのプロトコルを見つけるために、我々は2つの技術貢献をする。
まず、北エヴとモチョンが導入したポイントゲーム-プロトコル対応を拡張して、以下のことを組み込む。
(i)近似点ゲーム
(二)不正に処罰された設定、及び
(三)ラウンドとスペースの複雑さ。
第二に、高いセキュリティと低複雑性に対応する(近似的な)ポイントゲームを構築するための最初の(私たちの知る限りの)数値アルゴリズムを与える。
この結果から,マルチパーティ計算のためのセキュアで実用的な量子プロトコルが実現可能である可能性が示唆された。
関連論文リスト
- Pseudo-Equilibria, or: How to Stop Worrying About Crypto and Just Analyze the Game [48.93355782581436]
本稿では,暗号プロトコルを用いたゲーム解析の問題点を考察する。
疑似ナッシュ平衡という新しい解の概念を提案する。
論文 参考訳（メタデータ） (2025-06-27T10:21:28Z) - Cloning Games, Black Holes and Cryptography [50.022147589030304]
クローンゲーム解析のための新しいツールキットを提案する。
このフレームワークにより、バイナリフェーズ状態に基づいて新しいクローンゲームを分析することができる。
連成位相の変分最適境界は、ブラックホールの理想化されたモデルで衝突する情報について定量的な洞察を与えることを示す。
論文 参考訳（メタデータ） (2024-11-07T14:09:32Z) - Juggernaut: Efficient Crypto-Agnostic Byzantine Agreement [1.77513002450736]
信頼できる設定によって、$tn/2$の汚職が存在する場合、ビザンツ協定の問題を解決することはよく知られている。
本稿では, レジリエンスに最適化されたビザンチン合意プロトコルを, 暗号に依存しないものに変換するコンパイラを提案する。
以上の結果より,少なくとも$n$の2因子はビット複雑性の最先端性を改善し,早期停止(決定論的)あるいは期待される一定ラウンド複雑性(ランダム化)を提供する。
論文 参考訳（メタデータ） (2024-10-15T23:44:29Z) - Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed? [4.465134753953128]
同期分散システムにおいて,通信リンクから障害当事者への通信がメッセージの送信を省略できる場合,$n$の自律的パーティによる合意に達するという問題について検討する。
我々は、$O(sqrtnlog2 n)$ラウンドで動作し、$O(n2log3 n)$通信ビットを送信するランダム化アルゴリズムを設計する。
MCアルゴリズムが$O(R)$呼び出しを使用する場合、$Omega(fracn2maxR,nlog n)$ラウンドで動作しないことを示す。
論文 参考訳（メタデータ） (2024-05-08T02:17:10Z) - Improving device-independent weak coin flipping protocols [0.08192907805418585]
弱いコインフリップは、アリスとボブが遠隔でコインをひっくり返すが、反対の結果を求める暗号的なタスクである。
最高のプロトコルは10年以上前にSilman, Chailloux, Aharon, Kerenidis, Pironio, Massarによって考案された。
我々は、$n-1$を$n$デバイスからテストする方法を示し、残りのデバイスの性能を、後からプロトコルで使用するために見積もる。
論文 参考訳（メタデータ） (2024-04-25T23:17:37Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - A Quantum Approach For Reducing Communications in Classical Secure Computations with Long Outputs [2.3465488122819123]
我々は、2つの当事者が長い出力でセキュアな計算を行いたいという古典的な暗号問題について研究する。
本研究では,セキュリティを近似したセキュアな関数サンプリングを実現するために,まず量子暗号プロトコルを設計する。
論文 参考訳（メタデータ） (2023-10-08T16:07:46Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳（メタデータ） (2021-10-25T02:53:24Z) - Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's
Post-Quantum Security [67.06003361150228]
作業の証明(英: proof of work、PoW)は、当事者が計算タスクの解決にいくらかの労力を費やしたことを他人に納得させることができる重要な暗号構造である。
本研究では、量子戦略に対してそのようなPoWの連鎖を見つけることの難しさについて検討する。
我々は、PoWs問題の連鎖が、マルチソリューションBernoulliサーチと呼ばれる問題に還元されることを証明し、量子クエリの複雑さを確立する。
論文 参考訳（メタデータ） (2020-12-30T18:03:56Z) - Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm
for Stochastic Bandits with Corruptions [91.8283876874947]
我々は,T段の固定予算設定において,敵対的腐敗を伴う連続的包帯に対する最適な腕識別(BAI)問題を考察した。
我々は, 汚職の量に依存しない新しいランダム化アルゴリズム, Probabilistic Shrinking($u$) (PSS($u$)) を設計する。
CPS が十分に大きいとき、BAI 確率を$Trightarrow infty$ として達成できるアルゴリズムは存在しない。
論文 参考訳（メタデータ） (2020-10-15T17:34:26Z) - Quantum weak coin flipping with a single photon [3.0969191504482247]
弱いコインフリップは、現代の通信ネットワークのセキュリティを保証する基本的な暗号プリミティブの1つである。
単一の光子と線形光学のみを必要とする実用的なプロトコルを提案する。
しきい値の単光子検出器を用いた場合においても公平かつバランスが取れ、エプシロン=1/sqrt2-1/2approx 0.207$のバイアスに達する。
論文 参考訳（メタデータ） (2020-02-20T20:30:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。