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

【Author】 Cojocaru, Alexandru; Garay, Juan; Kiayias, Aggelos; Song, Fang; Wallden, Petros

【Source】QUANTUM

【影响因子】6.439

【Abstract】A proof of work (PoW) is an important cryptographic construct which enables a party to convince other parties that they have invested some effort in solving a computational task. Arguably, its main impact has been in the setting of cryptocur-rencies such as Bitcoin and its underlying blockchain protocol, which have 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 mod-els. 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. At the same time, the rapid development in quantum computing makes the threats to cryptography more and more concerning. 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 due to Zhandry [Crypto 2019]. As an application, we revisit the formal treatment of security of the core of the Bitcoin consensus protocol, called the Bitcoin backbone [Eurocrypt 2015], in a setting where the adversary has quantum capabilities while the honest parties remain classical, and show that the protocol???s security holds under a quantum analogue of the classical ???honest majority??? assumption that we formulate. Our analysis indicates that the security of the Bitcoin backbone protocol is guaranteed provided that 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 probability of success of a single classical query to the protocol???s underlying hash function. Somewhat surprisingly, the wait time for safe settlement of transactions in the case of quantum adversaries matches (up to a constant) the safe settlement time in the classical case.

【Keywords】

【发表时间】2023 9-Mar

【收录时间】2023-06-04

【文献类型】

【主题类别】

--