論文の概要: Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security
- arxiv url: http://arxiv.org/abs/2311.03723v1
- Date: Tue, 7 Nov 2023 04:59:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-08 16:50:09.349707
- Title: Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security
- Title（参考訳）: 一般化ハイブリッド検索とブロックチェーンとハッシュ関数セキュリティへの応用
- Authors: Alexandru Cojocaru and Juan Garay and Fang Song
- Abstract要約: まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
- 参考スコア（独自算出の注目度）: 50.16790546184646
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work we first examine the hardness of solving various search problems
by hybrid quantum-classical strategies, namely, by algorithms that have both
quantum and classical capabilities. We then construct a hybrid
quantum-classical search algorithm and analyze its success probability.
Regarding the former, for search problems that are allowed to have multiple
solutions and in which the input is sampled according to arbitrary
distributions we establish their hybrid quantum-classical query complexities --
i.e., given a fixed number of classical and quantum queries, determine what is
the probability of solving the search task. At a technical level, our results
generalize the framework for hybrid quantum-classical search algorithms
proposed by Rosmanis. Namely, for an arbitrary distribution $D$ on Boolean
functions, the probability an algorithm equipped with $\tau_c$ classical and
$\tau_q$ quantum queries succeeds in finding a preimage of $1$ for a function
sampled from $D$ is at most $\nu_D \cdot(2\sqrt{\tau_c} + 2\tau_q + 1)^2$,
where $\nu_D$ captures the average (over $D$) fraction of preimages of $1$. As
applications of our hardness results, we first revisit and generalize the
security of the Bitcoin protocol called the Bitcoin backbone, to a setting
where the adversary has both quantum and classical capabilities, presenting a
new hybrid honest majority condition necessary for the protocol to properly
operate. Secondly, we examine the generic security of hash functions against
hybrid adversaries. Regarding our second contribution, we design a hybrid
algorithm which first spends all of its classical queries and in the second
stage runs a ``modified Grover'' where the initial state depends on the
distribution $D$. We show how to analyze its success probability for arbitrary
target distributions and, importantly, its optimality for the uniform and the
Bernoulli distribution cases.
- Abstract（参考訳）: 本研究では,まず,量子と古典の両方の能力を持つアルゴリズムによるハイブリッド量子古典戦略を用いて,様々な探索問題の難解性を検討する。
次に,ハイブリッド量子古典探索アルゴリズムを構築し,その成功確率を分析する。
前者については、複数の解を持ち、任意の分布に従って入力がサンプリングされる探索問題に対して、それらのハイブリッド量子古典的問合せ複雑度(すなわち、一定の数の古典的および量子的問合せが与えられた場合、探索課題を解決する確率を決定する。
技術レベルでは、rosmanisが提案したハイブリッド量子古典探索アルゴリズムのフレームワークを一般化する。
すなわち、Boolean関数上の任意の分布$D$に対して、$\tau_c$ classical と $\tau_q$ の量子量子方程式を備えたアルゴリズムは、$D$からサンプリングされた関数に対して$$$1 のプリイメージを見つけるのに成功し、最も高いのは $\nu_D \cdot(2\sqrt{\tau_c} + 2\tau_q + 1)^2$ である。
ハードネスの結果の応用として、我々はまずbitcoinバックボーンと呼ばれるbitcoinプロトコルのセキュリティを再検討し、一般化し、敵が量子と古典の両方の能力を持つように設定し、プロトコルが適切に動作するために必要な新しいハイブリッドな正直な多数派条件を提示します。
次に,ハイブリッド敵に対するハッシュ関数の汎用セキュリティについて検討する。
第2のコントリビューションでは、まずすべての古典的なクエリを消費するハイブリッドアルゴリズムを設計し、第2の段階では、初期状態が分布の$D$に依存する 'modified Grover'' を実行する。
任意の対象分布に対するその成功確率を解析する方法と、その一様分布とベルヌーイ分布の場合に対する最適性を示す。
関連論文リスト
- Quantum Approximate $k$-Minimum Finding [2.810947654192424]
我々は、全ての$k geq 1$に対して近似値を扱う最適量子$k$-minimum探索アルゴリズムを提案する。
我々は、複数の観測可能量のうち、$k$最小の期待値を同定し、ハミルトンの最低基底状態エネルギーを$k$最小に決定するための効率的な量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-12-21T11:21:15Z) - A generalization of Bernstein-Vazirani algorithm with multiple secret
keys and a probabilistic oracle [0.0]
問題は、量子オラクルを使って複数の秘密鍵の集合から1つ以上の秘密鍵を見つけることである。
提案した量子アルゴリズムは(a)確率オラクルへの単一のクエリを用いて任意のキー(確実に)を取得することができる。
古典的なアルゴリズムでは、秘密鍵の1ビットも確実に見つけることができません。
論文 参考訳（メタデータ） (2023-01-21T19:34:57Z) - The NISQ Complexity of Collision Finding [2.9405711598281536]
現代の暗号における基本的なプリミティブである衝突耐性ハッシュは、同じハッシュ値を生成する入力を効率的に見つける方法がないことを保証している。
現在、量子敵はNISQのパワーを備えたフルスケールのコンピュータを必要とする。
本稿では, NISQアルゴリズムの3つの異なるモデルについて検討する。
論文 参考訳（メタデータ） (2022-11-23T13:55:28Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - 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) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-11-26T18:22:21Z) - On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs
of Sequential Work [10.43571631715192]
我々は、量子ランダムオラクルモデル(QROM)における量子アルゴリズムの分析のために、Zhandryによって導入されたいわゆる圧縮オラクル手法を再考する。
我々の主な技術的貢献は、クエリ複雑性の結果を証明するために圧縮されたオラクル技法の並列クエリの一般化を単純化するフレームワークである。
本手法の具体的な暗号的応用として,Cohen と Pietrzak が提唱した "Simple Proofs of Sequential Work" が量子攻撃に対して安全であることを示す。
論文 参考訳（メタデータ） (2020-10-22T12:44:08Z) - Optimizing Quantum Search with a Binomial Version of Grover's Algorithm [4.220030262107688]
Groverの検索アルゴリズムの重要なコンポーネントである振幅増幅は、1つまたは複数のターゲット状態の確率を体系的に増加させるために反復的アプローチを使用する。
状態をクラスに分割することで増幅手順を強化するための新しい戦略を提案する。
論文 参考訳（メタデータ） (2020-07-21T15:36:35Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。