Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's Post-Quantum Security

• URL: http://arxiv.org/abs/2012.15254v4
• Date: Mon, 6 Mar 2023 18:05:25 GMT
• Title: Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's Post-Quantum Security
• Authors: Alexandru Cojocaru, Juan Garay, Aggelos Kiayias, Fang Song, Petros Wallden
• Abstract summary: 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. 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.
• Score: 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.

Related papers

• The Latency Price of Threshold Cryptosystem in Blockchains [52.359230560289745]
  We study the interplay between threshold cryptography and a class of blockchains that use Byzantine-fault tolerant (BFT) consensus protocols. Existing approaches for threshold cryptosystems introduce a latency overhead of at least one message delay for running the threshold cryptographic protocol. We propose a mechanism to eliminate this overhead for blockchain-native threshold cryptosystems with tight thresholds.
  arXiv  Detail & Related papers  (2024-07-16T20:53:04Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• From Portfolio Optimization to Quantum Blockchain and Security: A Systematic Review of Quantum Computing in Finance [0.0]
  We provide an overview of the recent work in the quantum finance realm from various perspectives. The applications in consideration are Portfolio Optimization, Fraud Detection, and Monte Carlo methods for derivative pricing and risk calculation. We give a comprehensive overview of the applications of quantum computing in the field of blockchain technology.
  arXiv  Detail & Related papers  (2023-06-12T19:53:23Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• Quantum-resistance in blockchain networks [46.63333997460008]
  This paper describes the work carried out by the Inter-American Development Bank, the IDB Lab, LACChain, Quantum Computing (CQC), and Tecnologico de Monterrey to identify and eliminate quantum threats in blockchain networks. The advent of quantum computing threatens internet protocols and blockchain networks because they utilize non-quantum resistant cryptographic algorithms.
  arXiv  Detail & Related papers  (2021-06-11T23:39:25Z)
• Quantum Advantage on Proof of Work [0.0]
  We make the case that quantum devices provide a computational advantage in performing Proof-of-Work (PoW) in the context of Bitcoin. This has strong consequences regarding both quantum-based attacks on the integrity of the entirety of the blockchain, as well as more legitimate uses of quantum computation for the purpose of mining Bitcoin and other cryptocurrencies.
  arXiv  Detail & Related papers  (2021-05-05T01:27:31Z)
• Vulnerability of Blockchain Technologies to Quantum Attacks [0.0]
  Quantum computation represents a threat to many cryptographic protocols in operation today. It has been estimated that by 2035, there will exist a quantum computer capable of breaking the vital cryptographic scheme RSA2048.
  arXiv  Detail & Related papers  (2021-05-05T01:01:42Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)
• A Quantum Money Solution to the Blockchain Scalability Problem [3.89615163169501]
  We give the first example of the use of smart contracts in a quantum setting. We describe a simple hybrid classical-quantum payment system whose main ingredients are a classical blockchain capable of handling stateful smart contracts. Our hybrid payment system employs quantum states as banknotes and a classical blockchain to settle disputes and to keep track of the valid serial numbers.
  arXiv  Detail & Related papers  (2020-02-27T09:40:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.