CryptoDB
Generalized Hybrid Search with Applications to Blockchain and Hash Function Security
| Authors: |
|
|---|---|
| Download: | |
| Conference: | ASIACRYPT 2024 |
| 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 recently proposed by Rosmanis. Namely, for an arbitrary distribution D on Boolean functions, the probability that an algorithm equipped with t_c classical queries and t_q quantum queries succeeds in finding a preimage of 1 for a function sampled from D is at most v_D(2sqrt(t_c) + 2t_q + 1)^2, where v_D captures the average (over D) fraction of preimages of 1. 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” in which the initial state depends on the target distribution D. We then show how to analyze its success probability for arbitrary target distributions and, importantly, its optimality for the uniform and the Bernoulli distribution cases. As applications of our hardness results, we first revisit and generalize the formal security treatment of the Bitcoin protocol called the Bitcoin backbone [Eurocrypt 2015], 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 re-examine the generic security of hash functions [PKC 2016] against quantum-classical hybrid adversaries. |
BibTeX
@inproceedings{asiacrypt-2024-34641,
title={Generalized Hybrid Search with Applications to Blockchain and Hash Function Security},
publisher={Springer-Verlag},
author={Alexandru Cojocaru and Juan Garay and Fang Song},
year=2024
}