Cryptographic protocols, such as protocols for secure function evaluation (SFE), have played a crucial role in the development of modern cryptography. The extensive theory of these protocols, however, deals almost exclusively with classical attackers. If we accept that quantum information processing is the most realistic model of physically feasible computation, then we must ask: What classical protocols remain secure against quantum attackers? Our main contribution is showing the existence of classical two-party protocols for the secure evaluation of any polynomial-time function under reasonable computational assumptions (for example, it suffices that the learning with errors problem be hard for quantum polynomial time). Our result shows that the basic two-party feasibility picture from classical cryptography remains unchanged in a quantum world.
We initiate the study of multi-party computation for classical functionalities (in the plain model) with security against malicious polynomial-time quantum adversaries. We observe that existing techniques readily give a polynomial-round protocol, but our main result is a construction of *constant-round* post-quantum multi-party computation. We assume mildly super-polynomial quantum hardness of learning with errors (LWE), and polynomial quantum hardness of an LWE-based circular security assumption. Along the way, we develop the following cryptographic primitives that may be of independent interest: 1. A spooky encryption scheme for relations computable by quantum circuits, from the quantum hardness of an LWE-based circular security assumption. This yields the first quantum multi-key fully-homomorphic encryption scheme with classical keys. 2. Constant-round zero-knowledge secure against multiple parallel quantum verifiers from spooky encryption for relations computable by quantum circuits. To enable this, we develop a new straight-line non-black-box simulation technique against *parallel* verifiers that does not clone the adversary's state. This forms the heart of our technical contribution and may also be relevant to the classical setting. 3. A constant-round post-quantum non-malleable commitment scheme, from the mildly super-polynomial quantum hardness of LWE.
How could quantum cryptography help us achieve what are not achievable in classical cryptography? In this work we study the classical cryptographic problem that two parties would like to perform secure computations with long outputs. As a basic primitive and example, we first consider the following problem which we call secure function sampling with long outputs: suppose
f:{0,1}n→{0,1}m is a public, efficient classical function, where
m is big; Alice would like to sample
x from its domain and sends
f(x) to Bob; what Bob knows should be no more than
f(x) even if it behaves maliciously. Classical cryptography, like FHE and succinct arguments [Gen09,Kil92,HW15], allows us to achieve this task within communication complexity
O(n+m); could we achieve this task with communication complexity independent of
m? In this work, we first design a quantum cryptographic protocol that achieves secure function sampling with approximate security, within
O(n) communication (omitting the dependency on the security parameter and error tolerance). We also prove the classical impossibility using techniques in [HW15], which means that our protocol indeed achieves a type of quantum advantage. Building on the secure function sampling protocol, we further construct protocols for general secure two-party computations [Yao86,GB01] with approximate security, with communication complexity only depending on the input length and the targeted security. In terms of the assumptions, we construct protocols for these problems assuming only the existence of collapsing hash functions [Unr16]; what's more, we also construct a classical-channel protocol for these problems additionally assuming the existence of noisy trapdoor claw-free functions [BCMVV,BKVV].
A significant branch of classical cryptography deals with the problems which arise when mistrustful parties need to generate, process, or exchange information. As Kilian showed a while ago, mistrustful classical cryptography can be founded on a single protocol, oblivious transfer, from which general secure multiparty computations can be built. The scope of mistrustful quantum cryptography is limited by no-go theorems, which rule out, inter alia, unconditionally secure quantum protocols for oblivious transfer or general secure two-party computations. These theorems apply even to protocols which take relativistic signaling constraints into account. The best that can be hoped for, in general, are quantum protocols which are computationally secure against quantum attack. Here a method is described for building a classically certified bit commitment, and hence every other mistrustful cryptographic task, from a secure coin-tossing protocol. No security proof is attempted, but reasons are sketched why these protocols might resist quantum computational attack.
Properties of quantum mechanics such as entanglement and the no-cloning theorem enable new forms of cryptography that are unattainable in classical models of computation. Quantum information, however, is harder to process, store, and transmit than classical information. As such, it is desirable to construct semi-quantum cryptographic protocols where only a subset of the parties have quantum capabilities while the rest operate classically. In this dissertation, we analyze the security of semi-quantum protocols based on two approaches: (i) nonlocality-based techniques and (ii) the hardness of the Learning with Errors (LWE) problem. In the first part of the dissertation, we leverage a form of Bell test to construct a quantum position verification (QPV) protocol. Initial QPV protocols required verifiers to prepare and send quantum states to an honest prover to achieve security against adversaries with bounded memory or entanglement. Later work constructed QPV protocols with classical verifiers but required additional assumptions such as the hardness of LWE or of random circuit sampling. We construct a variant of QPV where classical verifiers verify the spatial locations of two provers. We use the nonlocal correlations produced by the two provers to show security against adversaries with bounded quantum memory without making any computational intractability assumptions. In the second part of the dissertation, we use trapdoor claw-free functions (TCFs) to construct semi-quantum cryptographic protocols. TCFs, which are constructible from the hardness of LWE, have been shown to be immensely valuable in the construction of classically verifiable quantum cryptographic protocols. As opposed to previous work where the server is asked to prepare a claw state and perform Pauli-X and Z measurements, we use a technique that leverages the entire range of qubit measurements on the XY-plane. We use this technique to construct three protocols: (i) a one-round blind remote state preparation protocol that delegates the preparation of an arbitrary state on the XY-plane up to a Pauli-X correction; (ii) a two-round proof of quantumness whose security is directly in terms of the hardness of LWE and only requires the prover to prepare and measure a single claw state; and (iii) a 1-of-2 Puzzle with a single qubit auxiliary state.
Quantum cryptography has emerged as a revolutionary technology for ensuring secure communication in the era of quantum computing. While existing research primarily focuses on theoretical frameworks and small-scale experimental setups, significant challenges remain in practical implementation, scalability, and security vulnerabilities. This study aims to bridge the gap between theory and real-world deployment by developing robust quantum cryptographic protocols that address key challenges such as noise management, side-channel attacks, and Trojan horse attacks. Additionally, we propose an optimized quantum key distribution (QKD) mechanism that ensures secure communication over long distances under realistic conditions. Our research integrates post-quantum cryptography with quantum cryptographic techniques to provide a hybrid security model that is resilient against both classical and quantum computing threats. By leveraging commercially available quantum hardware and advanced randomness extraction methods, this study contributes to the development of scalable, secure, and efficient quantum communication networks. The findings of this research will play a crucial role in advancing secure digital communication systems and fortifying data security in the post-quantum era.
Quantum cryptography has emerged as a revolutionary technology for ensuring secure communication in the era of quantum computing. While existing research primarily focuses on theoretical frameworks and small-scale experimental setups, significant challenges remain in practical implementation, scalability, and security vulnerabilities. This study aims to bridge the gap between theory and real-world deployment by developing robust quantum cryptographic protocols that address key challenges such as noise management, side-channel attacks, and Trojan horse attacks. Additionally, we propose an optimized quantum key distribution (QKD) mechanism that ensures secure communication over long distances under realistic conditions. Our research integrates post-quantum cryptography with quantum cryptographic techniques to provide a hybrid security model that is resilient against both classical and quantum computing threats. By leveraging commercially available quantum hardware and advanced randomness extraction methods, this study contributes to the development of scalable, secure, and efficient quantum communication networks. The findings of this research will play a crucial role in advancing secure digital communication systems and fortifying data security in the post-quantum era.