Alexandru Cojocaru

In this work, we derive the first lifting theorems for establishing security in the quantum random permutation and ideal cipher models. These theorems relate the success probability of an arbitrary quantum adversary to that of a classical algorithm making only a small number of classical queries. By applying these lifting theorems, we improve previous results and obtain new quantum query complexity bounds and post-quantum security results. Notably, we derive tight bounds for the quantum hardness of the double-sided zero search game and establish the post-quantum security for the preimage resistance, one-wayness, and multi-collision resistance of constant-round sponge, as well as the collision resistance of the Davies-Meyer construction.

In this work, we derive the first lifting theorems for establishing security in the quantum random permutation and ideal cipher models. These theorems relate the success probability of an arbitrary quantum adversary to that of a classical algorithm making only a small number of classical queries. By applying these lifting theorems, we improve previous results and obtain new quantum query complexity bounds and post-quantum security results. Notably, we derive tight bounds for the quantum hardness of the double-sided zero search game and establish the post-quantum security for the preimage resistance, one-wayness, and multi-collision resistance of constant-round sponge, as well as the collision resistance of the Davies-Meyer construction.

We give novel and tighter lifting theorems for security games in the quantum random oracle model (QROM), as well as in Noisy Intermediate-Scale Quantum (NISQ) settings such as the hybrid query model, the noisy oracle and the bounded-depth models. At the core of our main results lies a novel measure-and-reprogram framework that we call coherent reprogramming. This framework gives a tighter lifting theorem for query complexity problems. Secondly, we provide, for the first time, a hybrid lifting theorem for hybrid algorithms that can perform both quantum and classical queries, as well as a lifting theorem for quantum algorithms with access to noisy oracles or bounded quantum depth. At the core of these results lies a novel measure-and-reprogram framework, called hybrid coherent measure-and-reprogramming, tailored specifically for hybrid algorithms. Equipped with both lifting theorems, we are able to prove directly both quantum and NISQ security and complexity results by calculating a single combinatorial quantity, relying solely on classical reasoning. Crucially, we derive the first direct product theorems in the average case, both in the quantum and the hybrid settings— 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 two-party computation considers the problem of two parties computing a joint function of their private inputs without revealing anything beyond the output of the computation. In this work, we take the first steps towards understanding the setting where: 1) the two parties (Alice and Bob) can communicate only via a classical channel, 2) the input of Bob is quantum and 3) the input of Alice is classical. Our first result indicates that in this setting it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. In particular, we show that the existence of a secure protocol that relies only on classical channels would contradict the quantum no-cloning argument. We circumvent this following three different approaches. The first is by considering a weaker security notion called one-sided simulation security. This notion protects the input of one party (the quantum Bob) in the standard simulation-based sense, and protects the privacy of the other party's input (the classical Alice). We realize our protocol relying on the learning with errors assumption. As a result, we put forward a first construction of secure one-sided quantum two-party computation over classical networks. The second way to circumvent the impossibility result, while at the same time providing standard simulation-based security also against Bob, is by assuming that the quantum input has an efficient classical representation. Finally, we focus our attention on the class of zero-knowledge functionalities, and provide a protocol for such a class for specific QMA relations. We note that the direct implication of our result is that Mahadev's protocol for classical verification of quantum computations (FOCS'18) can be turned into a zero-knowledge proof of quantum knowledge protocol with classical verifiers. To the best of our knowledge, we are the first to instantiate such a primitive.

Classical remote state preparation (RSPCC) is a primitive that allows an honest client to prepare a quantum state remotely with the help of an (untrustworthy) server using only a classical communication channel. With this primitive quantum protocols (such as secure delegation of quantum computations) become accessible to classical clients, by removing the need for a quantum channel. Since this cryptographic primitive’s main role is to be a building block within larger protocols, it is of utmost importance to examine its security under composition. In this work we present three results related to the composability of RSPCC protocols: 1. As our first main result, we show that no classical remote state preparation protocol RSPCC can be composable in the Abstract Cryptography framework [MR11], even when the distinguisher is computationally bounded. In other words, remote state preparation cannot be constructed with only a classical channel. 2. We further show that any classical-client delegated quantum computing protocol that uses the universal blind quantum computation (UBQC) protocol [BFK09] and a RSPCC protocol as a subroutine cannot be composable. 3. Upon relaxing the security requirement, we show that replacing the quantum channel of the UBQC protocol by the particular RSPCC protocol of [CCKW19] is secure in the game-based security framework.

Bitcoin and its underlying blockchain protocol have received recently significant attention in the context of building distributed systems as well as from the perspective of the foundations of the consensus problem. At the same time, the rapid development of quantum technologies brings the possibility of quantum computing devices from a theoretical concept to an emerging technology. Motivated by this, in this work we revisit the formal security of the core of the Bitcoin protocol, called the Bitcoin backbone, in the presence of an adversary that has access to a scalable quantum computer. We prove that the protocol’s essential properties stand in the post-quantum setting assuming a general quantum adversary with suitably bounded number of queries in the Quantum Random Oracle (QRO) model. In order to achieve this, we investigate and bound the quantum complexity of a Chain-of-Proofs-of-Work search problem which is at the core of the blockchain protocol. Our results imply that security can be shown by bounding the quantum queries so that each quantum query is worth O(p^{−1/2}) classical ones and that the wait time for safe settlement is expanded by a multiplicative factor of O(p^{−1/6}), where p is the probability of success of a single classical query to the protocol’s underlying hash function.