Welcome to the resource topic for 2023/798
Title:
Generalized Hybrid Search and Applications
Authors: Alexandru Cojocaru, Juan Garay, Fang Song
Abstract:In this work we examine the hardness of solving various search problems by hybrid quantum-classical strategies, namely, by algorithms that have both quantum and classical capabilities. Specifically, for search problems that are allowed to have multiple solutions and in which the input is sampled according to uniform or Bernoulli 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 \tau_c classical queries and \tau_c quantum queries succeeds in finding a preimage of 1 for a function sampled from D is at most \nu_D \cdot (2\sqrt{\tau_c} + 2\tau_q + 1)^2, where \nu_D captures the average (over D) fraction of preimages of 1.
As applications of our 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.
ePrint: https://eprint.iacr.org/2023/798
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .