Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2311.03723

Generalized Hybrid Search and Applications to Blockchain and Hash Function Security

Alexandru Cojocaru, Juan A. Garay, Fang Song

Published Nov 7, 2023• 0 citations
arXivHTMLPDF

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 $τ_c$ classical and $τ_q$ quantum queries succeeds in finding a preimage of $1$ for a function sampled from $D$ is at most $ν_D \cdot(2\sqrt{τ_c} + 2τ_q + 1)^2$, where $ν_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.

DOI
10.48550/arxiv.2311.03723

Related papers

Post-Quantum Security of the Bitcoin Backbone and Quantum Multi-Solution Bernoulli Search.

Alexandru Cojocaru, Juan A. Garay, Aggelos Kiayias +2 more

Bitcoin and its underlying blockchain protocol have recently received significant attention in the context of building distributed systems and foundations of the consensus problem. At the same time, the rapid development in quantum computing makes the threats to cryptography more and more concerning. In this work, we revisit the formal security of the core of the Bitcoin consensus protocol, called the Bitcoin backbone (Eurocrypt 2015), in the presence of quantum adversaries -- i.e. adversaries equipped with quantum computers. We show that the security of the Bitcoin backbone holds under a quantum analogue of the ``honest majority'' assumption that we develop. The critical ingredient of proving security of the blockchain is to analyzing the quantum query complexity of a Chain-of-Proofs-of-Work search problem. This problem in turn reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity. This can be viewed as 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 powerful recording technique due to Zhandry (Crypto 2019). 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. Perhaps 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 and thus does not result in any further overhead.

•Dec 30, 2020•3 citations

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

Alexandru Cojocaru, Juan A. Garay, Aggelos Kiayias +2 more

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.

arXiv:2012.15254•Quantum•Mar 9, 2023•10 citations

Tight bounds for hybrid quantum-classical query algorithms

Andris Ambainis, András Gilyén, Martins Kokainis

We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most $q$ oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision $ε$ requires $Θ(\frac{1}{q ε^2})$ queries; (ii) (Unbiased) Amplitude estimation up to a precision $ε$ requires $Θ(\frac{p(1-p)}{q ε^2})$ queries; (iii) Search among $N$ items requires $Θ(\frac{N}{q})$ queries; (iv) Two level AND-OR tree (AND of $m$ ORs, with $n$ inputs to each OR) requires $Θ(\frac{nm}{q})$ queries. All of these bounds are optimal up to a constant factor, for all $q$ from 1, corresponding to the classical complexity, to $Q(f)$, the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.

quant-pharXiv:2610.06803•Oct 6, 2026•1 citation

Post-Quantum Blockchain Proofs of Work.

Alexandru Cojocaru, Juan A. Garay, Aggelos Kiayias +2 more

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 due to Zhandry (Crypto 2019). In addition, we revisit the formal treatment of security of the core of the Bitcoin consensus protocol, called the Bitcoin backbone (Eurocrypt 2015), against quantum adversaries and show that its security holds under a quantum analogue of the ``honest majority'' assumption that we formulate. Our analysis indicates that 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 in the case of quantum adversaries matches the safe settlement time in the classical case.

•Dec 1, 2021•0 citations

Hybrid Classical–Quantum Text Search Based on Hashing

Farid Mansurovich Ablayev, Nailya Salikhova, Marat Ablayev

The paper considers the problem of finding a given substring in a text. It is known that the complexity of a classical search query in an unordered database is linear in the length of the text and a given substring. At the same time, Grover’s quantum search provides a quadratic speed-up in the complexity of the query and gives the correct result with a high probability. We propose a hybrid classical–quantum algorithm (hybrid random–quantum algorithm, to be more precise) that implements Grover’s search to find a given substring in a text. As expected, the algorithm works (a) with a high probability of obtaining the correct result and (b) with a quadratic query acceleration compared to the classical one. What is new is that our algorithm uses the uniform hash family functions technique. As a result, our algorithm is much more memory efficient (in terms of the number of qubits used) compared to previously known quantum algorithms.

