International Association
for Cryptologic Research

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.

We give a tighter lifting theorem for security games in the quantum random oracle model. At the core of our main result lies a novel measure-and-reprogram framework that we call coherent reprogramming. This framework gives a tighter lifting theorem for query complexity problems, that only requires purely classical reasoning. As direct applications of our lifting theorem, we first provide a quantum direct product theorem in the average case --- i.e., an enabling tool to determine the hardness of solving multi-instance security games. This allows us to derive in a straightforward manner the hardness of various security games, for example (i) the non-uniform hardness of salted games, (ii) the hardness of specific cryptographic tasks such as the multiple instance version of one-wayness and collision-resistance, and (iii) uniform or non-uniform hardness of many other games.

Secure delegated quantum computing allows a computationally weak client to outsource an arbitrary quantum computation to an untrusted quantum server in a privacy-preserving manner. One of the promising candidates to achieve classical delegation of quantum computation is classical-client remote state preparation ($\sf{RSP}_{CC}$), where a client remotely prepares a quantum state using a classical channel. However, the privacy loss incurred by employing $\sf{RSP}_{CC}$ as a sub-module is unclear. In this work, we investigate this question using the Constructive Cryptography framework by Maurer and Renner (ICS'11). We first identify the goal of $\sf{RSP}_{CC}$ as the construction of ideal \RSP resources from classical channels and then reveal the security limitations of using $\sf{RSP}_{CC}$. First, we uncover a fundamental relationship between constructing ideal \RSP resources (from classical channels) and the task of cloning quantum states. Any classically constructed ideal \RSP resource must leak to the server the full classical description (possibly in an encoded form) of the generated quantum state, even if we target computational security only. As a consequence, we find that the realization of common \RSP resources, without weakening their guarantees drastically, is impossible due to the no-cloning theorem. Second, the above result does not rule out that a specific $\sf{RSP}_{CC}$ protocol can replace the quantum channel at least in some contexts, such as the Universal Blind Quantum Computing ($\sf{UBQC}$) protocol of Broadbent et al. (FOCS '09). However, we show that the resulting UBQC protocol cannot maintain its proven composable security as soon as $\sf{RSP}_{CC}$ is used as a subroutine. Third, we show that replacing the quantum channel of the above $\sf{UBQC}$ protocol by the $\sf{RSP}_{CC}$ protocol QFactory of Cojocaru et al. (Asiacrypt '19) preserves the weaker, game-based, security of $\sf{UBQC}$.

The functionality of classically-instructed remotely prepared random secret qubits was introduced in (Cojocaru et al. 2018) as a way to enable classical parties to participate in secure quantum computation and communications protocols. The idea is that a classical party (client) instructs a quantum party (server) to generate a qubit to the server’s side that is random, unknown to the server but known to the client. Such task is only possible under computational assumptions. In this contribution we define a simpler (basic) primitive consisting of only BB84 states, and give a protocol that realizes this primitive and that is secure against the strongest possible adversary (an arbitrarily deviating malicious server). The specific functions used, were constructed based on known trapdoor one-way functions, resulting to the security of our basic primitive being reduced to the hardness of the Learning With Errors problem. We then give a number of extensions, building on this basic module: extension to larger set of states (that includes non-Clifford states); proper consideration of the abort case; and verifiablity on the module level. The latter is based on “blind self-testing”, a notion we introduced, proved in a limited setting and conjectured its validity for the most general case.