論文の概要: Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's
Post-Quantum Security
- arxiv url: http://arxiv.org/abs/2012.15254v4
- Date: Mon, 6 Mar 2023 18:05:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-25 04:06:17.248662
- Title: Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's
Post-Quantum Security
- Title（参考訳）: 量子多解BernoulliサーチとBitcoinのポスト量子セキュリティへの応用
- Authors: Alexandru Cojocaru, Juan Garay, Aggelos Kiayias, Fang Song, Petros
Wallden
- Abstract要約: 作業の証明(英: proof of work、PoW)は、当事者が計算タスクの解決にいくらかの労力を費やしたことを他人に納得させることができる重要な暗号構造である。
本研究では、量子戦略に対してそのようなPoWの連鎖を見つけることの難しさについて検討する。
我々は、PoWs問題の連鎖が、マルチソリューションBernoulliサーチと呼ばれる問題に還元されることを証明し、量子クエリの複雑さを確立する。
- 参考スコア（独自算出の注目度）: 67.06003361150228
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A proof of work (PoW) is an important cryptographic construct enabling a
party to convince others that they invested some effort in solving a
computational task. Arguably, its main impact has been in the setting of
cryptocurrencies such as Bitcoin and its underlying blockchain protocol, which
received significant attention in recent years due to its potential for various
applications as well as for solving fundamental distributed computing questions
in novel threat models. PoWs enable the linking of blocks in the blockchain
data structure and thus the problem of interest is the feasibility of obtaining
a sequence (chain) of such proofs. In this work, we examine the hardness of
finding such chain of PoWs against quantum strategies. We prove that the chain
of PoWs problem reduces to a problem we call multi-solution Bernoulli search,
for which we establish its quantum query complexity. Effectively, this is an
extension of a threshold direct product theorem to an average-case unstructured
search problem. Our proof, adding to active recent efforts, simplifies and
generalizes the recording technique of Zhandry (Crypto'19). As an application,
we revisit the formal treatment of security of the core of the Bitcoin
consensus protocol, the Bitcoin backbone (Eurocrypt'15), against quantum
adversaries, while honest parties are classical and show that protocol's
security holds under a quantum analogue of the classical ``honest majority''
assumption. Our analysis indicates that the security of Bitcoin backbone is
guaranteed provided the number of adversarial quantum queries is bounded so
that each quantum query is worth $O(p^{-1/2})$ classical ones, where $p$ is the
success probability of a single classical query to the protocol's underlying
hash function. Somewhat surprisingly, the wait time for safe settlement in the
case of quantum adversaries matches the safe settlement time in the classical
case.
- Abstract（参考訳）: 作業の証明(英: proof of work、PoW)は、当事者が計算タスクの解決にいくらかの労力を費やしたことを他人に納得させることができる重要な暗号構造である。
おそらく、その主な影響はBitcoinやその基盤となるブロックチェーンプロトコルといった暗号通貨の設定であり、これは近年、様々なアプリケーションの可能性や、新しい脅威モデルにおける基本的な分散コンピューティング問題の解決によって大きな注目を集めている。
PoWはブロックチェーンデータ構造におけるブロックのリンクを可能にするため、興味のある問題は、そのような証明のシーケンス(チェーン)を取得することの可能なことだ。
本研究では, 量子戦略に対する穴の連鎖を見つけることの難しさについて検討する。
我々は、ポーズ問題の連鎖が多重解ベルヌーイ探索(multi-solution bernoulli search)と呼ばれる問題に還元されることを証明する。
効果的に、これは閾値直積定理から平均ケース非構造化探索問題への拡張である。
近年の活発な取り組みに加え、Zhandry (Crypto'19) の録音技法の簡素化と一般化を図っている。
アプリケーションとして、bitcoinコンセンサスプロトコルのコアであるビットコインバックボーン(eurocrypt'15)の量子敵に対するセキュリティの形式的な扱いを再検討します。
我々の分析は、各量子クエリが$O(p^{-1/2})$classicalで、プロトコルの基盤となるハッシュ関数に対する単一の古典的クエリの成功確率が$p$であるように、Bitcoinバックボーンのセキュリティが保証されていることを示唆している。
やや意外なことに、量子敵の場合の安全な解決の待ち時間は、古典的な場合の安全な解決時間と一致する。
関連論文リスト
- The Latency Price of Threshold Cryptosystem in Blockchains [52.359230560289745]
本稿では,Byzantine-fault Tolerant(BFT)コンセンサスプロトコルを用いた,しきい値暗号とブロックチェーンのクラス間の相互作用について検討する。
しきい値暗号システムに対する既存のアプローチは、しきい値暗号プロトコルを実行するための少なくとも1つのメッセージ遅延の遅延オーバーヘッドを導入している。
しきい値が狭いブロックチェーンネイティブのしきい値暗号システムに対して,このオーバーヘッドを取り除く機構を提案する。
論文 参考訳（メタデータ） (2024-07-16T20:53:04Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - From Portfolio Optimization to Quantum Blockchain and Security: A
Systematic Review of Quantum Computing in Finance [0.0]
量子ファイナンス領域における最近の研究の概要を,様々な観点から概説する。
導出価格とリスク計算のためのPortfolio Optimization、Fraud Detection、Monte Carlo法が検討されている。
ブロックチェーン技術分野における量子コンピューティングの応用の概要を概観する。
論文 参考訳（メタデータ） (2023-06-12T19:53:23Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。
我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。
すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
論文 参考訳（メタデータ） (2023-03-02T14:18:17Z) - Quantum-resistance in blockchain networks [46.63333997460008]
本稿では、ブロックチェーンネットワークにおける量子脅威を特定し、排除するために、米国間開発銀行、IDBラボ、LACChain、量子コンピューティング(CQC)、Tecnologicalo de Monterreyによる研究について述べる。
量子コンピューティングの出現は、非量子耐性暗号アルゴリズムを利用するため、インターネットプロトコルやブロックチェーンネットワークを脅かす。
論文 参考訳（メタデータ） (2021-06-11T23:39:25Z) - Quantum Advantage on Proof of Work [0.0]
量子デバイスは、BitcoinのコンテキストでProof-of-Work(PoW)を実行する上で、計算上の優位性を提供する、と我々は主張する。
これは、ブロックチェーン全体の完全性に対する量子ベースの攻撃と、Bitcoinやその他の暗号通貨のマイニングを目的とした、より合法的な量子計算の使用の両方に対して、強力な結果をもたらす。
論文 参考訳（メタデータ） (2021-05-05T01:27:31Z) - Vulnerability of Blockchain Technologies to Quantum Attacks [0.0]
量子計算は、今日の運用中の多くの暗号プロトコルに対する脅威である。
2035年までには、重要な暗号スキームRSA2048を破ることのできる量子コンピュータが存在すると推定されている。
論文 参考訳（メタデータ） (2021-05-05T01:01:42Z) - Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
計算・比較プログラム(Computer-and-compare program)として知られる回避関数のクラスに対する量子コピー保護スキームを導入する。
我々は,量子乱数オラクルモデル(QROM)において,完全悪意のある敵に対する非自明なセキュリティを実現することを証明した。
補完的な結果として、「セキュアソフトウェアリース」という,ソフトウェア保護の概念の弱さが示される。
論文 参考訳（メタデータ） (2020-09-29T08:41:53Z) - A Quantum Money Solution to the Blockchain Scalability Problem [3.89615163169501]
量子環境におけるスマートコントラクトの利用の最初の例を示す。
本稿では、ステートフルなスマートコントラクトを処理可能な古典的ブロックチェーンを主成分とする、シンプルな古典的量子支払いシステムについて述べる。
我々のハイブリッド支払いシステムは、紛争を解決し、有効なシリアル番号を追跡するために、紙幣や古典的なブロックチェーンとして量子状態を使用している。
論文 参考訳（メタデータ） (2020-02-27T09:40:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。