arXiv:2311.01213•Mathematics•Jun 14, 2024•12 citations

Quantum Hashing: A Theoretical Framework for Post-Quantum Secure Data Structures

Pulkit Sharma

The rapid advancement of quantum computing presents a fundamental challenge to modern cryptographic security, particularly in the domain of hash functions that ensure data integrity, authentication, and blockchain security. Traditional crypto graphic hash functions such as SHA-256, SHA-3, and BLAKE2 rely on computational hardness assumptions that become obsolete in the presence of large-scale quantum computers. Shor’s algorithm can efficiently break RSA and ECC-based cryptosys tems, while Grover’s algorithm reduces the security of traditional hash functions by square root complexity, significantly weakening their preimage and collision resistance. This quantum threat necessitates the development of post-quantum secure hashing techniques that remain resilient against both classical and quantum adversaries. This paper proposes Quantum Hashing, a novel cryptographic framework that integrates quantum entanglement, lattice-based cryptography, and hybrid quantum classical hashing to construct post-quantum secure hash functions. We introduce a formal model for Quantum Collision Resistance (QCR) and provide entropy-based ran domness enhancement to ensure unpredictable hash outputs. Unlike classical hashing approaches, our framework leverages the hardness of lattice problems (e.g., Shortest Vector Problem, Learning with Errors) to withstand quantum attacks while incorpo rating Quantum Key Distribution (QKD) mechanisms to enhance entropy and key management. Furthermore, we evaluate the security of Quantum Hashing under various attack models, comparing its resistance against Grover’s search and collision attacks. We benchmark its performance against NIST Post-Quantum Cryptography (PQC) final ists, including CRYSTALS-DILITHIUM, SPHINCS+, and Falcon, demonstrating that our approach offers superior resilience while maintaining computational feasibility. Additionally, we present an implementation of Quantum Hashing using Qiskit, show casing its practical applicability in quantum circuits and quantum-secure blockchain architectures. Our findings highlight that Quantum Hashing provides a scalable, entropy-efficient, and post-quantum resilient cryptographic primitive suitable for next-generation cryptographic applications. This work paves the way for secure post-quantum digital signatures, blockchain consensus mechanisms, and zero-knowledge proof systems that require tamper-resistant hashing in a quantum computing era.

