Any two-party cryptographic primitive can be implemented using quantum communication under the assumption that it is difficult to store a large number of quantum states perfectly. However, achieving reliable quantum communication over long distances remains a difficult problem. Here, we consider a large network of nodes with only neighboring quantum links. We exploit properties of this cloud of nodes to enable any two nodes to achieve security even if they are not directly connected. Our results are based on techniques from classical cryptography and do not resort to technologically difficult procedures like entanglement swapping. More precisely, we show that oblivious transfer can be achieved in such a network if and only if there exists a path in the network between the sender and the receiver along which all nodes are honest. Finally, we show that useful notions of security can still be achieved when we relax the assumption of an honest path. For example, we show that we can combine our protocol for oblivious transfer with computational assumptions such that we obtain security if either there exists an honest path, or, as a backup, at least the adversary cannot solve a computational problem.
Any two-party cryptographic primitive can be implemented using quantum communication under the assumption that it is difficult to store a large number of quantum states perfectly. However, achieving reliable quantum communication over long distances remains a difficult problem. Here, we consider a large network of nodes with only neighboring quantum links. We exploit properties of this cloud of nodes to enable any two nodes to achieve security even if they are not directly connected. Our results are based on techniques from classical cryptography and do not resort to technologically difficult procedures like entanglement swapping. More precisely, we show that oblivious transfer can be achieved in such a network if and only if there exists a path in the network between the sender and the receiver along which all nodes are honest. Finally, we show that useful notions of security can still be achieved when we relax the assumption of an honest path. For example, we show that we can combine our protocol for oblivious transfer with computational assumptions such that we obtain security if either there exists an honest path, or, as a backup, at least the adversary cannot solve a computational problem.
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 in which the two parties want to evaluate a joint quantum functionality while using only a classical channel between them. Our first result indicates that it is in general impossible to realize a two-party quantum functionality against malicious adversaries with black-box simulation, relying only on classical channels. The negative result stems from reducing the existence of a black-box simulator to an extractor for classical proof of quantum knowledge, which in turn leads to violation of the quantum no-cloning. Next, we introduce the notion of oblivious quantum function evaluation (OQFE). An OQFE is a two-party quantum cryptographic primitive with one fully classical party (Alice) whose input is (a classical description of a) quantum unitary,
U, and a quantum party (Bob) whose input is a quantum state,
ψ. In particular, Alice receives a classical output corresponding to the measurement of
U(ψ) while Bob receives no output. In OQFE, Bob remains oblivious to Alice's input, while Alice learns nothing about
ψ more than what can be learned from the output. We present two constructions, one secure against semi-honest parties and the other against malicious parties. Due to the no-go result mentioned above, we consider what is arguably the best possible notion obtainable in our model concerning malicious adversaries: one-sided simulation security. Our protocol relies on the assumption of injective homomorphic trapdoor OWFs, which in turn rely on the LWE problem. As a result, we put forward a first, simple and modular, construction of one-sided quantum two-party computation and quantum oblivious transfer over classical networks.
Modern cryptography is more than sending secret messages, and quantum cryptography is more than quantum key distribution. One example is oblivious transfer, which is interesting partly because it can be used to implement secure multiparty computation. We discuss a protocol for quantum XOR oblivious transfer, and how non-interactive quantum oblivious transfer protocols can be “reversed”, so that oblivious transfer is still implemented from a sender to a receiver, but so that it is the receiver who sends a quantum state to the sender, who measures it, instead of the other way round. This is useful when one party can only prepare and send quantum states, and the other party can only measure them, which is often the case in practical quantum communication systems. Both the “original” XOR oblivious transfer protocol and its reversed version have been implemented optically. We also discuss how quantum random access codes can be connected with quantum oblivious transfer.
There are various practical obstacles in quantum cryptography. These include the problems that arise in implementing quantum cryptographic protocols with current and near-term technology, and those that come with the development and security analysis of new protocols. In this work, we examine a few of these obstacles and, for each one, we highlight an approach that aims to mitigate it. We start by examining the setting of device-independence, with oblivious transfer in the bounded-quantum-storage-model as the primitive of interest. The typical approach to enabling device-independence is the use of a Bell-inequality violation, which requires a strict non-communication assumption that is practically difficult to enforce. We develop and analyze the security of a device-independent oblivious transfer protocol that replaces the Bell-inequality violation approach with a computational assumption, thereby relaxing the non-communication assumption. Our second topic examines the problem of noise in a quantum money scheme. We show how to achieve noise-tolerance in the public-key setting. Our scheme can be seen as a generalization of the [AC12] scheme: a valid banknote is now a subspace state possibly affected by noise, and verification is performed by using classical oracles to check for membership in "larger spaces." Additionally, a banknote in our scheme is minted by preparing conjugate coding states and applying a unitary. For our last topic, we consider the general task of proving security against a specious adversary, which is the quantum analogue of the classical semi-honest adversary. A useful feature of specious adversaries is that security against them can guarantee security against stronger adversaries [DNS12]. This motivates the search for a canonical specious adversary, where proving security against such an adversary guarantees security against the entire class of specious adversaries. Within a restricted setting, we define a particular specious adversary and show that it satisfies our definition of canonical.
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].