•Apr 9, 2025•0 citations
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 DDD on Boolean functions, the probability an algorithm equipped with τcτ_cτc​ classical and τqτ_qτq​ quantum queries succeeds in finding a preimage of 111 for a function sampled from DDD is at most νD⋅(2τc+2τq+1)2ν_D \cdot(2\sqrt{τ_c} + 2τ_q + 1)^2νD​⋅(2τc​​+2τq​+1)2, where νDν_DνD​ captures the average (over DDD) fraction of preimages of 111. 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 DDD. We show how to analyze its success probability for arbitrary target distributions and, importantly, its optimality for the uniform and the Bernoulli distribution cases.
Bitcoin and its underlying blockchain protocol have recently received significant attention in the context of building distributed systems and foundations of the consensus problem. At the same time, the rapid development in quantum computing makes the threats to cryptography more and more concerning. In this work, we revisit the formal security of the core of the Bitcoin consensus protocol, called the Bitcoin backbone (Eurocrypt 2015), in the presence of quantum adversaries -- i.e. adversaries equipped with quantum computers. We show that the security of the Bitcoin backbone holds under a quantum analogue of the ``honest majority'' assumption that we develop. The critical ingredient of proving security of the blockchain is to analyzing the quantum query complexity of a Chain-of-Proofs-of-Work search problem. This problem in turn reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity. This can be viewed as 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 powerful recording technique due to Zhandry (Crypto 2019). 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)O(p^{-1/2})O(p−1/2) classical ones, where ppp is the probability of success of a single classical query to the protocol's underlying hash function. Perhaps 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 and thus does not result in any further overhead.
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.
We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most qqq oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision εεε requires Θ(1qε2)Θ(\frac{1}{q ε^2})Θ(qε21​) queries; (ii) (Unbiased) Amplitude estimation up to a precision εεε requires Θ(p(1−p)qε2)Θ(\frac{p(1-p)}{q ε^2})Θ(qε2p(1−p)​) queries; (iii) Search among NNN items requires Θ(Nq)Θ(\frac{N}{q})Θ(qN​) queries; (iv) Two level AND-OR tree (AND of mmm ORs, with nnn inputs to each OR) requires Θ(nmq)Θ(\frac{nm}{q})Θ(qnm​) queries. All of these bounds are optimal up to a constant factor, for all qqq from 1, corresponding to the classical complexity, to Q(f)Q(f)Q(f), the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.
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 due to Zhandry (Crypto 2019). In addition, we revisit the formal treatment of security of the core of the Bitcoin consensus protocol, called the Bitcoin backbone (Eurocrypt 2015), against quantum adversaries and show that its security holds under a quantum analogue of the ``honest majority'' assumption that we formulate. Our analysis indicates that 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)O(p^{-1/2})O(p−1/2) classical ones, where ppp 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 in the case of quantum adversaries matches the safe settlement time in the classical case.
The paper considers the problem of finding a given substring in a text. It is known that the complexity of a classical search query in an unordered database is linear in the length of the text and a given substring. At the same time, Grover’s quantum search provides a quadratic speed-up in the complexity of the query and gives the correct result with a high probability. We propose a hybrid classical–quantum algorithm (hybrid random–quantum algorithm, to be more precise) that implements Grover’s search to find a given substring in a text. As expected, the algorithm works (a) with a high probability of obtaining the correct result and (b) with a quadratic query acceleration compared to the classical one. What is new is that our algorithm uses the uniform hash family functions technique. As a result, our algorithm is much more memory efficient (in terms of the number of qubits used) compared to previously known quantum algorithms.
The rapid advancement of quantum computing presents a fundamental challenge to modern cryptographic security, particularly in the domain of hash functions that ensure data integrity, authentication, and blockchain security. Traditional crypto graphic hash functions such as SHA-256, SHA-3, and BLAKE2 rely on computational hardness assumptions that become obsolete in the presence of large-scale quantum computers. Shor’s algorithm can efficiently break RSA and ECC-based cryptosys tems, while Grover’s algorithm reduces the security of traditional hash functions by square root complexity, significantly weakening their preimage and collision resistance. This quantum threat necessitates the development of post-quantum secure hashing techniques that remain resilient against both classical and quantum adversaries. This paper proposes Quantum Hashing, a novel cryptographic framework that integrates quantum entanglement, lattice-based cryptography, and hybrid quantum classical hashing to construct post-quantum secure hash functions. We introduce a formal model for Quantum Collision Resistance (QCR) and provide entropy-based ran domness enhancement to ensure unpredictable hash outputs. Unlike classical hashing approaches, our framework leverages the hardness of lattice problems (e.g., Shortest Vector Problem, Learning with Errors) to withstand quantum attacks while incorpo rating Quantum Key Distribution (QKD) mechanisms to enhance entropy and key management. Furthermore, we evaluate the security of Quantum Hashing under various attack models, comparing its resistance against Grover’s search and collision attacks. We benchmark its performance against NIST Post-Quantum Cryptography (PQC) final ists, including CRYSTALS-DILITHIUM, SPHINCS+, and Falcon, demonstrating that our approach offers superior resilience while maintaining computational feasibility. Additionally, we present an implementation of Quantum Hashing using Qiskit, show casing its practical applicability in quantum circuits and quantum-secure blockchain architectures. Our findings highlight that Quantum Hashing provides a scalable, entropy-efficient, and post-quantum resilient cryptographic primitive suitable for next-generation cryptographic applications. This work paves the way for secure post-quantum digital signatures, blockchain consensus mechanisms, and zero-knowledge proof systems that require tamper-resistant hashing in a quantum computing era.